Esto es bastante largo, solo porque la pregunta es muy grande. Intenté agrupar mis comentarios según sus viñetas.
Componentes para dibujar polígonos
Mi conjetura es que usted tendrá éxito limitado sin proporcionar más información - un componente para dibujar polígonos será mucho acoplado al paradigma de la lengua y la interfaz de usuario que está utilizando para el resto de su proyecto, es decir. el código para un componente web se verá muy diferente a un componente nativo.
Quizás una alternativa sea separar este elemento del proceso del resto de lo que estás tratando de hacer. Hay algunos editores preexistentes absolutamente fantásticos que puede usar para crear polígonos 2D y 3D.
Inkscape es un ejemplo de un editor de gráficos vectoriales que hace que sea fácil ingresar polígonos en 2d, y tiene la ventaja de producir salida SVG, que es razonablemente fácil de analizar.
En tres dimensiones Blender es un editor de código abierto que se puede utilizar para generar geometrías arbitrarias que se pueden exportar a varios formatos.
Si puede usar una API de google-maps (posiblemente en un control nativo de representación de HTML) y está interesado en agregar puntos espaciales en una superposición de mapa, puede estar interesado en click-to-draw polygon question on stackoverflow relacionado.Según la experiencia anterior, otras API de mapas como OpenLayers admiten enfoques similares.
Comprobar si los polígonos se solapan
Thomas T hizo el momento de su answer, que hay familias de predicados relacionados que se pueden utilizar para hacer frente a este y otros consultas. Si está literalmente buscando solapamientos y otras operaciones teóricas (unión, intersección, diferencia de ajuste) en dos dimensiones, puede usar el General Polygon Clipper
. También puede ser necesario considerar el problema un poco más genérico cuando dos polígonos que no funcionan t se superponen o comparten un vértice cuando deberían. Puede usar una suma de Minkowski para dilatar (ampliar) polígonos de dos y tres dimensiones para evitar tales problemas. El Computational Geometry Algorithms Library tiene implementaciones robustas de estos algoritmos.
Creo que es más probable que realmente esté buscando un programa que pueda realizar la soldadura de vértices, el libro de Christer Ericson Real-time Collision Detection incluye una descripción extensa y muy legible de los conceptos básicos en este campo, y también snapping, detección de grietas, uniones en T y más. Sin embargo, aunque se incluyen fragmentos de código para ese libro, no conozco ninguna biblioteca preparada que aborde estos problemas, en particular, no se ofrece una implementación completa para nada más allá de la soldadura básica de vértices.
Obviamente, todos los paquetes 3D (blender, maya, max, rhino) incluyen software y herramientas integradas para resolver este problema.
polígonos Grupo de acuerdo con vértices
de la experiencia pasada, esto resultó ser uno de los que más tiempo consume partes de desarrollo de software para resolver problemas en esta área. Requiere una comprensión razonable de la teoría de los gráficos y los algoritmos para atravesar los límites. Vale la pena confiar en una sólida biblioteca de geometría o gráficos para hacer el trabajo pesado por usted. En el pasado he tenido éxito con igraph.
Vincular los polígonos actualizados a los originales.
De nuevo, por experiencia, este es solo un caso de contabilidad cuidadosa, y un diseño muy cuidadoso de sus clases de malla por adelantado. Me gustaría dar más consejos, pero incluso después de haber gastado una gran parte de los últimos seis meses en esto, todavía estoy luchando por encontrar una "buena" manera de hacerlo.
Otros Comentarios
Si va a interactuar con los usuarios, lo recomiendo encarecidamente evitar este problema cuando sea posible mediante el uso de un editor que "encaje", redondeando todos los usuarios introducen puntos en una rejilla. Esto con suerte reducirá significativamente la cantidad de trabajo que tienes que hacer.
¿Los polígonos están en dos o tres dimensiones? –