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

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

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

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

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

alt text

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

Ответы

Ответ 1

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

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

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

Ответ 2

Это не выпуклая оболочка.

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

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

Ответ 3

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