Calcular la unión de dos formas arbitrarias

Question

Estoy trabajando en una aplicación, tengo que ser capaz de combinar la superposición de dos formas arbitrarias como dibujado por el usuario. Esto 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.

Las formas se almacenan como una secuencia de puntos de una manera hacia la derecha.

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 en Wikipedia booleana operaciones en polígonos que menciona la línea de barrido algoritmo pero no puede hacer el enlace entre este y mi objetivo, por desgracia no soy un 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 ++.

Answer 1

La implementación de operaciones booleanas correctamente no es trivial; Afortunadamente, hay bibliotecas que ya implementar esta funcionalidad.

¿Qué idioma se utiliza? Si se trata de C ++, echar un vistazo a CGAL , los algoritmos Biblioteca Geometría Computacional.

Answer 2

Dadas dos listas de puntos (A y B)
  - [1] para cada línea en A hace que se cruzan en una línea B Opiniones     -.- [2] si no hay (más) líneas se cruzan, no hay solapamiento
    -.- [3] si una línea en (A) se cruza una línea en B, entonces
     -.-.- [4] añadir el punto de intersección en la salida
     -.-.- [5] hace la siguiente línea de la A se cruzan B Opiniones        -.-.-.- [6] si no, añadir esto a la salida (que está dentro B) Goto 5
       -.-.-.- [7] si es así, añadir el intersecan a listas de salida y el interruptor A & B Goto 2

También ver Punto de intersección de dos líneas . No voy a escribir el código siento:)

Answer 3

GPC .

Answer 4

este algoritmo trabajo para usted?

Answer 5

¿Qué hay de:

1. Elige el más a la izquierda punto de las dos formas. Llama a ese Forma A y que sea la forma actual.
2. las agujas del reloj del viento a lo largo de la forma actual al siguiente punto y comprobar para ver si una o más líneas se cruzan.
   • Si todas las líneas intersectan, encontrar el primer punto de intersección y añadir que a su nueva forma. Cambiar a bobinado a lo largo de la otra forma.
   • Si no hay líneas de intersección pasar al siguiente punto de la forma A y añadir que a medida que el punto en su nueva forma. Continuar bobinado a lo largo de la forma actual.
3. 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 debería hacer frente a las formas cóncavas, así ...

Estoy seguro de que hay una gran cantidad de optimizaciones se puede añadir una vez que tienes los conceptos básicos de trabajo.

Answer 6

Parece que hay también una API de JavaScript:

https://github.com/bjornharrtell/jsts/

que parece poner en práctica el STC estándar y tiene varias implementaciones diferentes personas:

http://tsusiatsoftware.net/jts/jts-links.html#ports

todos ellos deben ser capaces de realizar la unión, etc:

http://tsusiatsoftware.net/jts/JTSUser/contents.html

Pero csg.js es el proyecto más impresionante OMI

https://github.com/evanw/csg.js