Operaciones booleanas en polígonos rectangulares

Question

¡Avast hay otros programadores!

I tienen el siguiente problema:

Tengo dos rectángulos superpuestos como se muestra en la imagen siguiente.

Quiero averiguar el polígono formado por punto ABCDEF.

Descripción navideña alternativa: El cortador de galletas rojas está cortando un poco de la galleta negra. Quiero calcular la galleta negra.

Cada rectángulo es una estructura de datos con 4 vértices en 2d.

¿Cuál es el mejor algoritmo para lograr esto?

Answer 1

Este es un caso especial de 2D en general recorte polígono. Un buen lugar para comenzar es el algoritmo de Weiler-Atherton. Wikipedia has a summary y links to the original paper. El algoritmo parece coincidir bastante bien con la estructura de datos que describió.

Tenga en cuenta que es muy posible que termine con un rectángulo con un agujero (si el rojo está completamente dentro del negro) o incluso dos rectángulos (por ejemplo, si el rojo es más alto y delgado que el negro) Si está seguro de que solo hay una esquina del rectángulo rojo dentro del negro, entonces la solución debería ser mucho más simple.

Answer 2

constructive solid geometry

Answer 3

he encontrado algunas cosas aquí puede ser que utilice:

http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html

realidad He descargado la fuente CGAL antes de que incluso envió esta pregunta, pero creo que voy a mirar más de cerca en él.

Answer 4

¿Cuán precisas son las coordenadas? Si los rectángulos son bastante pequeños, el enfoque más fácil podría ser simplemente pintarlos en un lienzo, primero el rectángulo negro, seguido por el rojo. Los píxeles negros restantes en el lienzo son el polígono que queda.

Otro enfoque es dividir la cuadrícula de coordenadas en un grupo de rectángulos basados ​​en todos los lados de los rectángulos (sin contar rectángulos sin límites, tiene hasta 9 rectángulos generados si tiene dos rectángulos originales). Luego solo prueba un punto representativo de cada uno de estos rectángulos para la membresía en los polígonos particulares para determinar qué rectángulos están dentro y cuáles están fuera.