Balancer>Пардон, всё усложняется. Полигон может быть невыпуклым. Т.е. задача стоит из набора точек их сортировкой построить несамопересекающийся полигон.
Эх, облом. А я-то простенькую идейку соорудил, базирующуюся на заведомой выпуклости.
>Опционально - наибольшей площади
А вот это ИМХО снова немного упрощает дело.
Предыдущая идея заключалась в том, что, сидя внутри выпуклой фигуры (в т.ч. и на её границе), можно взглядом ощупать всю её границу, вертя головой только в одну сторону.
Ну, и мысля была такая: переносим начало координат в любую точку, выбираем из знаков "+" и "-" любимый, после чего упорядочиваем массив оставшихся точек, имея критерий для упорядочения любой пары из них - знак векторного произведения векторов, соединяющих начало координат с этими точками. Например, если больше любим "+", то вторая точка следует за первой при условии, что x1y2>x2y1. Если x1y2<x2y1, то первая следует за второй в нашей воображаемой линии. Если они равны, то либо фигура невыпуклая, либо координаты точек совпадают, либо одна из точек лежит на стороне многоугольника. Нифига не страшно, т.к. можно отсортировать это подмножество точек, перенеся начало координат в другую точку. В общем, не проблема.
И все, задача свелась к сортировке массива.
Я бы начал с метода дихотомического деления, хотя не спец по этой части.
Дык вот, ИМХО, при условии максимальной площади (а ИМХО это значит, "максимально возможно выпуклого") невыпуклого многоугольника, этим критерием упорядочения можно пользоваться и дальше, без изменения.
Только случаи, когда x1y2=x2y1, ИМХО, разбирать будет муторно. Копать надо, а лень.