¿Cómo representar un polígono con agujero(s)?

Question

Suele ser popular trabajar con polígonos con sus vértices ordenados en sentido horario o antihorario en vectores (matrices de 2*1 o 1*2).Sin embargo, ¿cómo enunciar polígonos con huecos en vectores?

Voy a aplicar varios procesos en estos polígonos, por lo que quiero una forma de representación con la que pueda trabajar fácil o eficientemente (es decir, ¿cómo indicar ese tipo de polígonos en mi programa para facilitar mis algoritmos?).

Los polígonos son 2D y estoy programando en MATLAB.

EDITAR 1:voy a calcular gráfico de visibilidad de estos polígonos (con o sin agujeros).

Answer 1

Como han mencionado otros, un polígono con agujeros se puede representar como un límite exterior, más cero o más límites interiores, los cuales no se superponen entre sí*.Si usas distinto de cero número de liquidación Para determinar interior/exterior, asegúrese de especificar sus límites interiores en la dirección opuesta a los límites exteriores (en el sentido contrario a las agujas del reloj para el exterior y en el sentido de las agujas del reloj para el interior, o viceversa) de modo que las integrales de contorno sean cero dentro de los agujeros.

Para su información, este tipo de definición/representación se ha formalizado en la Especificación de características simples de OpenGIS (PDF).

En cuanto a representación:

Probablemente tendría una matriz de celdas de matrices K Nx2, donde el primer elemento de la matriz de celdas es el límite exterior y los elementos restantes (si los hay) en la matriz de celdas son los límites interiores.Usaría una matriz de celdas porque puede que no haya la misma cantidad de puntos en cada límite.

*no superpuesto = excepto en puntos individuales, p.e.un diamante dentro de un cuadrado:

Answer 2

Puede romper un polígono con un agujero en dos formas sin un agujero. Cuando realiza integración de contornos en un plano complejo, puede crear un & "; Cortar &"; desde un borde del polígono que te lleva al borde del hoyo; integrar alrededor de un lado del agujero y la espalda; luego atraviese el otro lado para el segundo polígono. Terminas con dos integrales de ruta a lo largo de cada corte que se cancelan entre sí.

" gráfico de visibilidad " - ¿Es esto para un cálculo del factor de visión de radiación con sombreado? ¿O un algoritmo gráfico de trazado de rayos?

Answer 3

Un polígono, más una lista de agujeros poligonales. Solo asegúrese de que los diversos polígonos no se crucen.

¿Qué planeas hacer con esto?

Answer 4

Parece que cada hoyo es solo un polígono dentro del propio polígono. Tal vez podría almacenar un vector como el que describe para el polígono exterior, luego un vector de más vectores de polígono para los agujeros.

Answer 5

Presumiblemente querrás tener una estructura de árbol si quieres que sea lo más genérico posible (es decir, polígonos con agujeros poligonales que tienen polígonos dentro de ellos con agujeros dentro de eso, ...). Matlab no es muy bueno para representar estructuras de árboles de manera eficiente, pero aquí hay una idea ...

Tener una estructura de matriz de polígonos.

Cada polígono es una estructura con dos campos, 'esquinas' y 'hijos'.

El campo 'esquinas' contiene una matriz de coordenadas (x, y) de las esquinas, a las que se accede como " data {polyIdx} .corners (:, cornerIdx) " ;.

El campo 'hijos' es una estructura de matriz de polígonos.

Aquí hay un ejemplo de algún código para hacer un triángulo con niños falsos que son agujeros (aunque en realidad no son válidos porque probablemente se superpongan:

polygon = struct;
npoints = 3;
polygon.corners = rand(2,npoints);
polygon.children = struct;
nchildren = 5;
for c=1:nchildren
    polygon.children(c).corners = rand(2,npoints);
    polygon.children(c).children = struct;
end

Podría continuar definiendo recursivamente los elementos secundarios que alternan entre crear agujeros y rellenarlos.

Answer 6

¿Qué quiere decir exactamente con " un gráfico de visibilidad " ?

Dos " completo " polígonos, dos estados posibles, ya sea +1 o -1.

Si representa un agujero, tiene uno con el estado +1 y otro con el estado -1, que representa un agujero, lo que da como resultado el estado 0.
Si tienes polígonos superpuestos, terminarás con el estado resultante & Gt; 1. Luego puede calcular los bordes de un nuevo polígono.
Si tiene dos polígonos con agujeros que se cruzan, primero calcule el estado de un nuevo polígono que consiste en bordes exteriores de los dos viejos, luego trate con agujeros.

De todos modos, ... creo que entiendes el principio general.

No tengo idea de cómo hacerlo en matlab, lo usé solo marginalmente hasta ahora, e incluso eso para cosas muy simples.