Dado n 2D puntos y un punto especial de p, cuál sería la mejor manera de encontrar cuantas veces p está dentro de entre los triángulos de #% de #% % formados por los números puntos.
Respuesta
¿Demasiados anuncios?
JiminyCricket
Puntos
143
He aquí un algoritmo en $O(n\log n)$ tiempo y $O(n)$ espacio; dudo que usted puede hacer mejor que eso.
Voy a asumir la posición general, es decir, $\mathbb p$ no está en la línea a través de cualquiera de las dos de la $n$ puntos. En la siguiente, los ángulos se normalizan en un intervalo de longitud de $2\pi$, dicen, $[0,2\pi)$, y las diferencias entre ellos son normalizados $(-\pi,\pi)$ sumando o restando $2\pi$ si es necesario.
Calcular y el orden de los ángulos bajo los cuales el $n$ aparecen los puntos de $\mathbb p$; esto se lleva a $O(n\log n)$ del tiempo. El número de triángulos que contienen $\mathbb p$ es de un tercio del número de ordenadas triples de ángulos tales que la diferencia entre los ángulos es positivo para los tres pares de (cíclicamente) sucesivas ángulos. (No puede ser cero o $\pi$ debido a la asunción de la posición general.)
Para contar el número de triples, asignar índices para los ángulos de acuerdo a su orden, y para cada uno de los ángulos $\alpha_i$ con índice de $i$ determinar el número de $m_i$ de los índices de $j$ tal que $\alpha_j-\alpha_i$ es positivo. Esto se puede hacer en $O(n\log n)$ tiempo al realizar una búsqueda binaria para el opuesto al ángulo $\alpha_i+\pi$.
Ahora recorrer $i$, contando el número de ordenadas triples con primer elemento $\alpha_i$ que cumplir la condición anterior. Por cada segundo elemento $\alpha_j$ positivos $\alpha_j-\alpha_i$, el número de tripletas es el número de tercera elementos $\alpha_k$ tanto $\alpha_k-\alpha_j$ $\alpha_i-\alpha_k$ son positivos. Esta es la superposición entre las $m_j$ ángulos para que $\alpha_k-\alpha_j$ es positivo y el $n-m_i-1$ ángulos para que $\alpha_k-\alpha_i$ es negativo. Esto puede ser escrito como $m_j+(n-m_i-1)-(n-d_{ij}-1)=m_j+d_{ij}-m_i$ donde $d_{ij}$ es el ciclo de distancia de$i$$j$. (El diagrama circular que contiene los tres términos pueden ayudar a la comprensión.)
El plazo $m_i$ es independiente de $j$, por ello la suma es $j$ da $m_i^2$. El plazo $d_{ij}$ es también fácilmente sumando $j$; la suma es $m_i(m_i+1)/2$, por lo que estos términos, junto contribuir $-m_i(m_i-1)/2$. La suma de $m_j$ puede ser calculado en tiempo constante por siempre puede calcular previamente las sumas $\sum_{j<i}m_j$; luego la suma de $m_j$ $\alpha_j-\alpha_i$ positivo es sólo el cíclica de la diferencia entre dos cantidades, una de ellas con el índice de $i$ y el otro con el "contrario" índice de la que ya se determinó mediante la búsqueda binaria para calcular el $m_i$ por encima.
Me he saltado algunos de los detalles técnicos, pero espero que sea claro, cómo todos los pasos pueden llevarse a cabo en $O(n\log n)$ del tiempo. (Claramente las estructuras de datos utilizadas sólo el uso de $O(n)$ de espacio.)
[Modificar:] hubo un error en el cálculo original. Por cierto, el cálculo correcto es ligeramente más sencillo. También nos permite derivar de forma inmediata el número de triángulos en el caso de un regular $n$-gon (con $n$ extraño que la posición general): En este caso, todos los $m_i$ son iguales, por lo $m_j$ $m_i$ cancelar, y el resultado es: $1/3$ de la suma de $d_{ij}$$i$$j$, $nm(m+1)/2$. Aquí $m$ es el valor común de la $m_i$,$(n-1)/2$; el resultado final es $n(n^2-1)/24$ triángulos.
