Как отсортировать точки в многоугольнике карт Google, чтобы линии не пересекались?

Question

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

Чтобы увидеть, о чем я говорю, перейдите на эту страницу и выполните следующие шаги:

1. нажмите 4 точки, чтобы сделать 4 угла коробки
2. нажмите между каждым из 4 точки, которые вы только что сделали для дальнейшего определить периметр ящика
3. клик сделан

Вы должны увидеть что-то вроде этого:

Есть ли простой способ решить эту проблему, или я в основном имею дело с ситуацией типа «Командор»? Вся логика выполнена в javascript, поэтому не стесняйтесь «просматривать исходные тексты», если вы хотите посмотреть, как я это делаю.

Answer 1

Это не выпуклый корпус.

Представьте, что у вас была остановка в "Линфилд-Оукс" недалеко от того места, где пересекаются эти две линии. Выпуклая оболочка пропустит это и проведет прямую линию между «международной» и «82»

То, что вы пытаетесь сделать, это определить, находится ли каждая новая точка внутри многоугольника, образованного существующими точками - если это так, то вам нужно разбить ближайшую сторону многоугольника и вставить новую точку на этом ребре. См. http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm для точки в тестах многоугольника.

Answer 2

В прошлом я решал похожую проблему и столкнулся с проблемой, о которой упоминал Джеффри, из-за того, что не знал точно, какую форму ожидает пользователь. В итоге я решил эту проблему, потребовав от пользователя выбора двух точек, между которыми он хотел бы установить новую точку. Требуется больше кликов (3 против 1), но пользователь полностью контролирует, какую форму он хочет. Возможно, у меня еще есть код, который я где-то использовал (он был для Google Maps), если вам интересно.

Answer 3

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

Например, предположим, вам даны точки A-B-C-D-E-F-A, где B-C и E-F пересекаются. Вы можете пересечь их, изменив подпоследовательность C..E, что приведет к A-B-E-D-C-F-A.

Это что-то попробовать в любом случае.