Задача с сортировкой (Delphi). Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную

[Леон2110]

Здравствуйте, подскажите как правильно это реализовать, вот задание:

Дано n точек на плоскости. Указать (n-1)-звенную несамопересекающуюся незамкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам ломаной разрешается лежать на одной прямой.) Обеспечить число действий порядка n*log n.

Указание. Упорядочим точки по x-координате, а при равных x-координатах - по y-координате. В таком порядке и можно проводить ломаную.

С одной стороны все понятно,
1. создаю массив, наполняю его координатами (тут пока не совсем понимаю как их наполнять ведь в координатах будет две цифры по х и по у)
2. отсортировать массив по х это понятно, но как подставить если по х одинаковые значения, чтобы смотрелось на вторую координату y.
3. далее уже с упорядоченного массива можно построить график и прочертить ломаную.

Пока все проблемы, что непонятно как быть со второй координатой? есть мысль пузырьком упорядочить, но как туда подставить проверку на -y координаты если по -х совпадут значения.

[BHMJ(G)]

Надо создать массив структур и отсортировать его qsort'ом. В функции сравнения сначала сравнивать X'ы, а при их совпадении -- Y'и. По отсортированному таким образом массиву координат легко строится ломаная.

Кстати, интересно было бы модифицировать алгоритм так, чтобы по заданному набору случайных точек строилась ломаная, закрученная по спирали, от краев области к центру.

[rrrFer]

Модифицировать можно, но эффективность упадет. Зачем нужны эти спирали вообще, что за извращения?

Упадет потому, что надо будет получать точки выпуклой оболочки, соединять их, получать новую оболочку и т.п. Время будет вроде бы тоже n*log(n), но лишних операций будет достаточно. Достаточно и непонятно из за чего вся эта свистопляска.

[BHMJ(G)]

Спираль -- это усложнённая вариация задачи. Как я и написал, просто интересно было бы её решить, почему сразу "извращения"? В результате работы программы, решающей исходную задачу, область будет "заштрихована" линиями, идущими более или менее вертикально, а в моей вариации получится красивая спиралька. Попробую сделать, отпишусь по результатам.

[Леон2110]

Спасибо за ответы, но не получается пока. *(плохо с программированием)

К примеру сделал массив (пока без рандома или ручного ввода):
Const
po : Array[0..4] Of TPoint = ((x:20; y:40),(x:40; y:40),(x:30; y:10),(x:50; y:20),(x:30; y:20));


Вывожу на форме по нажатии кнопки так:
procedure TForm1.btn1Click(Sender: TObject);
begin
Form1.Canvas.Polygon(po);
end;

Помогите как его упорядочить перед выводом.

[BHMJ(G)]

Используйте любой алгоритм сортировки (ищите на этом сайте по запросу "сортировка массива delphi"). В том месте, где сравниваются элементы массива, сначала сравнивайте x координаты, при их равенстве -- у координаты.

Например при пузырьковой сортировке код, сравнивающий элементы будет такой:

if (po[i].x > po[j].x) or ( (po[i].x = po[j].x) and (po[i].y > po[j].y) ) then begin
  ; меняем местами элементы
end;

[Леон2110]

Нашел такой пример:

//кнопка заполняет мемо 20-ю случайными числами
procedure TForm1.Button2Click(Sender: TObject);
begin
 Memo1.Clear;
for i:=0 to 19 do
begin
 a[i]:=Random(20) ;
   Memo1.Lines.Add(IntToStr(a[i]))
end;
end;

//процедура сортировки пузырьком
procedure BubbleSort( var a: array of integer; min, max: Integer);
var
i, j, tmp: integer;
begin
for i:=min to max do
for j:=min to max-i do
if A[j]>A[j+1] then
begin
tmp:=A[j];
A[j]:=A[j+1];
A[j+1]:=tmp;
end;
end;

//кнопка вызывает процедуру сортировки и помещает отсортированные данныее в мемо 2
procedure TForm1.Button4Click(Sender: TObject);
begin
BubbleSort(a,0,high(a));
for i:=0 to 19 do
begin
   Memo2.Lines.Add(IntToStr(a[i]))
end;
end;

Все работает, вот только это немного другой пример, тут массив с целочисленными данными, а у меня раньше был массив TPoint с двумя координатами, подскажите пожалуйста как правильно сделать, чтобы в этом массиве было по 2 координаты.

[BHMJ(G)]

В BubbleSort у параметра a поменяйте тип вместо "массив целых чисел" сделайте "массив TPoint'ов". Алгоритм остаётся тот же, только вместо сравнения чисел сравнивайте точки, вернее их координаты, код сравнения я уже приводил. Аналогично, вместо обмена двух чисел между ячейками массива надо обменивать структуры.

[Леон2110]

так немного вроде получилось, в мемо1 я записал координаты:
x:20; y:40
x:40; y:30
x:30; y:50
x:50; y:20
x:30; y:20
x:20; y:60
x:40; y:30
x:30; y:40
x:50; y:30
x:30; y:30
x:20; y:50
x:40; y:10
x:30; y:10
x:50; y:20
x:30; y:20
x:20; y:30
x:40; y:50
x:30; y:20
x:50; y:30
x:30; y:10

В коде я заменил массив на TPoint, вставил код для сравнения, но еще проблемы есть, как быть с этими строками перемещения элементов массива и передачи элементов к вызову процедуры:

var
  Form1: TForm1;
  i:integer;

implementation

{$R *.dfm}

//процедура сортировки
procedure BubbleSort( var a: array of TPoint; min, max: Integer);
var
i, j, tmp: integer;
begin
for i:=min to max do
for j:=min to max-i do
//if A[j]>A[j+1] then  begin
if (A[i].x > A[j].x) or ( (A[i].x = A[j].x) and (A[i].y > A[j].y) ) then begin
tmp:=A[j];
A[j]:=A[j+1];
A[j+1]:=tmp;
end;
end;

//кнопка запускающая процедуру сортировки и вывод в мемо2
procedure TForm1.Button4Click(Sender: TObject);
begin
BubbleSort(a,0,high(a));
for i:=0 to 19 do
begin
   Memo2.Lines.Add(IntToStr(a[i]))
end;
end;

end.

[Леон2110]

Теперь вот как:

var
  Form1: TForm1;
  i:integer;
  a: array[0..6] of TPoint = ((x:10; y:20),(x:20; y:30),(x:30; y:40),(x:40; y:50),(x:50; y:60),(x:60; y:70),(x:70; y:80));
implementation

{$R *.dfm}

//Процедура сортировки
procedure BubbleSort( var a: array of TPoint; min, max: Integer);
var
i, j: integer;
tmp: TPoint;
begin
for i:=min to max do
for j:=min to max-i do
if (A[i].x > A[j].x) or ( (A[i].x = A[j].x) and (A[i].y > A[j].y) ) then begin
tmp:=A[j];
A[j]:=A[j+1];
A[j+1]:=tmp;
end;
end;

//кнопка запускающая процедуру сортировки и вывод в мемо2
procedure TForm1.Button4Click(Sender: TObject);
begin
BubbleSort(a,0,high(a));
for i:=0 to 6 do
begin
  Memo2.Lines.Add (IntToStr(A[i].x)+ ','+ IntToStr(A[i].y)  );
end;
end;

end.

Вот как работает сортировка, из уже отсортированных данных делает вот что:
Координаты в массиве / вывод в мемо2
x:10; y:20 / 10,20
x:20; y:30 / 40,50
x:30; y:40 / 20,30
x:40; y:50 / 30,40
x:50; y:60 / 50,60
x:60; y:70 / 60,70
x:70; y:80 / 70,80

Подскажите, что еще не так в коде?