How to test if a point is inside of a convex polygon in 2D integer coordinates?

by

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]

More Related Contents:

  1. How do I determine if two convex polygons intersect?
  2. How do CSS triangles work?
  3. How do you detect where two line segments intersect? [closed]
  4. Circle-Rectangle collision detection (intersection)
  5. An algorithm for inflating/deflating (offsetting, buffering) polygons
  6. ray and ellipsoid intersection accuracy improvement
  7. How to determine if a list of polygon points are in clockwise order?
  8. A simple algorithm for polygon intersection
  9. How to create circle with Bézier curves?
  10. How do I efficiently determine if a polygon is convex, non-convex or complex?
  11. Largest circle inside a non-convex polygon
  12. How to determine if a point is inside a 2D convex polygon?
  13. Problem superimposing and aligning 3D triangles
  14. Efficiently find points inside a circle sector
  15. Polygon enclosing a set of points
  16. algorithm to rasterize and fill a hypersphere?
  17. Is there a more efficient way of texturing a circle?
  18. How to determine whether a point (X,Y) is contained within an arc section of a circle (i.e. a Pie slice)?
  19. Check if polygon is inside a polygon
  20. Boundary enclosing a given set of points
  21. How can I create an internal spiral for a polygon?
  22. Transfer coordinates from one triangle to another triangle
  23. Checking if a point is inside a polygon
  24. Cone to box collision
  25. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  26. How do I detect intersections between a circle and any other circle in the same plane?
  27. How to find largest triangle in convex hull aside from brute force search
  28. Shortest distance between two line segments
  29. Create non-intersecting polygon passing through all given points
  30. Google Maps API Polygon with “Hole” In Center

Leave a Comment