Distribuir un Número Fijo de Puntos "Uniforme" en el interior de un Polígono

Question

Tengo un polígono en 2D (definido por una serie de Vértices $V$ con coordenadas). El polígono puede ser convexo o cóncavo. He a $n$ número de revisión de puntos que puedo poner en el interior del polígono.

La pregunta es, ¿cómo puedo distribuir la solución de puntos uniformemente como sea posible dentro del polígono?

La motivación para esta pregunta es que quiero crear una malla generador y quiero que todos los elementos triangulares $E$ ( que es definido por una lista de vértices $V$) se ven bien con no demasiado grandes o demasiado pequeños ángulos. Con el fin de controlar la granularidad de la malla estoy pensando en usar el número de puntos fijos $n$ como el control de parámetro. Los puntos fijos se utilizan para controlar el vértice de la triangular elementos.

¿Hay algún algoritmo para esto?

Answer 1

Simplemente colocar puntos en el polígono de acuerdo a una distribución uniforme no, por desgracia, generar soluciones uniformes: con una muy alta probabilidad de que habrá grandes lagunas y apretados racimos.

La obtención de una muy uniforme patrón dentro de una arbitraria (convexo) polígono es un problema difícil de resolver; soluciones exactas, sólo son conocidos para el especial de polígonos y muy pequeñas cantidades de puntos. Como el número de puntos de $n$ crece, tienden a caer en un patrón hexagonal. Sin embargo, como verdaderos cristales, estos patrones pueden presentar fallas y fracturas impuestas por el polígono de la frontera. Como un rápido y sucio solución se puede estimar el espaciamiento promedio dividiendo el polígono del área por $n$ y resolviendo las dimensiones de un hexágono de la zona, la creación de una malla hexagonal de esas dimensiones, y la realización de algunas juicio superposiciones de que la malla (la traducción es un poco en cada ensayo) para encontrar algo que funcione bien. Usted es probable que se ejecute en problemas en los lugares sólo dentro del polígono de la frontera, aunque.

Una forma práctica de encontrar soluciones que realmente funcionan es con espacial de recocido simulado. A pesar de que un uso intensivo de recursos informáticos y puramente aproximado de enfoque, en la práctica se pueden obtener soluciones razonables para la aplicación deseada en un tiempo extremadamente corto (miles de iteraciones en lugar de cientos de miles).

Answer 2

La idea más simple es generar una secuencia de puntos de $(X_i,Y_i)$ donde $X_i,Y_i$ son independientes uniforme de variables aleatorias, en un rectángulo que contiene el polígono (el mínimo rectángulo de delimitación del polígono). A continuación, basta con colocar los puntos que quedan fuera del polígono. Continúe hasta que usted consigue $n$ unrejected puntos.

Como es de esperar, este problema ha sido considerado antes por muchas personas. Usted puede encontrar esta uno muy útil. La pregunta básica es ¿cómo de rápido/simple desea generar el $n$ puntos. El método que he descrito es la más simple, pero puede llevar mucho tiempo.

EDIT: Para añadir algo de matemáticas de este post, nos vamos a justificar el rechazo del método y la triangulación de enfoques (a pesar de que puede parecer intuitivamente claro).

El rechazo del método de enfoque. Supongamos que $(X,Y)$ es distribuido uniformemente en un rectángulo $R$ la delimitación de la poligonal $M$, $S$ es arbitraria plaza contenidas en $M$. A continuación, $$ {\rm P}((X,Y) \in S |(X,Y) \in M) = \frac{{{\rm P}((X,Y) \in S )}}{{{\rm P}((X,Y) \in M)}} = \frac{{{\rm área}(S) /{\rm área}(R)}}{{{\rm área}(M)/{\rm área}(R)}} = \frac{{\rm área}(S) }{{{\rm área}(M)}}. $$ Por lo tanto, dado que $(X,Y) \in M$, $(X,Y)$ se distribuyen de manera uniforme en $M$.

La triangulación de enfoque. Supongamos que el polígono $M$ se divide en triángulos $T_1,\ldots,T_m$, y establecer $p_i = {\rm area} (T_i)/ {\rm area}(M)$. Supongamos que ${\rm P}((X,Y) \in T_i)=p_i$ y que, dado $(X,Y) \in T_i$, $(X,Y)$ se distribuyen de manera uniforme en $T_i$. Ahora, para fijo $k$, vamos a $S \subset M$ arbitrarios en la plaza de contenidos en $T_k$ (creo que de forma arbitraria cuadrados pequeños). A continuación, $$ {\rm P}((X,Y) \in S) = \sum\limits_{i = 1}^m {{\rm P}((X,Y) \in S|(X,Y) \in T_i )p_i } = {\rm P}((X,Y) \in S|(X,Y) \in T_k )p_k. $$ Puesto que, dado que $(X,Y) \in T_k$, $(X,Y)$ se distribuyen de manera uniforme en $T_k$, tenemos $$ {\rm P}((X,Y) \in S|(X,Y) \in T_k ) = \frac{{{\rm área}(S)}}{{{\rm área}(T_k )}}. $$ Por lo tanto, $$ {\rm P}((X,Y) \in S) = \frac{{{\rm área}(S)}}{{{\rm área}(T_k )}}\frac{{{\rm área}(T_k )}}{{{\rm área}(M)}} = \frac{{{\rm área}(S)}}{{{\rm área}(M)}}. $$ Llegamos a la conclusión de que $(X,Y)$ es distribuido uniformemente en $M$.

Answer 3

Como whuber menciona, utilizando una distribución uniforme para el muestreo se traducirá en "clumpiness" de los puntos. Una manera de cuantificar este "clumpiness" es a través de una medida de la discrepancia. Hay numerosos baja discrepancia secuencias de allí. También puede que desee ver en la de Poisson el método de disco.