Point-In-Nonconvex Polygon | Dataford Interview Questions

How would you determine if a given 2D point lies inside a complex, non-convex polygon?

Implement point_in_polygon(point, polygon), where point is [x, y] and polygon is an ordered list of vertices forming a simple polygon. Return true only for points strictly inside; points outside, on an edge, or on a vertex return false. Example: point [2, 2] in square [[0, 0], [4, 0], [4, 4], [0, 4]] returns true; point [4, 2] returns false. Use integer coordinates with 3 <= len(polygon) <= 5000 and assume the polygon is non-self-intersecting.

Constraints

3 <= len(polygon) <= 5000
Each vertex is an integer pair [x, y]
-10^9 <= x, y <= 10^9
The polygon is simple and vertices are listed in boundary order
The polygon has no zero-length edges
Points on edges or vertices are considered outside

Function Signature

def point_in_polygon(point, polygon):

Your question is Point-In-Nonconvex Polygon. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

How would you determine if a given 2D point lies inside a complex, non-convex polygon?

Constraints

3 <= len(polygon) <= 5000
Each vertex is an integer pair [x, y]
-10^9 <= x, y <= 10^9
The polygon is simple and vertices are listed in boundary order
The polygon has no zero-length edges
Points on edges or vertices are considered outside

Function Signature

def point_in_polygon(point, polygon):

Your question is Point-In-Nonconvex Polygon. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.