Menu
The polygon is given as a list of Vector2I objects (2 dimensional, integer coordinates). How can i test if a given point is inside? All implementations i found on the web fail for some trivial counter-example. It really seems to be hard to write a correct implementation. The language does not matter as i will port it myself.
943
Algorithm: For a convex polygon, if the sides of the polygon can be considered as a path from any one of the vertex. Then, a query point is said to be inside the polygon if it lies on the same side of all the line segments making up the path.
One simple way of finding whether the point is inside or outside a simple polygon is to test how many times a ray, starting from the point and going in any fixed direction, intersects the edges of the polygon. If the point is on the outside of the polygon the ray will intersect its edge an even number of times.
First, obtain the convex hull for your point cloud. Then loop over all of the edges of the convex hull in counter-clockwise order. For each of the edges, check whether your target point lies to the "left" of that edge. When doing this, treat the edges as vectors pointing counter-clockwise around the convex hull.
If it is convex, a trivial way to check it is that the point is laying on the same side of all the segments (if traversed in the same order).
You can check that easily with the dot product (as it is proportional to the cosine of the angle formed between the segment and the point, if we calculate it with the normal of the edge, those with positive sign would lay on the right side and those with negative sign on the left side).
Here is the code in 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 = cosine_sign(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 cosine_sign(a, b): return a[0]*b[1]-a[1]*b[0] The Ray Casting or Winding methods are the most common for this problem. See the Wikipedia article for details.
Also, Check out this page for a well-documented solution in C.
22
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
