Соединить 4 точки ломаной линией без пересечений - C#
Формулировка задачи:
Доброго времени суток, вопрос заключается в следующем: Пользователь вводит координаты 4-х точек на плоскости, необходимо максимально простым способом соединить эти точки ломаной линией в четырехугольник без пересечений между линиями. Я набросал оболочку программы, но когда дело дошло до алгоритма соединения ничего не выходит. Помогите пожалуйста написать адекватно работающую функцию GetNext() которая определяет след. точку. Я определяю крайнюю левую точку и двигаюсь от неё.
class DotsConnecter
{
private dot[] dots;
public DotsConnecter()
{
dots = new dot[4];
}
private struct dot
{
public double x;
public double y;
public bool isActive;
public int id;
}
public void Start()
{
Console.WriteLine("Hello World!");
GetDots();
ShowResults(ConnectDots());
}
private void GetDots()
{
Console.WriteLine("Enter coordinates of your points:");
for (byte i = 0; i < 4; i++)
{
Console.Write("dot" + (i + 1).ToString() + ".x = ");
dots[i].x = Convert.ToDouble(Console.ReadLine());
Console.Write("dot" + (i + 1).ToString() + ".y = ");
dots[i].y = Convert.ToDouble(Console.ReadLine());
dots[i].isActive = true;
dots[i].id = i + 1;
}
}
private dot[] ConnectDots()
{
dot[] sequence = new dot[5];
sequence[0] = GetLeft();
sequence[4] = sequence[0];
sequence[1] = dots[GetNext(sequence[0])];
sequence[2] = dots[GetNext(sequence[1])];
for (byte i = 0; i < 4; i++)
if (dots[i].isActive == true)
{
sequence[3] = dots[i];
dots[i].isActive = false;
}
return sequence;
}
private void ShowResults(dot[] sequence)
{
Console.WriteLine("It will be:");
Console.Write(
"dot" + sequence[0].id + "->" +
"dot" + sequence[1].id + "->" +
"dot" + sequence[2].id + "->" +
"dot" + sequence[3].id + "->" +
"dot" + sequence[4].id
);
}
private double Angle(dot a, dot b)
{
if (a.x == b.x)
if (a.y < b.y)
return Math.PI / 2;
else
return Math.PI / (-2);
else
if (a.y == b.y)
if (a.x < b.x)
return 0;
else
return Math.PI;
else
return Math.Atan((b.y - a.y) / (b.x - a.x));
}
private dot GetLeft()
{
dot min = dots[0];
byte j = 0;
for (byte i = 1; i < 4; i++)
if (dots[i].x < min.x)
{
min = dots[i];
j = i;
}
dots[j].isActive = false;
return min;
}
private byte GetNext(dot a)
{
byte j = 0;
double maxAngle = 0;
double currentAngle = 0;
for (byte i = 0; i < 4; i++)
{
if (dots[i].isActive == true)
{
currentAngle = Math.Abs(Angle(a, dots[i]));
if (maxAngle < currentAngle)
{
j = i;
maxAngle = currentAngle;
}
}
}
dots[j].isActive = false;
return j;
}
}Решение задачи: «Соединить 4 точки ломаной линией без пересечений»
textual
Листинг программы
struct dot
{
public double x;
public double y;
public bool isActive;
public int id;
public override string ToString()
{
return string.Format("x={0}; y={1}", x, y);
}
}
class Program
{
static IEnumerable<dot> Foo(dot[] dots)
{
return dots.Take(1).Union(
dots.Skip(1).OrderBy(dot =>
Math.Atan2(dot.x - dots[0].x, dot.y - dots[0].y)));
}
static void Main()
{
dot[] dots = {
new dot() { x = 1, y = 1 },
new dot() { x = 3, y = 3 },
new dot() { x = 5, y = 1 },
new dot() { x = 2, y = 3 },
new dot() { x = 4, y = 2 }
};
foreach(var dot in Foo(dots))
{
Console.WriteLine(dot);
}
Console.ReadLine();
}
}