То, как отсортировать точки в Google, отображает полигон так, чтобы строки не пересекались?
Я пытаюсь сделать карту, где пользователь может обрисовать в общих чертах любую форму, они хотели бы. Но я сталкиваюсь с проблемой, где пользователи могут выбрать точки, которые будут раздражать строки полигона и исключать область, которую я хотел бы включать.
Для наблюдения то, что я говорю о движении к этой странице и беру следующие шаги:
- нажмите 4 точки для создания 4 углов поля
- нажмите промежуточный каждая из 4 точек, которые Вы просто сделали для дальнейшего определения периметра поля
- нажмите сделанный
Необходимо видеть что-то вроде этого:
Существует ли простой способ решить эту проблему, или я в основном справляюсь с ситуацией с типом "Коммивояжера" здесь? Вся логика сделана в JavaScript, так не стесняйтесь "просматривать источник", если требуется видеть, как я делаю это.
3 ответа
Выпуклая оболочка может включать области, которые пользователь желает исключить. Вот еще один способ приблизиться к этому, который может дать более удовлетворительные результаты. Проверьте каждую линию, чтобы увидеть, какие из них пересекаются (есть много способов сделать это). Затем поменяйте местами последовательность точек, которые появляются между этими двумя линиями.
Например, предположим, что вам даны точки A-B-C-D-E-F-A, где пересекаются B-C и E-F. Вы можете отключить их, изменив подпоследовательность C..E на противоположную, что приведет к A-B-E-D-C-F-A.
В любом случае это стоит попробовать.
Это не выпуклая оболочка.
Представьте, что вы остановились в «Линфилд-Оукс» рядом с местом пересечения этих двух линий. Выпуклая оболочка пропустит это и проведет прямую линию между "international" и "82"
. Вы пытаетесь определить, находится ли каждая новая точка внутри многоугольника, образованного существующими точками - если это так, то вам нужно чтобы разбить ближайшую сторону многоугольника и вставить новую точку на этом ребре. См. http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm для получения информации о точках в тестах многоугольников.
В прошлом я решал похожую проблему и столкнулся с проблемой, о которой упоминал Джеффри, когда не знал точно, какой формы ожидает пользователь. В итоге я решил эту проблему, потребовав от пользователя выбрать две точки, между которыми должна находиться новая точка. Это требует больше кликов (3 против 1), но пользователь полностью контролирует, какую форму он хочет получить. Возможно, у меня еще где-то есть код, который я использовал (он был для Google Maps), если вам интересно.