Ищется алгоритм построения выпуклого многоугольника из случайно перемешанных точек.

Есть точки, составляющие выпуклый многоугольник. Они перемешаны случайным образом. Как отсортировать их так, чтобы их последовательность описывала выпуклый многоугольник?

Например, из:

0,0
0,10
10,0
10,10

получить:

0,0
10,0
10,10
0,10

Первый, пришедший в голову вариант: находим среднюю точку (можно тупо по среднему X и среднему Y) и дальше сортируем по углу из этой точки на искомую.

Но хочется без углов

А угол - это тот же наклон прямой. Т.е. отношение (x-x0)/(y-y0), с дополнительным условием y-y0 > 0 - по нему высортировывается вторая половина точек.

Вообще говоря, условием упорядоченного вхождения точек в выпуклый многоугольник является то, что все остальные точки лежат по другую сторону от прямой соединяющей две точки. Т.е. для каждой точки с номером N надо подобрать из оставшихся такую точку, что ВСЕ остальные точки лежат от прямой построенной по точкам N, N+1 по одну сторону - причем такая точка имхо единственная.

Задача вычислительной сложности N*N*N, я так понимаю. Т.е. выбираем любую точку. Заносим в массив как точку номер 0. После этого ищем точку номер 1, такую, чтобы все точки лежали от прямой Т0-Т1 по одну сторону. Как только находим такую точку - заносим ее в массив и ищем среди оставшихся точку номер 2, такую, чтобы все точки включая уже найденные лежали от прямой Т1-Т2 по одну сторону. Ну и т.д., пока точки не кончатся.

Прямая описывается уравнением y = y0 + (y1-y0)/(x1-x0)*x. Растояние от точки до прямой -


вот таким выражением, где х, у - это координаты примеряемой точки, а х0,х1, у0, у1 - координаты точек, задающих прямую.


Дополнение - кроме особых случаев (вертикальная прямая), все точки должны лежать ВЫШЕ или НИЖЕ прямой. Или, если допускаются точки на грани - то выше или на ней. Или ниже и на ней.

Позор. Не знаем стандартных функций явы. Я ведь правильно понял, что сортировка это не самоцель, а создание обьекта содержащего многоугольник?

>Есть точки, составляющие выпуклый многоугольник.
Т.е. не нужно учитывать вариант, когда такой номер не пройдет - это хорошо.

>Они перемешаны случайным образом. Как отсортировать их так, чтобы их последовательность описывала выпуклый многоугольник?
Наличие точек на одной линии не исключается?

Сколько платим?

Предполагаем, что ВСЕ точки - вершины этого многоугольника.

1. Выбираем любую точку (например - первую точку массива). Примем ее координаты за х00,у00
2. Перебираются все точки, для каждой вычисляется значение:

1.  type A = (y00!=y) ? (x-x00)/(y-y00) : MAXVAL;
2.  longtype B = A + (у00>y) ? 0 : MAXVAL+1; // где MAXVAL - максимальное положительное число в употребляемом типе type

3. Массив точек сортируется по B любым подходящим случаю способом.

Как именно выразить в коде переход через бесконечность - дело десятое, главное, чтобы число "после" было гарантировано больше числа "до".

Итоговый о(N) = N + o(N)_алгоритма_сортировки

Как-то так, IMHO.
В смысле памяти - требуется массив из N int (как чистый минимум), но, ИМХО, сложно придумать что-то, что будет быстрее. Можно и без массива - тут как всегда, можно заплатить памятью за скорость и наоборот.

Ну, ты тоже пошёл с углами, точнее с тагенсами, только ещё и систему координат перенёс.

Пардон, всё усложняется. Полигон может быть невыпуклым. Т.е. задача стоит из набора точек их сортировкой построить несамопересекающийся полигон.

Вариант с углами отпадает

Кроме Монте-Карло (страшно подумать, сколько оно будет жрать ресурсов, но, в принципе, оно нужно один раз на загрузке данных) в голову ничего не приходит.

...

Кстати, а как проверить самопересечённость полигона, кроме как последовательное проверкой на пересечение всех пар отрезков?

Balancer>Пардон, всё усложняется. Полигон может быть невыпуклым. Т.е. задача стоит из набора точек их сортировкой построить несамопересекающийся полигон.
Эх, облом. А я-то простенькую идейку соорудил, базирующуюся на заведомой выпуклости.

>Опционально - наибольшей площади
А вот это ИМХО снова немного упрощает дело.

Предыдущая идея заключалась в том, что, сидя внутри выпуклой фигуры (в т.ч. и на её границе), можно взглядом ощупать всю её границу, вертя головой только в одну сторону.

Ну, и мысля была такая: переносим начало координат в любую точку, выбираем из знаков "+" и "-" любимый, после чего упорядочиваем массив оставшихся точек, имея критерий для упорядочения любой пары из них - знак векторного произведения векторов, соединяющих начало координат с этими точками. Например, если больше любим "+", то вторая точка следует за первой при условии, что x1y2>x2y1. Если x1y2<x2y1, то первая следует за второй в нашей воображаемой линии. Если они равны, то либо фигура невыпуклая, либо координаты точек совпадают, либо одна из точек лежит на стороне многоугольника. Нифига не страшно, т.к. можно отсортировать это подмножество точек, перенеся начало координат в другую точку. В общем, не проблема.

И все, задача свелась к сортировке массива.

Я бы начал с метода дихотомического деления, хотя не спец по этой части.

Дык вот, ИМХО, при условии максимальной площади (а ИМХО это значит, "максимально возможно выпуклого") невыпуклого многоугольника, этим критерием упорядочения можно пользоваться и дальше, без изменения. Только случаи, когда x1y2=x2y1, ИМХО, разбирать будет муторно. Копать надо, а лень.

Упс, ошибся. Вот тут:

>...(а ИМХО это значит, "максимально возможно выпуклого")...
Критерий вообще не катит. По нему будет построен один из возможных многоугольников с наименее резкими изломами сторон, м.быть, за исключением тех 2х, что приходятся на начало координат. Я так думаю.

Площадь любого многоугольника считается элементарно, в нашем случае даже можно обойтись чисто целочисленными расчетами, если координаты целые. Но, блин, перебор всех возможных - это атас. Как вариант - проделать вышеупомянутый алгоритм, оочередно помещая начало координат в каждую точку. Этот алгоритм заведомо будет строить только односвязные многоугольники, ИМХО их площадь больше многосвязных.

После этого, имея упорядоченный массив координат, также упорядоченно строятся и складываются векторные произведения для каждой пары соседних точек. Модуль суммы - удвоенная площадь многоугольника. Насчитав таких удвоенных площадей, выбираем самую большую.

ЗЫ: все картинки держал в уме, ничего не рисуя, так шта...

Ужасы, блин... А, ведь, на глаз задача решается как правило легко Каким же, интересно, алгоритмом?

Неоднозначности, конечно, есть (примитивный пример - построить пятиугольник из точек на домино "5" - "конвертик", возможны четыре равновероятных варианта.) Но это - редкость...

Может, тупо перебирать все возможные варианты, считая максимальную площадь? Скажем, для набора из 6 точек это всего 720 комбинаций - вполне терпимо, если площадь будет считаться быстро.

... Всего есть 8941 локация, 40229 точек, т.е. по 4.5 точки. Где-то будет около миллиона измерений площадей. Если секунд за 20 на типичной машине на Java будет решаться - прекрасно.

Как быстро посчитать площадь?

>Неоднозначности, конечно, есть (примитивный пример - построить пятиугольник из точек на домино "5" - "конвертик", возможны четыре равновероятных варианта.) Но это - редкость...
При хорошем наборе точек их сумасшедшее количество. Вон, пятиконечную звезду можно получить и цельную по контуру, и пятисвязную (пентагон, к коему крепятся лучи, выпал). А сколько еще хреновин из этих 10 точек можно получить...

>Как быстро посчитать площадь?
Дык я же сказал, как удвоенная площадь быстро считается - векторными произведениями. Ну, сдвиньте результат вправо, и бит С вам укажет, что делать дальше.

И вообще: площадь уже имеющегося многоугольника можно считать по указанному алгоритму, поместив начало координат куда угодно. Никаких углов, никакой тригонометрии - почти сплошь целочисленка.

>А, ведь, на глаз задача решается как правило легко Каким же, интересно, алгоритмом?
Мысленным закрашиванием всей области куда попали точки, последовательным выделением и отбрасыванием области, где точек явно нет. А потом - тщательное рассмотрение по краям неотброшенной области.

+

>"Точек явно нет"? А как именно это узнать?
Увидеть. Balancer спросил про алгоритм, по которому наши мозги работают.

А собственно, если подумать - вроде как, как раз максимальную площадь и получим. Хотя хрен знает. Думать лень.