Dadas las coordenadas de un punto, ¿cómo puedo determinar si está dentro de una forma arbitraria?determinar si un punto se encuentra dentro de una forma arbitraria?
La forma está definida por una matriz 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í está una imagen para ilustrar lo que quiero decir un poco mejor:
manera más fácil de hacerlo es arrojado un rayo desde ese punto y contar cuántas veces se cruza el límite. Si es impar, el punto está adentro, incluso el punto está afuera.
Wiki: http://en.wikipedia.org/wiki/Point_in_polygon
Tenga en cuenta que esto sólo funciona para múltiples formas.
Fantástico. ¡Gracias por recordarme esto! – ambrus
En realidad, si se le da una matriz de puntos, se puede comprobar la cercanía de la forma de la siguiente manera:
Considere pares de puntos P[i] y P[i+1] dadas en la matriz - forman algún segmento del borde de su forma . Lo que necesita comprobar es si existen dos segmentos de ese tipo que se cruzan, que se pueden verificar en O(N^2) tiempo (simplemente verificando todos los pares posibles de dichos segmentos). Si existe una intersección, eso significa que su forma está cerrada.
Nota: debe prestar atención para no olvidar comprobar el segmento P[0],P[n-1] (es decir, el primero y el último punto de la matriz).
¿Cuándo se unirán p [i], p [i + 1] yp [j], p [j + 1]? Creo que diría si la forma es un polígono simple o un polígono complejo. Además, no respondió la pregunta original sobre cómo encontrar si el punto yace en el polígono. –
@logic_max: Bueno, respondí la parte de la pregunta sobre cómo verificar si la forma está cerrada y, de acuerdo con la declaración del problema, no debe ser necesariamente un polígono, puede ser una polilínea arbitraria. La presencia de cualquier intersección de p [i], p [i + 1] yp [j], p [j + 1] solo nos dirá que la forma tiene una parte cerrada. ¿Qué pasa con el punto interno? La respuesta de Mikola es correcta al respecto. –
Eso no funciona. ¿Qué sucede si toma un polígono cerrado y luego le agrega un borde colgante? De hecho, no estoy seguro exactamente de qué pruebas y cómo se relaciona con la pregunta. – Mikola
Si desea determinar si un punto P tiene o no forma arbitraria, simplemente ejecutaría un relleno de inundación empezando por P. Si su relleno de inundación deja un recuadro delimitador predeterminado, se encuentra 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: Flood Fill
la forma no está abierto ... Es sólo que no sé dónde está cerrado. – gibo
Tiene que indicar cómo se define la forma mediante una matriz de puntos. Si quiere decir que la matriz de puntos es el conjunto de puntos dentro de la forma, entonces la pregunta es trivial. – sawa
La imagen en mi publicación podría explicarlo un poco mejor ... Conozco los puntos a lo largo de la línea azul, pero no sé dónde está la cruz cerrando la forma – gibo