2D Polygon Selection
Question submitted by (20 October 1999)
|Return to The Archives|
|I have an engine that can handle concave polygons in all of the pipeline and rendering stages, but I can't figure out how to check if someone has clicked inside a concave polygon. By the way, the selction is done in wireframe, allowing both front AND back faces to be picked. It's easy if you have a convex poly, you just find the winding direction and see if the spot is to the left or right of all the edges. This doesn't work with concave faces, does it? Please help.|
The most popular method for this is to find the scan-line where the
user's point is. Find all the edges of the complex polygon that
intersect the scan-line and sort the intersection points from left-right
(or the other way, if you happen to be lexdysic.) Count the
intersections to the left (or right if you prefer.) If there are an odd
number of intersections on that side, then the point is inside the
polygon. Otherwise, it's not.
Response provided by Paul Nettle
This article was originally an entry in flipCode's Fountain of Knowledge, an open Question and Answer column that no longer exists.