algorithm - pentagono - poligonos concavos y convexos ejercicios
Encajando un polígono convexo en otro polígono (2)
Motivación. Si se preguntara si un disco B de cierto radio puede encajar en un polígono P, entonces hay un método estándar en geometría computacional : compruebe si el círculo máximo inscrito tiene un radio no menor; ver esta respuesta de stackoverflow :
El algoritmo anterior para calcular el círculo máximo inscrito es bastante "simple": calcule el denominado Diagrama de Voronoi Generalizado y tome el nodo Voronoi con el radio de mayor separación. (Esto es solo una motivación, solo sigue leyendo por un minuto).
En tu caso tu Forma 2 no es una bola; Bueno, no es una bola euclidiana, para ser precisos. Pero, en realidad, su Forma 2, como un polígono convexo B, podría definir una función de distancia convexa y calcular el diagrama de Voronoi bajo esta función de distancia poliédrica . Pero este es un fondo más teórico y tal vez no sea algo que quiera implementar para el código de producción.
Esos diagramas de Voronoi están fuertemente relacionados con el cálculo de curvas de desviación, por ejemplo, para la planificación de trayectorias de herramientas en el mecanizado NC. Vea este artículo del blog para algunas discusiones y la siguiente figura:
Una bola B de radio r encaja en la forma P si y solo si hay una curva de desplazamiento en la distancia r. (En realidad, se obtiene el conjunto de todos los centros válidos, es decir, aquellos dentro de la curva de desplazamiento en el radio r). Y esas curvas de desplazamiento pueden describirse matemáticamente como una diferencia de Minkowski , como se describe en el artículo del blog.
La diferencia de Minkowski. Así que ahora podemos volver a su problema original. ¿Encaja un polígono convexo B dentro de un polígono P? Lo hace si y solo si la diferencia de Minkowski (PB) es un conjunto no vacío; cualquier centro fuera de (PB) funciona como ejemplo.
Algunos detalles más basados en la figura anterior: denotemos por -B = {-v: v en B} la forma B después de la reflexión del punto. (Elija el origen en el lugar que desee; lo denoté con la cruz pequeña con ''o'' para el origen). Ahora piense en -B como la forma de una pluma (azul) y mueva la pluma (en realidad la cruz) a lo largo del límite de P. Obtienes la zona gris. (Esta es la suma de Minkowski del límite de P con -B.) Elimine el área gris de P y obtendrá la diferencia de Minkowski PB. Elija cualquier punto dentro de PB y coloque una copia de B allí; encajará dentro de P. Coloqué algunas copias (naranja) para ti.
Implementación. Puede construir el área gris considerando cada segmento s de P individualmente y deslizar -B a lo largo de él. Más precisamente, coloca una copia de -B en cada punto final de s y encuentra las tangentes de las dos copias de -B que forman el límite del área gris:
Tome las soluciones por segmento y calcule la unión en todos los segmentos de P. Luego reste esta unión de P. Eche un vistazo a Clipper para obtener una biblioteca de código abierto que puede hacer eso por usted.
Lo que obtienes no es solo la respuesta booleana si B se ajusta a P, sino el conjunto de todos los centros válidos para B en forma de un conjunto de polígonos. Quizás esto también sea interesante para su aplicación.
Si también permites las rotaciones de B, entonces el problema se vuelve mucho más complejo, creo. Tal vez puedas trabajar con cierta discretización de los ángulos de rotación. Tal vez encuentre alguna solución en el campo de la planificación de movimiento de robots resp. Relacionado con el problema del motor del piano en la geometría computacional.
Estoy buscando un algoritmo donde pueda verificar si un polígono convexo (forma 1) encaja en otro polígono (forma 2).
Mi primera investigación me llevó a "Empaquetar formas irregulares". Esto es en mi opinión un poco excesivo. Solo tengo un contenedor y un objeto.
La forma 1 es normalmente un polígono convexo. La forma 2 puede ser convexa o cóncava.
Mi aplicación: tengo un escáner láser 3D para medir registros, lo que me da la forma 2. También tengo diferentes perfiles de corte desde los cuales considero el casco convexo, dando forma 1.
Ahora quiero comprobar si un perfil de corte se ajusta a mi perfil de láser.
Requisitos: debe tener todas las coordenadas de vértice de ambos polígonos convexos (PolygonA, PolygonB).
Paso 1 : Ponga todos los puntos de ambos polígonos convexos en un conjunto.
Paso 2: Encuentra el polígono convexo usando grahamscan con un nuevo conjunto de puntos.
Paso 3: Ahora tienes un polígono convexo grande que contendrá ambos polígonos convexos. Eso significa que tienes el vértice del polígono recién creado, llamémoslo PolígonoC.
Etapa 4:
- Ahora verifique si polygonC y PolygonA son iguales con el mismo conjunto de puntos de vértice
- Si es así, significa que PolygonA contiene PolygonB
Si la condición anterior no es verdadera, repita la misma comprobación con PolygonB
Si la condición anterior no es cierta para ninguno de los polígonos, entonces ningún polígono se ajusta a otro polígono.