Article Preview

COLUMN

Polygon Hit Testing

Is a point inside a polygon?

Issue: 3.4 (March/April 2005)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 9,445
Starting Page Number: 34
Article Number: 3415
Resource File(s):

3415.zip Updated: 2013-03-11 19:07:58

Related Link(s): None

Excerpt of article text...

Hit testing -- that is, determining whether a point lies within an object -- is a recurring problem in many programs. Applications of hit testing can range from collision testing in games to deciding whether a mouse click lies within a user interface element. Such decisions are trivial for rectangular objects, and only slightly more complex for ovals, rounded rectangles, triangles, and other such regular shapes.

However, when it comes to determining whether a point lies inside an arbitrary, irregular shape, many people throw up their hands. While this is often a trivial determination for a human, who comes equipped with very complex visual computing hardware, telling a computer how to come to the same conclusion seems difficult. How is it done?

One oft-used solution involves storing an off screen bitmap image of the shape, in which black pixels lie inside the shape and white pixels lie outside. Hit-testing becomes as simple as checking the color of the pixel at the given point. However, this method can easily become impractical. For example, the shape may be defined at runtime, thus requiring that you figure out what pixels lie inside it anyway, in order to generate the pixel map. It seems that there must be another way.

If you can make the assumption that the shape is a polygon, consisting of a series of points defining the edges of the polygon, and that all the edges are straight lines, then there is an amazingly simple algorithm available to solve the problem. In human terms, you simply draw a straight line from the point outward until it is definitely outside the polygon. Then count the number of times it crosses a side of the polygon. If the line crosses polygon edges an even number of times, the point lies outside the polygon. If instead it crosses an odd number of times, the point is inside the polygon. Consider the complex polygon in Figure 1. Even a human would have a little trouble determining if the point was inside the polygon at first glance, but by counting the crossings of the vertical line drawn from that point, the determination becomes trivial.

The process of counting intersections is simple for a person with a picture to look at, but how does one tell a computer how to come to the same conclusions using nothing but a list of numeric coordinates? At first glance, this seems to involve some pretty complex decision making. However, in reality, there is a simple solution. A computer can easily make a large number of comparisons fairly quickly, thus a brute-force approach of evaluating each side of the polygon for intersection with an imaginary vertical line will work remarkably well.

Code to count the intersections would involve iterating over each edge in the polygon, comparing the x position of the point with the x positions of the endpoints of that edge. If the point does not lie horizontally between the endpoints, then it can safely be assumed that the vertical line cannot cross that edge. If, on the other hand, it does lie between the endpoints, then the code must examine the vertical position of the intersection point.

...End of Excerpt. Please purchase the magazine to read the full article.