triangulo saber que punto interior graham geometricos geometrico esta equilatero dentro como algoritmos algoritmo performance graphics collision-detection polygon point-in-polygon

performance - saber - punto interior de un triangulo equilatero



¿Cómo puedo determinar si un punto 2D está dentro de un polígono? (30)

Estoy intentando crear un punto 2D rápido dentro del algoritmo de polígono, para usarlo en pruebas de Polygon.contains(p:Point) por ejemplo, Polygon.contains(p:Point) ). Se agradecerían sugerencias de técnicas efectivas.

Aquí hay una variante de JavaScript de la respuesta de M. Katz basada en el enfoque de Nirg:

function pointIsInPoly(p, polygon) { var isInside = false; var minX = polygon[0].x, maxX = polygon[0].x; var minY = polygon[0].y, maxY = polygon[0].y; for (var n = 1; n < polygon.length; n++) { var q = polygon[n]; minX = Math.min(q.x, minX); maxX = Math.max(q.x, maxX); minY = Math.min(q.y, minY); maxY = Math.max(q.y, maxY); } if (p.x < minX || p.x > maxX || p.y < minY || p.y > maxY) { return false; } var i = 0, j = polygon.length - 1; for (i, j; i < polygon.length; j = i++) { if ( (polygon[i].y > p.y) != (polygon[j].y > p.y) && p.x < (polygon[j].x - polygon[i].x) * (p.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x ) { isInside = !isInside; } } return isInside; }

Aquí hay una versión en C # de la respuesta dada por nirg , que proviene de here . Tenga en cuenta que el uso del código de esa fuente RPI requiere atribución.

Se ha agregado una marca de límite en la parte superior. Sin embargo, como señala James Brown, el código principal es casi tan rápido como la propia casilla delimitador, por lo que la verificación del recuadro delimitador puede ralentizar la operación en general, en el caso de que la mayoría de los puntos que está marcando se encuentren dentro del recuadro delimitador . Por lo tanto, podría dejar el cuadro delimitador marcado o una alternativa sería calcular previamente los cuadros delimitadores de sus polígonos si no cambian de forma con demasiada frecuencia.

public bool IsPointInPolygon( Point p, Point[] polygon ) { double minX = polygon[ 0 ].X; double maxX = polygon[ 0 ].X; double minY = polygon[ 0 ].Y; double maxY = polygon[ 0 ].Y; for ( int i = 1 ; i < polygon.Length ; i++ ) { Point q = polygon[ i ]; minX = Math.Min( q.X, minX ); maxX = Math.Max( q.X, maxX ); minY = Math.Min( q.Y, minY ); maxY = Math.Max( q.Y, maxY ); } if ( p.X < minX || p.X > maxX || p.Y < minY || p.Y > maxY ) { return false; } // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html bool inside = false; for ( int i = 0, j = polygon.Length - 1 ; i < polygon.Length ; j = i++ ) { if ( ( polygon[ i ].Y > p.Y ) != ( polygon[ j ].Y > p.Y ) && p.X < ( polygon[ j ].X - polygon[ i ].X ) * ( p.Y - polygon[ i ].Y ) / ( polygon[ j ].Y - polygon[ i ].Y ) + polygon[ i ].X ) { inside = !inside; } } return inside; }

Calcule la suma orientada de ángulos entre el punto p y cada uno de los vértices del polígono. Si el ángulo orientado total es de 360 ​​grados, el punto está dentro. Si el total es 0, el punto está fuera.

Me gusta más este método porque es más robusto y menos dependiente de la precisión numérica.

Los métodos que calculan la uniformidad del número de intersecciones son limitados porque puede "golpear" un vértice durante el cálculo del número de intersecciones.

EDITAR: Por cierto, este método funciona con polígonos cóncavos y convexos.

EDITAR: Recientemente he encontrado un artículo completo de Wikipedia sobre el tema.

Creo que la siguiente pieza de código es la mejor solución (tomada de here ):

int pnpoly(int nvert, float *vertx, float *verty, float testx, float testy) { int i, j, c = 0; for (i = 0, j = nvert-1; i < nvert; j = i++) { if ( ((verty[i]>testy) != (verty[j]>testy)) && (testx < (vertx[j]-vertx[i]) * (testy-verty[i]) / (verty[j]-verty[i]) + vertx[i]) ) c = !c; } return c; }

Argumentos

  • nvert : Número de vértices en el polígono. Ya sea para repetir el primer vértice al final se ha discutido en el artículo mencionado anteriormente.
  • vertx, verty : Arreglos que contienen las coordenadas x e y de los vértices del polígono.
  • testx, testy : coordenadas X e Y del punto de prueba.

Es corto y eficiente, y funciona tanto para polígonos convexos como cóncavos. Como se sugirió anteriormente, primero debe verificar el rectángulo delimitador y tratar los orificios de los polígonos por separado.

La idea detrás de esto es bastante simple. El autor lo describe de la siguiente manera:

Ejecuto un rayo semiinfinito horizontalmente (aumentando x, fijo y) desde el punto de prueba, y cuento cuántos bordes cruza. En cada cruce, el rayo cambia entre el interior y el exterior. Esto se llama el teorema de la curva de Jordan.

La variable c cambia de 0 a 1 y de 1 a 0 cada vez que el rayo horizontal cruza cualquier borde. Así que, básicamente, se realiza un seguimiento de si el número de bordes cruzados es par o impar. 0 significa par y 1 significa impar.

El artículo de Eric Haines citado por bobobobo es realmente excelente. Particularmente interesantes son las tablas que comparan el rendimiento de los algoritmos; El método de suma de ángulos es realmente malo en comparación con los otros. También es interesante que las optimizaciones como el uso de una cuadrícula de búsqueda para subdividir aún más el polígono en sectores de "entrada" y "salida" pueden hacer que la prueba sea increíblemente rápida incluso en polígonos con> 1000 lados.

De todos modos, son los primeros días, pero mi voto va al método de los "cruces", que es lo que Mecki describe, creo. Sin embargo, lo encontré más sucintamente descrito y codificado por David Bourke . Me encanta que no se requiera una trigonometría real, y funciona para convexos y cóncavos, y funciona razonablemente bien a medida que aumenta el número de lados.

Por cierto, aquí está una de las tablas de rendimiento del artículo de Eric Haines para el interés, las pruebas en polígonos aleatorios.

number of edges per polygon 3 4 10 100 1000 MacMartin 2.9 3.2 5.9 50.6 485 Crossings 3.1 3.4 6.8 60.0 624 Triangle Fan+edge sort 1.1 1.8 6.5 77.6 787 Triangle Fan 1.2 2.1 7.3 85.4 865 Barycentric 2.1 3.8 13.8 160.7 1665 Angle Summation 56.2 70.4 153.6 1403.8 14693 Grid (100x100) 1.5 1.5 1.6 2.1 9.8 Grid (20x20) 1.7 1.7 1.9 5.7 42.2 Bins (100) 1.8 1.9 2.7 15.1 117 Bins (20) 2.1 2.2 3.7 26.3 278

Esta pregunta es muy interesante. Tengo otra idea viable diferente de otras respuestas de este post.

La idea es usar la suma de ángulos para decidir si el objetivo está dentro o fuera. Si el objetivo está dentro de un área, la suma de la forma del ángulo por el objetivo y cada dos puntos de borde será 360. Si el objetivo está fuera, la suma no será 360. El ángulo tiene dirección. Si el ángulo va hacia atrás, el ángulo es negativo. Esto es como calcular el número de bobinado .

Consulte esta imagen para obtener una comprensión básica de la idea:

Mi algoritmo asume que en el sentido de las agujas del reloj es la dirección positiva. Aquí hay una entrada potencial:

[[-122.402015, 48.225216], [-117.032049, 48.999931], [-116.919132, 45.995175], [-124.079107, 46.267259], [-124.717175, 48.377557], [-122.92315, 47.047963], [-122.402015, 48.225216]]

El siguiente es el código de Python que implementa la idea:

def isInside(self, border, target): degree = 0 for i in range(len(border) - 1): a = border[i] b = border[i + 1] # calculate distance of vector A = getDistance(a[0], a[1], b[0], b[1]); B = getDistance(target[0], target[1], a[0], a[1]) C = getDistance(target[0], target[1], b[0], b[1]) # calculate direction of vector ta_x = a[0] - target[0] ta_y = a[1] - target[1] tb_x = b[0] - target[0] tb_y = b[1] - target[1] cross = tb_y * ta_x - tb_x * ta_y clockwise = cross < 0 # calculate sum of angles if(clockwise): degree = degree + math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C))) else: degree = degree - math.degrees(math.acos((B * B + C * C - A * A) / (2.0 * B * C))) if(abs(round(degree) - 360) <= 3): return True return False

Hice un trabajo sobre esto cuando era investigador de Michael Stonebraker ; ya sabes, el profesor que creó Ingres , PostgreSQL , etc.

Nos dimos cuenta de que la forma más rápida era hacer primero un cuadro delimitador porque es SUPER rápido. Si está fuera del cuadro delimitador, está fuera. De lo contrario, haces el trabajo más duro ...

Si desea un gran algoritmo, consulte el código fuente del proyecto de código abierto PostgreSQL para el trabajo geo ...

Quiero señalar, nunca obtuvimos ninguna información sobre la zurda contra la zurda (también expresable como un problema "adentro" vs "afuera" ...

ACTUALIZAR

El enlace de BKB proporcionó un buen número de algoritmos razonables. Estaba trabajando en problemas de la Ciencia de la Tierra y, por lo tanto, necesitaba una solución que funcione en latitud / longitud, y tiene el problema peculiar de la habilidad con la mano: ¿el área dentro del área más pequeña o el área más grande? La respuesta es que la "dirección" de las verticías es importante, ya sea zurda o diestra, y de esta manera puede indicar cualquiera de las áreas como "dentro" de cualquier polígono dado. Como tal, mi trabajo utilizó la solución tres enumerada en esa página.

Además, mi trabajo utilizó funciones separadas para las pruebas "en línea".

... Desde que alguien preguntó: descubrimos que las pruebas del cuadro delimitador eran mejores cuando el número de verticales iba más allá de algún número; haga una prueba muy rápida antes de hacer la prueba más larga si es necesario ... Se crea un cuadro delimitador simplemente tomando el x mayor, x menor, x mayor y menor y y juntándolas para obtener cuatro puntos de una caja ...

Otro consejo para los que siguen: hicimos toda nuestra computación más sofisticada y de "atenuación de la luz" en un espacio de cuadrícula, todos en puntos positivos en un plano y luego volvimos a proyectarla en la longitud / latitud "real", evitando así posibles errores de envolviéndolo cuando se cruza una línea 180 de longitud y cuando se manejan regiones polares. Funcionó muy bien!

La respuesta de David Segond es prácticamente la respuesta general estándar, y la de Richard T es la optimización más común, aunque existen algunas otras. Otras optimizaciones fuertes se basan en soluciones menos generales. Por ejemplo, si va a verificar el mismo polígono con muchos puntos, triangular el polígono puede acelerar enormemente las cosas, ya que hay una serie de algoritmos de búsqueda de TIN muy rápidos. Otra es si el polígono y los puntos están en un plano limitado a baja resolución, por ejemplo, una pantalla, puede pintar el polígono en un búfer de memoria mapeado en un color determinado y verificar el color de un píxel dado para ver si se encuentra en los polígonos.

Al igual que muchas optimizaciones, éstas se basan en casos específicos en lugar de generales, y producen beneficios basados ​​en el tiempo amortizado en lugar de un solo uso.

Trabajando en este campo, encontré que la Geometría computacional de Joeseph O''Rourkes en C ''ISBN 0-521-44034-3 fue de gran ayuda.

La solución trivial sería dividir el polígono en triángulos y probar los triángulos como se explica here

Si tu polígono es CONVEX , podría haber un mejor enfoque. Mira el polígono como una colección de líneas infinitas. Cada línea divide el espacio en dos. para cada punto es fácil decir si está en un lado o en el otro lado de la línea. Si un punto está en el mismo lado de todas las líneas, entonces está dentro del polígono.

Me doy cuenta de que esto es viejo, pero aquí hay un algoritmo de lanzamiento de rayos implementado en Cocoa, en caso de que alguien esté interesado No estoy seguro de que sea la forma más eficiente de hacer las cosas, pero puede ayudar a alguien.

- (BOOL)shape:(NSBezierPath *)path containsPoint:(NSPoint)point { NSBezierPath *currentPath = [path bezierPathByFlatteningPath]; BOOL result; float aggregateX = 0; //I use these to calculate the centroid of the shape float aggregateY = 0; NSPoint firstPoint[1]; [currentPath elementAtIndex:0 associatedPoints:firstPoint]; float olderX = firstPoint[0].x; float olderY = firstPoint[0].y; NSPoint interPoint; int noOfIntersections = 0; for (int n = 0; n < [currentPath elementCount]; n++) { NSPoint points[1]; [currentPath elementAtIndex:n associatedPoints:points]; aggregateX += points[0].x; aggregateY += points[0].y; } for (int n = 0; n < [currentPath elementCount]; n++) { NSPoint points[1]; [currentPath elementAtIndex:n associatedPoints:points]; //line equations in Ax + By = C form float _A_FOO = (aggregateY/[currentPath elementCount]) - point.y; float _B_FOO = point.x - (aggregateX/[currentPath elementCount]); float _C_FOO = (_A_FOO * point.x) + (_B_FOO * point.y); float _A_BAR = olderY - points[0].y; float _B_BAR = points[0].x - olderX; float _C_BAR = (_A_BAR * olderX) + (_B_BAR * olderY); float det = (_A_FOO * _B_BAR) - (_A_BAR * _B_FOO); if (det != 0) { //intersection points with the edges float xIntersectionPoint = ((_B_BAR * _C_FOO) - (_B_FOO * _C_BAR)) / det; float yIntersectionPoint = ((_A_FOO * _C_BAR) - (_A_BAR * _C_FOO)) / det; interPoint = NSMakePoint(xIntersectionPoint, yIntersectionPoint); if (olderX <= points[0].x) { //doesn''t matter in which direction the ray goes, so I send it right-ward. if ((interPoint.x >= olderX && interPoint.x <= points[0].x) && (interPoint.x > point.x)) { noOfIntersections++; } } else { if ((interPoint.x >= points[0].x && interPoint.x <= olderX) && (interPoint.x > point.x)) { noOfIntersections++; } } } olderX = points[0].x; olderY = points[0].y; } if (noOfIntersections % 2 == 0) { result = FALSE; } else { result = TRUE; } return result; }

Para gráficos, prefiero no preferir los enteros. Muchos sistemas usan enteros para pintar UI (los píxeles son intactos después de todo), pero macOS, por ejemplo, usa flotar para todo. macOS solo conoce puntos y un punto se puede traducir a un píxel, pero dependiendo de la resolución del monitor, podría traducirse a otra cosa. En las pantallas de la retina, medio punto (0.5 / 0.5) es píxel. Sin embargo, nunca me di cuenta de que las IU de macOS son significativamente más lentas que otras IU. Después de que todas las API 3D (OpenGL o Direct3D) también funcionan con flotadores y las bibliotecas de gráficos modernas a menudo aprovechan la aceleración de la GPU.

Ahora dijiste que la velocidad es tu principal preocupación, bueno, vamos por la velocidad. Antes de ejecutar cualquier algoritmo sofisticado, primero realice una prueba simple. Crea un cuadro de límite alineado con el eje alrededor de tu polígono. Esto es muy fácil, rápido y ya puede asegurarle muchos cálculos. ¿Cómo funciona? Iterar sobre todos los puntos del polígono y encontrar los valores mínimo / máximo de X e Y.

Por ejemplo, tienes los puntos (9/1), (4/3), (2/7), (8/2), (3/6) . Esto significa que Xmin es 2, Xmax es 9, Ymin es 1 y Ymax es 7. Un punto fuera del rectángulo con los dos bordes (2/1) y (9/7) no puede estar dentro del polígono.

// p is your point, p.x is the x coord, p.y is the y coord if (p.x < Xmin || p.x > Xmax || p.y < Ymin || p.y > Ymax) { // Definitely not within the polygon! }

Esta es la primera prueba para ejecutar para cualquier punto. Como puede ver, esta prueba es ultra rápida pero también es muy basta. Para manejar los puntos que están dentro del rectángulo delimitador, necesitamos un algoritmo más sofisticado. Hay un par de maneras en que esto puede ser calculado. El método que funcione también depende del hecho de si el polígono puede tener agujeros o siempre será sólido. Aquí hay ejemplos de sólidos (uno convexo, otro cóncavo):

Y aquí hay uno con un agujero:

El verde tiene un agujero en el medio!

El algoritmo más sencillo, que puede manejar los tres casos anteriores y aún es bastante rápido, se llama casting de rayos . La idea del algoritmo es bastante simple: dibuja un rayo virtual desde cualquier lugar fuera del polígono hasta tu punto y cuenta la frecuencia con la que golpea un lado del polígono. Si el número de hits es par, está fuera del polígono, si es impar, está dentro.

El algoritmo del número de devanado sería una alternativa, es más preciso para los puntos que están muy cerca de una línea de polígono, pero también es mucho más lento. El lanzamiento de rayos puede fallar en puntos demasiado cercanos al lado de un polígono debido a la limitada precisión del punto flotante y los problemas de redondeo, pero en realidad eso no es un problema, ya que si un punto se encuentra tan cerca de un lado, a menudo no es posible visualmente. El espectador debe reconocer si ya está dentro o si todavía está fuera.

Todavía tienes el cuadro delimitador de arriba, ¿recuerdas? Simplemente elija un punto fuera del cuadro delimitador y utilícelo como punto de partida para su rayo. Por ejemplo, el punto (Xmin - e/py) está fuera del polígono con seguridad.

Pero ¿qué es e ? Bueno, e (en realidad épsilon) le da al cuadro delimitador algo de relleno . Como dije, el trazado de rayos falla si comenzamos demasiado cerca de una línea de polígono. Dado que el cuadro delimitador puede ser igual al polígono (si el polígono es un rectángulo alineado con el eje, el cuadro delimitador es igual al polígono en sí), necesitamos algo de relleno para hacer esto seguro, eso es todo. ¿Qué tan grande debe elegir e ? No tan grande. Depende de la escala del sistema de coordenadas que usas para dibujar. Si el ancho de tu píxel es 1.0, solo elige 1.0 (aunque 0.1 también habría funcionado)

Ahora que tenemos el rayo con sus coordenadas de inicio y fin, el problema cambia de " es el punto dentro del polígono " a "con qué frecuencia el rayo se cruza con un lado del polígono ". Por lo tanto, no podemos trabajar con los puntos de polígono como antes, ahora necesitamos los lados reales. Un lado siempre está definido por dos puntos.

side 1: (X1/Y1)-(X2/Y2) side 2: (X2/Y2)-(X3/Y3) side 3: (X3/Y3)-(X4/Y4) :

Necesitas probar el rayo contra todos los lados. Considera que el rayo es un vector y que cada lado es un vector. El rayo tiene que golpear a cada lado exactamente una vez o nunca en absoluto. No puede golpear el mismo lado dos veces. Dos líneas en el espacio 2D siempre se intersecarán exactamente una vez, a menos que sean paralelas, en cuyo caso nunca se intersectan. Sin embargo, como los vectores tienen una longitud limitada, es posible que dos vectores no sean paralelos y aún nunca se crucen porque son demasiado cortos para encontrarse uno con el otro.

// Test the ray against all sides int intersections = 0; for (side = 0; side < numberOfSides; side++) { // Test if current side intersects with ray. // If yes, intersections++; } if ((intersections & 1) == 1) { // Inside of polygon } else { // Outside of polygon }

Hasta ahora todo bien, pero ¿cómo se prueba si dos vectores se intersecan? Aquí hay un código C (no probado), que debería hacer el truco:

#define NO 0 #define YES 1 #define COLLINEAR 2 int areIntersecting( float v1x1, float v1y1, float v1x2, float v1y2, float v2x1, float v2y1, float v2x2, float v2y2 ) { float d1, d2; float a1, a2, b1, b2, c1, c2; // Convert vector 1 to a line (line 1) of infinite length. // We want the line in linear equation standard form: A*x + B*y + C = 0 // See: http://en.wikipedia.org/wiki/Linear_equation a1 = v1y2 - v1y1; b1 = v1x1 - v1x2; c1 = (v1x2 * v1y1) - (v1x1 * v1y2); // Every point (x,y), that solves the equation above, is on the line, // every point that does not solve it, is not. The equation will have a // positive result if it is on one side of the line and a negative one // if is on the other side of it. We insert (x1,y1) and (x2,y2) of vector // 2 into the equation above. d1 = (a1 * v2x1) + (b1 * v2y1) + c1; d2 = (a1 * v2x2) + (b1 * v2y2) + c1; // If d1 and d2 both have the same sign, they are both on the same side // of our line 1 and in that case no intersection is possible. Careful, // 0 is a special case, that''s why we don''t test ">=" and "<=", // but "<" and ">". if (d1 > 0 && d2 > 0) return NO; if (d1 < 0 && d2 < 0) return NO; // The fact that vector 2 intersected the infinite line 1 above doesn''t // mean it also intersects the vector 1. Vector 1 is only a subset of that // infinite line 1, so it may have intersected that line before the vector // started or after it ended. To know for sure, we have to repeat the // the same test the other way round. We start by calculating the // infinite line 2 in linear equation standard form. a2 = v2y2 - v2y1; b2 = v2x1 - v2x2; c2 = (v2x2 * v2y1) - (v2x1 * v2y2); // Calculate d1 and d2 again, this time using points of vector 1. d1 = (a2 * v1x1) + (b2 * v1y1) + c2; d2 = (a2 * v1x2) + (b2 * v1y2) + c2; // Again, if both have the same sign (and neither one is 0), // no intersection is possible. if (d1 > 0 && d2 > 0) return NO; if (d1 < 0 && d2 < 0) return NO; // If we get here, only two possibilities are left. Either the two // vectors intersect in exactly one point or they are collinear, which // means they intersect in any number of points from zero to infinite. if ((a1 * b2) - (a2 * b1) == 0.0f) return COLLINEAR; // If they are not collinear, they must intersect in exactly one point. return YES; }

Los valores de entrada son los dos puntos finales del vector 1 ( v1x1/v1y1 y v1x2/v1y2 ) y el vector 2 ( v2x1/v2y1 y v2x2/v2y2 ). Entonces tienes 2 vectores, 4 puntos, 8 coordenadas. YES y NO son claros. YES aumenta las intersecciones, NO hace nada.

¿Qué pasa con COLLINEAR? Significa que ambos vectores se encuentran en la misma línea infinita, dependiendo de la posición y la longitud, no se intersecan en absoluto o se intersecan en un número infinito de puntos. No estoy absolutamente seguro de cómo manejar este caso, no lo consideraría como una intersección de ninguna manera. Bueno, este caso es bastante raro en la práctica de todos modos debido a errores de redondeo de punto flotante; un código mejor probablemente no probaría para == 0.0f sino para algo como < epsilon , donde épsilon es un número bastante pequeño.

Si necesita probar un número mayor de puntos, puede acelerar todo un poco manteniendo las formas estándar de la ecuación lineal de los lados del polígono en la memoria, de modo que no tenga que volver a calcularlos cada vez. Esto le ahorrará dos multiplicaciones de punto flotante y tres restas de punto flotante en cada prueba a cambio de almacenar en la memoria tres valores de punto flotante por lado de polígono. Es un intercambio típico entre memoria y tiempo de cálculo.

Por último, pero no menos importante: si puede usar hardware 3D para resolver el problema, hay una alternativa interesante. Solo deja que la GPU haga todo el trabajo por ti. Crear una superficie de pintura que está fuera de la pantalla. Rellénelo completamente con el color negro. Ahora deja que OpenGL o Direct3D pinten tu polígono (o incluso todos tus polígonos si solo quieres probar si el punto está dentro de alguno de ellos, pero no te importa cuál) y rellena los polígonos con un color diferente. color, por ejemplo, blanco. Para verificar si un punto está dentro del polígono, obtenga el color de este punto de la superficie de dibujo. Esto es solo una recuperación de memoria O (1).

Por supuesto, este método solo se puede usar si la superficie de dibujo no tiene que ser enorme. Si no puede caber en la memoria de la GPU, este método es más lento que hacerlo en la CPU. Si tuviera que ser enorme y su GPU es compatible con sombreadores modernos, aún puede utilizar la GPU implementando el fundido de rayos que se muestra arriba como un sombreador de GPU, lo que es absolutamente posible. Para una mayor cantidad de polígonos o una gran cantidad de puntos para probar, esto dará sus frutos, considere que algunas GPU podrán probar de 64 a 256 puntos en paralelo. Sin embargo, tenga en cuenta que transferir datos de la CPU a la GPU y viceversa siempre es costoso, por lo que solo para probar un par de puntos contra un par de polígonos simples, donde los puntos o los polígonos son dinámicos y cambiarán con frecuencia, un enfoque de GPU rara vez pagará apagado.

Realmente me gusta la solución publicada por Nirg y editada por bobobobo. Acabo de hacer que sea javascript y un poco más legible para mi uso:

function insidePoly(poly, pointx, pointy) { var i, j; var inside = false; for (i = 0, j = poly.length - 1; i < poly.length; j = i++) { if(((poly[i].y > pointy) != (poly[j].y > pointy)) && (pointx < (poly[j].x-poly[i].x) * (pointy-poly[i].y) / (poly[j].y-poly[i].y) + poly[i].x) ) inside = !inside; } return inside; }

Versión de Obj-C de la respuesta de nirg con método de muestra para puntos de prueba. La respuesta de Nirg funcionó bien para mí.

- (BOOL)isPointInPolygon:(NSArray *)vertices point:(CGPoint)test { NSUInteger nvert = [vertices count]; NSInteger i, j, c = 0; CGPoint verti, vertj; for (i = 0, j = nvert-1; i < nvert; j = i++) { verti = [(NSValue *)[vertices objectAtIndex:i] CGPointValue]; vertj = [(NSValue *)[vertices objectAtIndex:j] CGPointValue]; if (( (verti.y > test.y) != (vertj.y > test.y) ) && ( test.x < ( vertj.x - verti.x ) * ( test.y - verti.y ) / ( vertj.y - verti.y ) + verti.x) ) c = !c; } return (c ? YES : NO); } - (void)testPoint { NSArray *polygonVertices = [NSArray arrayWithObjects: [NSValue valueWithCGPoint:CGPointMake(13.5, 41.5)], [NSValue valueWithCGPoint:CGPointMake(42.5, 56.5)], [NSValue valueWithCGPoint:CGPointMake(39.5, 69.5)], [NSValue valueWithCGPoint:CGPointMake(42.5, 84.5)], [NSValue valueWithCGPoint:CGPointMake(13.5, 100.0)], [NSValue valueWithCGPoint:CGPointMake(6.0, 70.5)], nil ]; CGPoint tappedPoint = CGPointMake(23.0, 70.0); if ([self isPointInPolygon:polygonVertices point:tappedPoint]) { NSLog(@"YES"); } else { NSLog(@"NO"); } }

Versión rápida de la respuesta por nirg :

extension CGPoint { func isInsidePolygon(vertices: [CGPoint]) -> Bool { guard !vertices.isEmpty else { return false } var j = vertices.last!, c = false for i in vertices { let a = (i.y > y) != (j.y > y) let b = (x < (j.x - i.x) * (y - i.y) / (j.y - i.y) + i.x) if a && b { c = !c } j = i } return c } }

VERSIÓN VBA:

Nota: recuerde que si su polígono es un área dentro de un mapa en la que la Latitud / Longitud son valores Y / X en lugar de X / Y (Latitud = Y, Longitud = X) debido a lo que entiendo, son implicaciones históricas de cuando La longitud no era una medida.

MÓDULO DE CLASE: CPoint

Private pXValue As Double Private pYValue As Double ''''''''''X Value Property'''''''''' Public Property Get X() As Double X = pXValue End Property Public Property Let X(Value As Double) pXValue = Value End Property ''''''''''Y Value Property'''''''''' Public Property Get Y() As Double Y = pYValue End Property Public Property Let Y(Value As Double) pYValue = Value End Property

MÓDULO:

Public Function isPointInPolygon(p As CPoint, polygon() As CPoint) As Boolean Dim i As Integer Dim j As Integer Dim q As Object Dim minX As Double Dim maxX As Double Dim minY As Double Dim maxY As Double minX = polygon(0).X maxX = polygon(0).X minY = polygon(0).Y maxY = polygon(0).Y For i = 1 To UBound(polygon) Set q = polygon(i) minX = vbMin(q.X, minX) maxX = vbMax(q.X, maxX) minY = vbMin(q.Y, minY) maxY = vbMax(q.Y, maxY) Next i If p.X < minX Or p.X > maxX Or p.Y < minY Or p.Y > maxY Then isPointInPolygon = False Exit Function End If '' SOURCE: http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html isPointInPolygon = False i = 0 j = UBound(polygon) Do While i < UBound(polygon) + 1 If (polygon(i).Y > p.Y) Then If (polygon(j).Y < p.Y) Then If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then isPointInPolygon = True Exit Function End If End If ElseIf (polygon(i).Y < p.Y) Then If (polygon(j).Y > p.Y) Then If p.X < (polygon(j).X - polygon(i).X) * (p.Y - polygon(i).Y) / (polygon(j).Y - polygon(i).Y) + polygon(i).X Then isPointInPolygon = True Exit Function End If End If End If j = i i = i + 1 Loop End Function Function vbMax(n1, n2) As Double vbMax = IIf(n1 > n2, n1, n2) End Function Function vbMin(n1, n2) As Double vbMin = IIf(n1 > n2, n2, n1) End Function Sub TestPointInPolygon() Dim i As Integer Dim InPolygon As Boolean '' MARKER Object Dim p As CPoint Set p = New CPoint p.X = <ENTER X VALUE HERE> p.Y = <ENTER Y VALUE HERE> '' POLYGON OBJECT Dim polygon() As CPoint ReDim polygon(<ENTER VALUE HERE>) ''Amount of vertices in polygon - 1 For i = 0 To <ENTER VALUE HERE> ''Same value as above Set polygon(i) = New CPoint polygon(i).X = <ASSIGN X VALUE HERE> ''Source a list of values that can be looped through polgyon(i).Y = <ASSIGN Y VALUE HERE> ''Source a list of values that can be looped through Next i InPolygon = isPointInPolygon(p, polygon) MsgBox InPolygon End Sub

Aquí está la versión de golang de @nirg answer (inspirada en el código C # de @@ m-katz)

func isPointInPolygon(polygon []point, testp point) bool { minX := polygon[0].X maxX := polygon[0].X minY := polygon[0].Y maxY := polygon[0].Y for _, p := range polygon { minX = min(p.X, minX) maxX = max(p.X, maxX) minY = min(p.Y, minY) maxY = max(p.Y, maxY) } if testp.X < minX || testp.X > maxX || testp.Y < minY || testp.Y > maxY { return false } inside := false j := len(polygon) - 1 for i := 0; i < len(polygon); i++ { if (polygon[i].Y > testp.Y) != (polygon[j].Y > testp.Y) && testp.X < (polygon[j].X-polygon[i].X)*(testp.Y-polygon[i].Y)/(polygon[j].Y-polygon[i].Y)+polygon[i].X { inside = !inside } j = i } return inside }

Para detectar un golpe en Polygon necesitamos probar dos cosas:

  1. Si el punto está dentro del área del polígono. (Se puede lograr mediante el algoritmo de Ray-Casting)
  2. Si el punto está en el borde del polígono (se puede lograr con el mismo algoritmo que se usa para la detección del punto en la polilínea (línea)).

Puede hacerlo comprobando si el área formada al conectar el punto deseado a los vértices de su polígono coincide con el área del polígono en sí.

O puede verificar si la suma de los ángulos internos de su punto a cada par de dos vértices de polígonos consecutivos a su punto de verificación asciende a 360, pero tengo la sensación de que la primera opción es más rápida porque no implica divisiones ni cálculos de inversa de funciones trigonométricas.

No sé qué sucede si su polígono tiene un agujero en su interior, pero me parece que la idea principal puede adaptarse a esta situación.

También puedes publicar la pregunta en una comunidad de matemáticas. Apuesto a que tienen un millón de maneras de hacer eso.

Puerto .Net:

static void Main(string[] args) { Console.Write("Hola"); List<double> vertx = new List<double>(); List<double> verty = new List<double>(); int i, j, c = 0; vertx.Add(1); vertx.Add(2); vertx.Add(1); vertx.Add(4); vertx.Add(4); vertx.Add(1); verty.Add(1); verty.Add(2); verty.Add(4); verty.Add(4); verty.Add(1); verty.Add(1); int nvert = 6; //Vértices del poligono double testx = 2; double testy = 5; for (i = 0, j = nvert - 1; i < nvert; j = i++) { if (((verty[i] > testy) != (verty[j] > testy)) && (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i])) c = 1; } }

Si está buscando una biblioteca de scripts java, hay una extensión de google maps v3 de javascript para que la clase Polygon detecte si un punto reside dentro de ella o no.

var polygon = new google.maps.Polygon([], "#000000", 1, 1, "#336699", 0.3); var isWithinPolygon = polygon.containsLatLng(40, -90);

Google Extention Github

Versión de Java:

public class Geocode { private float latitude; private float longitude; public Geocode() { } public Geocode(float latitude, float longitude) { this.latitude = latitude; this.longitude = longitude; } public float getLatitude() { return latitude; } public void setLatitude(float latitude) { this.latitude = latitude; } public float getLongitude() { return longitude; } public void setLongitude(float longitude) { this.longitude = longitude; } } public class GeoPolygon { private ArrayList<Geocode> points; public GeoPolygon() { this.points = new ArrayList<Geocode>(); } public GeoPolygon(ArrayList<Geocode> points) { this.points = points; } public GeoPolygon add(Geocode geo) { points.add(geo); return this; } public boolean inside(Geocode geo) { int i, j; boolean c = false; for (i = 0, j = points.size() - 1; i < points.size(); j = i++) { if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) && (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude())) c = !c; } return c; } }

Versión de Scala de la solución por nirg (se supone que la comprobación previa del rectángulo delimitador se realiza por separado):

def inside(p: Point, polygon: Array[Point], bounds: Bounds): Boolean = { val length = polygon.length @tailrec def oddIntersections(i: Int, j: Int, tracker: Boolean): Boolean = { if (i == length) tracker else { val intersects = (polygon(i).y > p.y) != (polygon(j).y > p.y) && p.x < (polygon(j).x - polygon(i).x) * (p.y - polygon(i).y) / (polygon(j).y - polygon(i).y) + polygon(i).x oddIntersections(i + 1, i, if (intersects) !tracker else tracker) } } oddIntersections(0, length - 1, tracker = false) }

Al usar qt (Qt 4.3 +), se puede utilizar la función de QPolygon containsPoint

Aquí hay un punto en la prueba de polígono en C que no usa el lanzamiento de rayos. Y puede funcionar para áreas superpuestas (auto intersecciones), vea el use_holesargumento.

/* math lib (defined below) */ static float dot_v2v2(const float a[2], const float b[2]); static float angle_signed_v2v2(const float v1[2], const float v2[2]); static void copy_v2_v2(float r[2], const float a[2]); /* intersection function */ bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr, const bool use_holes) { /* we do the angle rule, define that all added angles should be about zero or (2 * PI) */ float angletot = 0.0; float fp1[2], fp2[2]; unsigned int i; const float *p1, *p2; p1 = verts[nr - 1]; /* first vector */ fp1[0] = p1[0] - pt[0]; fp1[1] = p1[1] - pt[1]; for (i = 0; i < nr; i++) { p2 = verts[i]; /* second vector */ fp2[0] = p2[0] - pt[0]; fp2[1] = p2[1] - pt[1]; /* dot and angle and cross */ angletot += angle_signed_v2v2(fp1, fp2); /* circulate */ copy_v2_v2(fp1, fp2); p1 = p2; } angletot = fabsf(angletot); if (use_holes) { const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f); angletot -= nested * (float)(M_PI * 2.0); return (angletot > 4.0f) != ((int)nested % 2); } else { return (angletot > 4.0f); } } /* math lib */ static float dot_v2v2(const float a[2], const float b[2]) { return a[0] * b[0] + a[1] * b[1]; } static float angle_signed_v2v2(const float v1[2], const float v2[2]) { const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]); return atan2f(perp_dot, dot_v2v2(v1, v2)); } static void copy_v2_v2(float r[2], const float a[2]) { r[0] = a[0]; r[1] = a[1]; }

Nota: este es uno de los métodos menos óptimos ya que incluye muchas llamadas a atan2f, pero puede ser de interés para los desarrolladores que leen este hilo (en mis pruebas es ~ 23x más lento que usar el método de intersección de líneas)

He hecho una implementación de Python de C ++ code :

Entradas

  • bounding_points: nodos que forman el polígono.

  • bounding_box_positions: puntos candidatos para filtrar. (En mi implementación creada desde el cuadro delimitador.

    (Las entradas son listas de tuplas en el formato: [(xcord, ycord), ...])

Devoluciones

  • Todos los puntos que están dentro del polígono.

def polygon_ray_casting(self, bounding_points, bounding_box_positions): # Arrays containing the x- and y-coordinates of the polygon''s vertices. vertx = [point[0] for point in bounding_points] verty = [point[1] for point in bounding_points] # Number of vertices in the polygon nvert = len(bounding_points) # Points that are inside points_inside = [] # For every candidate position within the bounding box for idx, pos in enumerate(bounding_box_positions): testx, testy = (pos[0], pos[1]) c = 0 for i in range(0, nvert): j = i - 1 if i != 0 else nvert - 1 if( ((verty[i] > testy ) != (verty[j] > testy)) and (testx < (vertx[j] - vertx[i]) * (testy - verty[i]) / (verty[j] - verty[i]) + vertx[i]) ): c += 1 # If odd, that means that we are inside the polygon if c % 2 == 1: points_inside.append(pos) return points_inside

De nuevo, la idea está tomada desde here

La respuesta depende de si tienes los polígonos simples o complejos. Los polígonos simples no deben tener intersecciones de segmentos de línea. Así que pueden tener los agujeros pero las líneas no pueden cruzarse entre sí. Las regiones complejas pueden tener las intersecciones de línea, por lo que pueden tener regiones superpuestas o regiones que se tocan entre sí solo por un punto.

Para polígonos simples, el mejor algoritmo es el de Ray casting (Número de cruce). Para polígonos complejos, este algoritmo no detecta puntos que están dentro de las regiones superpuestas. Así que para polígonos complejos tienes que usar el algoritmo de número de bobina.

Aquí hay un excelente artículo con implementación en C de ambos algoritmos. Los probé y funcionan bien.

http://geomalgorithms.com/a03-_inclusion.html

La versión de C # de la respuesta de nirg está aquí: solo compartiré el código. Puede salvar a alguien algún tiempo.

public static bool IsPointInPolygon(IList<Point> polygon, Point testPoint) { bool result = false; int j = polygon.Count() - 1; for (int i = 0; i < polygon.Count(); i++) { if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y) { if (polygon[i].X + (testPoint.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < testPoint.X) { result = !result; } } j = i; } return result; }

No hay nada más hermoso que una definición inductiva de un problema. En aras de la exhaustividad, aquí tiene una versión en prólogo que también puede aclarar los pensamientos detrás del lanzamiento de rayos :

Basado en la simulación del algoritmo de simplicidad en here

Algunos predicadores de ayuda:

exor(A,B):- /+A,B;A,/+B. in_range(Coordinate,CA,CB) :- exor((CA>Coordinate),(CB>Coordinate)). inside(false). inside(_,[_|[]]). inside(X:Y, [X1:Y1,X2:Y2|R]) :- in_range(Y,Y1,Y2), X > ( ((X2-X1)*(Y-Y1))/(Y2-Y1) + X1),toggle_ray, inside(X:Y, [X2:Y2|R]); inside(X:Y, [X2:Y2|R]). get_line(_,_,[]). get_line([XA:YA,XB:YB],[X1:Y1,X2:Y2|R]):- [XA:YA,XB:YB]=[X1:Y1,X2:Y2]; get_line([XA:YA,XB:YB],[X2:Y2|R]).

La ecuación de una línea dada 2 puntos A y B (Línea (A, B)) es:

(YB-YA) Y - YA = ------- * (X - XA) (XB-YB)

Es importante que la dirección de rotación de la línea esté configurada en el sentido de las agujas del reloj para los límites y en el sentido contrario a las agujas del reloj para los orificios. Vamos a comprobar si el punto (X, Y), es decir, el punto probado está en el semiplano izquierdo de nuestra línea (es una cuestión de gusto, también podría ser el lado derecho, pero también la dirección de los límites). las líneas deben cambiarse en ese caso), esto es para proyectar el rayo desde el punto a la derecha (o izquierda) y reconocer la intersección con la línea. Hemos elegido proyectar el rayo en la dirección horizontal (de nuevo, es una cuestión de gusto, también se podría hacer en vertical con restricciones similares), por lo que tenemos:

(XB-XA) X < ------- * (Y - YA) + XA (YB-YA)

Ahora necesitamos saber si el punto está solo en el lado izquierdo (o derecho) del segmento de línea, no en todo el plano, por lo que necesitamos restringir la búsqueda solo a este segmento, pero esto es fácil porque estamos dentro del segmento. solo un punto en la línea puede ser más alto que Y en el eje vertical. Como esta es una restricción más fuerte, debe ser el primero en verificar, por lo que primero tomamos solo aquellas líneas que cumplen con este requisito y luego verificamos su posición. Según el teorema de la curva de Jordan, cualquier rayo proyectado a un polígono debe intersecarse en un número par de líneas. Así que hemos terminado, lanzaremos el rayo a la derecha y luego, cada vez que cruce una línea, cambiará su estado. Sin embargo, en nuestra implementación, nos encargamos de verificar la longitud de la bolsa de soluciones que cumplen con las restricciones dadas y decidir la incorporación a la misma. Para cada línea en el polígono esto debe hacerse.

is_left_half_plane(_,[],[],_). is_left_half_plane(X:Y,[XA:YA,XB:YB], [[X1:Y1,X2:Y2]|R], Test) :- [XA:YA, XB:YB] = [X1:Y1, X2:Y2], call(Test, X , (((XB - XA) * (Y - YA)) / (YB - YA) + XA)); is_left_half_plane(X:Y, [XA:YA, XB:YB], R, Test). in_y_range_at_poly(Y,[XA:YA,XB:YB],Polygon) :- get_line([XA:YA,XB:YB],Polygon), in_range(Y,YA,YB). all_in_range(Coordinate,Polygon,Lines) :- aggregate(bag(Line), in_y_range_at_poly(Coordinate,Line,Polygon), Lines). traverses_ray(X:Y, Lines, Count) :- aggregate(bag(Line), is_left_half_plane(X:Y, Line, Lines, <), IntersectingLines), length(IntersectingLines, Count). % This is the entry point predicate inside_poly(X:Y,Polygon,Answer) :- all_in_range(Y,Polygon,Lines), traverses_ray(X:Y, Lines, Count), (1 is mod(Count,2)->Answer=inside;Answer=outside).

Para hacer frente a los siguientes casos especiales en el algoritmo de fundición Ray :

  1. El rayo se superpone a uno de los lados del polígono.
  2. El punto está dentro del polígono y el rayo pasa a través de un vértice del polígono.
  3. El punto está fuera del polígono y el rayo solo toca uno de los ángulos del polígono.

Verifique si un punto está dentro de un polígono complejo . El artículo proporciona una manera fácil de resolverlos para que no se requiera un tratamiento especial para los casos anteriores.