Pregunta ¿Cómo particiono un cuadro de límite orientado?


Estoy escribiendo un código que construirá un árbol orientado de recuadro delimitador (obb) para un polígono (no necesariamente convexo) en 2 dimensiones.

Hasta ahora, soy capaz de encontrar el objeto de área mínima de un polígono encontrando su casco convexo y utilizando pinzas giratorias en el casco.

La imagen de abajo es un ejemplo de esto. El polígono de color amarillo con líneas rojas y puntos rojos representa el polígono original. El casco convexo se muestra en azul con líneas negras y el obb se muestra como líneas violetas.

(Editar) Según lo solicitado: Versión interactiva - probado solo en cromo

Ahora quiero extender mi código para construir un árbol OBB, en lugar de solo un OBB. Esto significa que tengo que cortar el polígono y calcular nuevos OBB para cada mitad del polígono.

La forma recomendada de hacer esto parece ser cortar el polígono cortando el OBB a la mitad. Pero si corto el objeto por el medio en cualquiera de sus ejes, parece que tendría que crear nuevos vértices en el polígono (de lo contrario, ¿cómo puedo encontrar el casco convexo de esa partición?).

  1. ¿Hay alguna manera de evitar agregar vértices como este?
  2. Si no, ¿cuál es la forma más fácil de hacerlo (con respecto a la dificultad de implementación)? ¿Cuál es la forma más eficiente en tiempo de ejecución?

5
2018-05-28 21:28


origen


Respuestas:


Aquí hay un ejemplo de un polígono cóncavo para el que queremos crear un árbol OBB:

Para dividirlo en un nuevo conjunto de polígonos cóncavos, podemos simplemente cortar nuestro polígono actual cortando el cuadro delimitador por la mitad y agregando nuevos vértices de "intersección" según corresponda:

:

Esto se puede hacer en tiempo O (vértices) porque simplemente podemos iterar a través de todos los bordes y agregar un vértice de intersección si el borde cruza la línea de división roja.

El polígono se puede dividir en términos de estos vértices de intersección para obtener un nuevo conjunto de polígonos más pequeños (pero posiblemente cóncavos). Habrá al menos dos de esos polígonos (uno por cada lado de la línea roja) pero puede haber más. En la siguiente imagen, los nuevos polígonos han sido coloreados para enfatizar:

El cálculo recursivo de los recuadros delimitadores orientados para estos polígonos más pequeños da el resultado deseado. Por ejemplo, aquí están los cuadros de la profundidad de recursión 2:

enter image description here

¡Espero que esto sea lo suficientemente claro para ayudar a alguien que está luchando de la misma manera que yo!


4
2018-05-29 05:08



No estoy realmente seguro de que esto es lo que necesita sin más contexto, pero aquí va ...

Subdividir un polígono cóncavo en un conjunto de polígonos convexos

En mi comentario anterior sugerí subdividir recursivamente el polígono cóncavo para obtener un conjunto de polígonos convexos. Un enfoque (común) es el siguiente:

  1. Si el polígono es convexo, deténgase. (agregar el polígono a una matriz, supongo)
  2. Seleccione un borde sin marcar del polígono. Marcar el borde
  3. Divide el polígono a través del borde (en realidad: la línea infinita que coincide con el borde).
  4. Repita recursivamente este algoritmo para ambos polígonos de resultados (si no está vacío).

Nota:Así es exactamente cómo se construye un árbol BSP. Excepto en el algoritmo anterior, no estamos construyendo nodos de árbol y almacenando polígonos en ellos. Tal vez una solución solo para BSP sería también una solución para su problema (en lugar de utilizar OBB).


3
2018-05-28 23:30