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)]
@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.
@notek I have a simple thought.
- Sort the x_min, x_max, y_min, y_max
- Create a rectangular from <x_min - 1, y_min -1> to <x_max + 1, y_max + 1>
- Choose any point inside the rectangular but not on the exterior of the polygon
- Perform a BFS (boundary points of the rectangular and the polygon are marked as visisted)
- 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
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.
here is the solution:
Here is my approach:
- The polygon has to be a convex polygon since it is guaranteed that points form a single connected polygon. Multiple non-convex polygons are possible from given set of points.
- Sort the points by slope of line formed by joining origin to the point. Doing this we can compute all the edges of the polygon.
- Consider an enclosing rectangle around the polygon. It can be computed using the min and max x-coordinate and y-coordinate of all the given points.
- For each point in the rectangle, do following to check whether that point is outside or inside the polygon
- (Same as http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/) Draw a horizontal line extending to the right from the point and find intersection of this horizontal line with each edge of the polygon. If there is exactly one intersection, then point is inside polygon. There are few edge cases as well, like point lying on an edge, coinciding with given point, etc. For full details check the link.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.