как упорядочить вершины в простом невыпуклом многоугольнике

Question

У меня есть проблема, когда у меня есть ряд точек для простого невыпуклого многоугольника (надеюсь, у меня правильная терминология).Но точки не обязательно в порядке (то есть по часовой стрелке или против часовой стрелки).Чтобы API рисования Flash правильно рисовал область заливки, мне нужно, чтобы эти точки развивались по краям (чтобы наконец соединиться с начальной точкой).

Есть ли способ сортировки моего списка декартовыхкоординаты по часовой стрелке или против часовой стрелки, чтобы я мог рисовать свою фигуру из точки в точку, не «поднимая ручку»?

Я видел один пост для сортировки 4-х точек многоугольника, но я думаю, что это был особыйдело только за 4 балла.Мои фигуры имеют минимум 6 баллов.В списке каждая запись гарантированно смежна (по часовой стрелке или против часовой стрелки) по крайней мере с одним из своих соседей (либо с предыдущей точкой, либо с последующей).Например: A, B, D, C ... или B, A, D, C ... но не A, C, B, D ... (мне нужно отсортировать, чтобы получитьили A, B, C, D или D, C, B, A).Я нашел этот пост, но он, похоже, остался без ответа: Сортировка списка точек в многоугольник

Производительность процессора является проблемой.Но даже «медленное» решение, если его легко реализовать и понять (для следующего программиста), может быть приемлемым, если я смогу создать эффективный механизм кэширования.

Я хотел бы прикрепить картинку кпоказать пример того, что мне нужно сделать, но у меня еще нет 10 очков репутации.В любом случае, если бы у меня было средство для сортировки вершин 3-го примера в этом списке полигонов, это было бы идеально: http://upload.wikimedia.org/wikipedia/commons/1/1f/Assorted_polygons.svg

Я действительно ценю любую помощь, спасибо!

РЕДАКТИРОВАТЬ: Я действительно могу гарантировать центральную точку для системы координат - это будет центр экрана.Все точки будут между 0 и шириной экрана / высотой (начало координат, очевидно, ширина / высота / 2).Я не могу гарантировать, что полигон будет содержать исходную точку внутри.Это редкое исключение, но я должен это учитывать.

Кстати, причина, по которой мои сегменты не обязательно расположены по порядку, заключается в том, что они генерируются с использованием Conrec: http://paulbourke.net/papers/conrec/ (они являются контурными линиями).Я упорядочиваю сегменты линии контура, сгенерированные Conrec, используя следующее: Как собрать массив (ы) непрерывных точек для линии контура, используя Conrec Теперь проблемный случай для внешних линий контура на карте.Они будут пересекаться с краем карты (т. Е. Не образуют замкнутый многоугольник).В этом случае я рисую по краям границ карты, пока я не соединюсь заново с местом, где линия начала (на краю карты), или линия родного брата не войдет в карту (повторяясь, пока я в конечном итоге не вернусь к своему исходному месту).точка).Затем я могу нарисовать область и заставить API заполнения работать.Надеюсь, эта информация поможет.Я предположил, что лучше всего было бы создать упорядоченный список вершин многоугольника, но, возможно, нужен другой подход.

Answer 1

Я думаю об алгоритме O(n^2):
Поскольку у вас есть точки для того, чтобы они были нарисованы (надеюсь), вы знаете конечные точки каждого ребра.
Выберите точку для начала, затем продолжайте, пока не пересечете другой край.
Затем вы отмечаете это место, продолжайте движение по новому ребру, пока не достигнете еще одного ребра или конечной точки. Всякий раз, когда вы достигаете точки, где вы меняете края, перечислите это. Как только вы достигнете начальной точки, все готово.

Answer 2

Простой пример, показывающий, что проблема не является однозначно решаемой, - это точки a = (0,0), b = (2,0), c = (1,1), d = (1,2);каждый из порядков (a, b, c, d, a), (a, b, d, c, a) (a, c, b, d, a) являются простыми многоугольниками.

Answer 3

Возможно, вы имеете в виду, что многоугольник является выпуклым (т.е. он не вогнутый). В противном случае я не думаю, что то, что вы делаете, действительно возможно (может быть несколько способов «соединить точки» и сформировать многоугольник).

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

Редактировать: Хорошо, только что посмотрел на ваш пример из Википедии, и вы делаете означает не выпуклый. Я не думаю, что это возможно, к сожалению.

Answer 4

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