Points contained in a polygon

  • 0

    Given a list of points, which forms the exterior of a polygon, return a list of all points that are in the interior of the polygon. You are guaranteed the given points forms a single, connected polygon. The list of points is not in any particular order.

    For example given: [(0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1), (2,2)]
    return [(1,1)]

  • 0

    @notek Hi, I have a quick question. Since a set of corners for a concave polygon can be rearranged to be a different concave polygon (not unique), does the problem assume the polygon is convex? Thanks.

  • 1

    @notek I have a simple thought.

    1. Sort the x_min, x_max, y_min, y_max
    2. Create a rectangular from <x_min - 1, y_min -1> to <x_max + 1, y_max + 1>
    3. Choose any point inside the rectangular but not on the exterior of the polygon
    4. Perform a BFS (boundary points of the rectangular and the polygon are marked as visisted)
    5. If during the BFS, the boundary of the rectangular is not visited, then return ( all visited points - exterior of polygon)
      If during the BFS, the boundary of the rectangular is visited, then return (all points insides polygon - visited points)

    In the case, it does not matter whether it is convex or concave

  • 0

    Here's my thought to judge if a point is inside a polygon not matter convex or concave:

    For a point P, draw a horizontal line and a vertical line through P and the polygon. P is inside the polygon if and only if it has old number of intersections in its left and right sides, and its up and down sides.

    So you can do a left to right and bottom to up scan for all the given points to find out the internal points.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.