Как упорядочить вершины в простом невыпуклом многоугольнике
У меня есть проблема, когда у меня есть ряд точек для простого невыпуклого многоугольника (надеюсь, у меня правильная терминология). Но точки не обязательно в порядке (т.е. по часовой стрелке или против часовой стрелки). Для того, чтобы 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 заполнения работать. Надеюсь, эта информация поможет. Я предположил, что лучше всего было бы создать упорядоченный список вершин многоугольника, но, возможно, нужен другой подход.
4 ответа
Возможно, вы имеете в виду, что многоугольник является выпуклым (то есть не вогнутым). В противном случае я не думаю, что то, что вы делаете, на самом деле возможно (может быть несколько способов "соединить точки" и сформировать многоугольник).
Одна из техник, о которой я могу подумать в этом случае: во-первых, первые два элемента в списке должны образовывать ребро, по правилам, которые вы даете. Затем попробуйте добавить вершины, как они появляются в порядке списка; в каждом случае, если результат может быть только вогнутым, удалите предыдущий элемент из списка результатов и пока игнорируйте его. После того, как вы пройдете список источников, если вы все еще пропускаете вершины, переходите к этим пропущенным вершинам.
Изменить: Хорошо, только что посмотрел на ваш пример из Википедии, и вы имеете в виду невыпуклые. Я не думаю, что это возможно, к сожалению.
Я думаю о O(n^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) являются простыми многоугольниками.