Это довольно долго, только потому, что вопрос такой большой.Я пытался сгруппировать свои комментарии, основываясь на ваших пунктах.
Компоненты для рисования полигонов
Я предполагаю, что вы будете иметь ограниченный успех без предоставления дополнительной информации- компонент для рисования полигонов будет очень сильно связан с языком и парадигмой пользовательского интерфейса, которые вы используете для остальной части вашего проекта, т.е.код для веб-компонента будет сильно отличаться от собственного компонента.
Возможно, альтернативой является отделение этого элемента процесса от остальной части того, что вы пытаетесь сделать.Есть несколько совершенно фантастических уже существующих редакторов, которые вы можете использовать для создания 2D и 3D полигонов.
Inkscape - это пример редактора векторной графики, который позволяет легко вводить 2-мерные полигоны и имеет преимущество в создании выходного SVG, который достаточно легко анализировать.
В трех измерениях Blender - это редактор с открытым исходным кодом, который можно использовать для создания произвольных геометрий, которые можно экспортировать в несколько форматов.
Если вы можете использовать API-интерфейс Google-карт (возможно, в нативном элементе управления рендерингом HTML), и вас интересует добавление пространственных точек на оверлей карты, вас может заинтересовать связанный переход по кликувывести вопрос о многоугольнике в stackoverflow .Исходя из прошлого опыта, другие API-интерфейсы карт, такие как OpenLayers , поддерживают аналогичные подходы.
Проверьте, перекрываются ли многоугольники
Томас Т высказал свое мнение в своем ответ , что существуют семейства связанных предикатов, которые можно использовать для решения этого и связанных запросов.Если вы буквально ищете перекрытия и другие теоретические операции над множествами (объединение, пересечение, разность множеств) в двух измерениях, вы можете использовать General Polygon Clipper
Возможно, вам также следует рассмотретьчуть более общая проблема, когда два многоугольника не перекрываются или не разделяют вершину, когда должны.Вы можете использовать сумму Минковского, чтобы расширить (увеличить) двумерные и трехмерные многоугольники, чтобы избежать таких проблем. Библиотека алгоритмов вычислительной геометрии имеет надежные реализации этих алгоритмов.
Я думаю, что более вероятно, что вы действительно ищете программное обеспечение, которое может выполнять сварку по вершинам, книгу Кристера Эриксона Обнаружение столкновений в режиме реального времени включает обширное и очень удобочитаемое описание основ в этой области, а также по связанным с этим вопросам замыкания краев, обнаружения трещин, Т-образных соединений и многого другого.Однако, хотя для этой книги включены фрагменты кода, я не знаю ни одной готовой библиотеки, которая бы решала эти проблемы, в частности, не дается полная реализация чего-либо, кроме базовой вершинной сварки.
Очевидно, что все 3D-пакеты (blender, maya, max, rhino) все включают встроенное программное обеспечение и инструменты для решения этой проблемы.
Группировка полигонов на основе вершин
Из прошлого опыта это оказалосьбыть одной из самых трудоемких частей разработки программного обеспечения для решения проблем в этой области.Требуется разумное понимание теории графов и алгоритмов для пересечения границ.Стоит полагаться на твердую геометрию или библиотеку графиков, чтобы сделать тяжелую работу за вас.В прошлом я имел успех с igraph .
Свяжите обновленные полигоны обратно с оригиналами.
Опять из прошлого опыта,это всего лишь случай тщательной бухгалтерии и очень тщательного проектирования ваших классов мешков.Я хотел бы дать больше советов, но даже потратив на это большую часть последних шести месяцев, я все еще пытаюсь найти «хороший» способ сделать это.
ДругоеКомментарии
Если вы взаимодействуете с пользователями, я настоятельно рекомендую по возможности избегать этой проблемы с помощью редактора, который «привязывается», округляя все введенные пользователем точки в сетку. Мы надеемся, что это значительно сократит объем работы, которую вы должны выполнить.