Calcular unión de dos formas arbitrarias

Estoy trabajando en una aplicación, necesito poder combinar dos formas superpuestas arbitrarias tal como las dibujó el usuario. Esta sería una operación de la Unión en las dos formas. La forma resultante sería la silueta de las dos formas superpuestas.Calcular unión de dos formas arbitrarias

Las formas se almacenan como una secuencia de puntos en el sentido de las agujas del reloj.

Idealmente me gustaría un algoritmo que tendrá dos matrices de puntos (x, y) y devolver una única matriz de la forma resultante.

He estado leyendo Wikipedia en Boolean operations on polygons que menciona el Sweep line algorithm pero no puedo establecer el vínculo entre esto y mi objetivo, por desgracia, no soy matemático.

estoy desarrollando la aplicación en ActionScript 3, pero estoy familiarizado con C#, Java y puedo elegir mi camino a través de C y C++.

Fuente

2010-01-26 Greg B

Implementar operaciones booleanas correctamente no es trivial; Afortunadamente, hay bibliotecas que ya implementan esta funcionalidad.

¿Qué idioma estás usando? Si se trata de C++, eche un vistazo a CGAL, la Biblioteca de algoritmos de geometría computacional.

Fuente

2010-01-26 14:48:47

Gracias, estoy poniendo en práctica en AS3, pero familiarizado con C#, Java –

Ah ... bueno, no estoy seguro si el código fuente de CGAL es tan divertido de separar y portuar, ya que expresa sus algoritmos de una manera bastante genérica, modelado según el STL (IIRC, ha pasado un tiempo). Tal vez sea mejor que transfiera una de las bibliotecas más específicas vinculadas al pie de la página de Wikipedia. Alternativamente, ¿puede salirse con la simple representación de ambos polígonos en un mapa de bits y luego realizar las operaciones booleanas en eso? –

Encontré este puerto (parcial) AS3 del puerto Java de GPC http://code.google.com/p/gpcas/ que admite operaciones de UNIÓN. Gracias por tu contribución. –

Dadas dos listas de puntos (A y B)
- [1] para cada línea en A no se intersectan una línea en B
-.- [2] Si no hay (más) líneas se cruzan, hay sin superposición
-.- [3] si una línea en (A) intersecta una línea en B entonces
-.-.- [4] agregue el punto de intersección en la salida
-.-.- [5] la línea siguiente de A se cruza B
-.-.-.- [6] si no, agregue esto a la salida (está dentro de B) vaya a 5
-.-.-.- [7] si es así, agregue la intersección a las listas de salida y cambio A & B Goto 2

también ver Intersection Point Of Two Lines. No voy a escribir el código lo siento :)

Fuente

2010-01-26 15:07:04

+1: Suena como un enfoque decente para mí –

gracias Jon ... también debería decir "agregar lógica para evitar el bucle infinito" –

Cuidado: este problema no es tan fácil como crees. Algo de reflexión: una línea (o "borde") en A puede intersectar más de un borde en B. Los dos polígonos originales pueden ser disjuntos; o A puede estar completamente dentro de B; o B puede estar completamente dentro de A (aunque estos tres casos tienen el mismo aspecto si simplemente observa las intersecciones entre líneas). Los polígonos no necesitan ser convexos, y la unión de dos polígonos no convexos puede tener agujeros. Y así sucesivamente ... la geometría computacional es notoria por tener todo tipo de casos especiales en los que no se piensa al principio. –

¿Funcionaría this algorithm para usted?

Fuente

2010-01-26 15:10:04

+1 Me gustaría darle una oportunidad primero tbh! –

Este algoritmo calcula la intersección; Greg B está buscando la unión. Además, este algoritmo solo funciona cuando ambos polígonos, así como su intersección son convexos; Greg B habla de "formas arbitrarias", así que supongo que también quiere poder manejar polígonos no convexos. –

Fair point Martin. Había asumido que eran formas convexas y estaba sugiriendo ese algoritmo como punto de partida para encontrar las dos intersecciones. –

¿Qué tal:

escoger el punto más a la izquierda de las dos formas. Llame a esa Forma A y conviértala en la forma actual.
Enrolle en sentido horario a lo largo de la forma actual hasta el siguiente punto y verifique si una o más líneas se cruzan.
- Si alguna línea DO se intersecta, encuentre el primer punto de intersección y agréguelo a su nueva forma. Cambie a enrollamiento a lo largo de la otra forma.
- Si no se cruzan líneas, avance al siguiente punto de la forma A y añádalo como el punto en su nueva forma. Continúa enrollando a lo largo de la forma actual.
Repita el paso 2.

Creo que si sigue serpenteando por lo que es la forma actual, en busca de las intersecciones, que debe hacer lo que quiera. Creo que también debería hacer frente a las formas cóncavas ...

Estoy seguro de que hay muchas optimizaciones que puede agregar una vez que tenga las funciones básicas en funcionamiento.

Fuente

2010-01-26 17:22:13