algorithm - saber - determinar si un punto se encuentra dentro de una forma arbitraria?
como saber si un punto pertenece a una recta r3 (3)
Dadas las coordenadas de un punto, ¿cómo puedo determinar si está dentro de una forma arbitraria?
La forma está definida por una serie de puntos, no sé dónde está "cerrada" la forma, la parte que realmente necesito ayuda es averiguar dónde está cerrada la forma.
Aquí hay una imagen para ilustrar lo que quiero decir un poco mejor:
La forma más fácil de hacerlo es lanzar un rayo desde ese punto y contar cuántas veces cruza el límite. Si es impar, el punto está dentro, incluso el punto está fuera.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Tenga en cuenta que esto solo funciona para múltiples formas.
Si desea determinar si un punto P está o no en una forma arbitraria, simplemente ejecutaría un relleno de inundación comenzando en P. Si su relleno de inundación deja un cuadro de límite predeterminado, está fuera de la forma. De lo contrario, si su relleno de inundación termina, entonces está dentro de la forma :)
Creo que este algoritmo es O (N ^ 2) donde N es el número de puntos, ya que el área máxima es proporcional a N ^ 2.
Wikipedia: Inundación
En realidad, si le dan una serie de puntos, puede verificar la proximidad de la forma de la siguiente manera:
Considere los pares de puntos P[i] y P[i+1] dados en la matriz; forman un segmento del borde de su forma. Lo que debe verificar es si existen dos segmentos de este tipo que se intersecan, los cuales se pueden verificar en tiempo O(N^2) (solo con la verificación de todos los pares posibles de dichos segmentos). Si existe una intersección, eso significa que su forma está cerrada.
Nota: debe estar atento para no olvidar verificar el segmento P[0],P[n-1] (es decir, los puntos primero y último de la matriz).