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.


Copyright 1999-2008 (C) FLIPCODE.COM and/or the original content author(s). All rights reserved.
Please read our Terms, Conditions, and Privacy information.