inside google check geometry polygon hittest

geometry - google - ¿Cómo probar si un punto está dentro de un polígono convexo en coordenadas enteras 2D?



ray casting algorithm (7)

El polígono se da como una lista de objetos Vector2I (2 dimensiones, coordenadas enteras). ¿Cómo puedo probar si un punto dado está dentro? Todas las implementaciones que encontré en la web fallan por algún contra-ejemplo trivial. Realmente parece ser difícil escribir una implementación correcta. El idioma no importa como lo portaré yo mismo.



La respuesta de Fortran casi funcionó para mí, excepto que encontré que tenía que traducir el polígono para que el punto que está probando sea el mismo que el origen. Aquí está el JavaScript que escribí para hacer este trabajo:

function Vec2(x, y) { return [x, y] } Vec2.nsub = function (v1, v2) { return Vec2(v1[0]-v2[0], v1[1]-v2[1]) } // aka the "scalar cross product" Vec2.perpdot = function (v1, v2) { return v1[0]*v2[1] - v1[1]*v2[0] } // Determine if a point is inside a polygon. // // point - A Vec2 (2-element Array). // polyVerts - Array of Vec2''s (2-element Arrays). The vertices that make // up the polygon, in clockwise order around the polygon. // function coordsAreInside(point, polyVerts) { var i, len, v1, v2, edge, x // First translate the polygon so that `point` is the origin. Then, for each // edge, get the angle between two vectors: 1) the edge vector and 2) the // vector of the first vertex of the edge. If all of the angles are the same // sign (which is negative since they will be counter-clockwise) then the // point is inside the polygon; otherwise, the point is outside. for (i = 0, len = polyVerts.length; i < len; i++) { v1 = Vec2.nsub(polyVerts[i], point) v2 = Vec2.nsub(polyVerts[i+1 > len-1 ? 0 : i+1], point) edge = Vec2.nsub(v1, v2) // Note that we could also do this by using the normal + dot product x = Vec2.perpdot(edge, v1) // If the point lies directly on an edge then count it as in the polygon if (x < 0) { return false } } return true }


Los métodos Ray Casting o Winding son los más comunes para este problema. Vea el artículo de Wikipedia para más detalles.

También, revisa esta página para una solución bien documentada en C.



Si el polígono es convexo, entonces en C #, lo siguiente implementa el método de " prueba si siempre está en el mismo lado ", y se ejecuta a lo sumo en O (n de puntos de polígono):

public static bool IsInConvexPolygon(Point testPoint, List<Point> polygon) { //Check if a triangle or higher n-gon Debug.Assert(polygon.Length >= 3); //n>2 Keep track of cross product sign changes var pos = 0; var neg = 0; for (var i = 0; i < polygon.Count; i++) { //If point is in the polygon if (polygon[i] == testPoint) return true; //Form a segment between the i''th point var x1 = polygon[i].X; var y1 = polygon[i].Y; //And the i+1''th, or if i is the last, with the first point var i2 = i < polygon.Count - 1 ? i + 1 : 0; var x2 = polygon[i2].X; var y2 = polygon[i2].Y; var x = testPoint.X; var y = testPoint.Y; //Compute the cross product var d = (x - x1)*(y2 - y1) - (y - y1)*(x2 - x1); if (d > 0) pos++; if (d < 0) neg++; //If the sign changes, then point is outside if (pos > 0 && neg > 0) return false; } //If no change in direction, then on same side of all segments, and thus inside return true; }


Si es convexo, una forma trivial de comprobarlo es que el punto se encuentra en el mismo lado de todos los segmentos (si se recorre en el mismo orden).

Puede verificarlo fácilmente con el producto cruzado (ya que es proporcional al coseno del ángulo formado entre el segmento y el punto, aquellos con signo positivo se ubicarán en el lado derecho y aquellos con signo negativo en el lado izquierdo).

Aquí está el código en Python:

RIGHT = "RIGHT" LEFT = "LEFT" def inside_convex_polygon(point, vertices): previous_side = None n_vertices = len(vertices) for n in xrange(n_vertices): a, b = vertices[n], vertices[(n+1)%n_vertices] affine_segment = v_sub(b, a) affine_point = v_sub(point, a) current_side = get_side(affine_segment, affine_point) if current_side is None: return False #outside or over an edge elif previous_side is None: #first segment previous_side = current_side elif previous_side != current_side: return False return True def get_side(a, b): x = x_product(a, b) if x < 0: return LEFT elif x > 0: return RIGHT else: return None def v_sub(a, b): return (a[0]-b[0], a[1]-b[1]) def x_product(a, b): return a[0]*b[1]-a[1]*b[0]


la forma en que sé es algo así.

Si selecciona un punto en algún lugar fuera del polígono, puede estar muy lejos de la geometría. luego trazas una línea desde este punto. Quiero decir que creas una ecuación de línea con estos dos puntos.

Luego, para cada línea en este polígono, verifica si se intersecan.

La suma del número de líneas entrecruzadas te lo da dentro o no.

si es raro: por dentro

si es parejo: afuera