Wednesday, October 10, 2007

New solutions to old problems - Point in Polygon

Some algorithms in computer graphics and topology never get a satisfactory solution that is both fast and logically simple to implement. One is line segment intersection , the other is the classic point-in-polygon (PIP) , fundamental to object selection / picking. I was attempting to make an implementation for World Wind for generic PolygonFeature picking.

Polygons rendered can be quite complex with holes and are curved to the earth's surface. 2D-topological solutions may not be adequate in all cases and DirectX based object selection may not be accurate. There are multiple strategies for PIP solution, here is the summary of a few:
1: Ray-Trace Test
2: Winding Number Test
3: Successive approximation using grids and bounding boxes
4: Triangle test

Not all strategies work for complex polygons(re-entrant,concave, with holes and what have you), and need to be carefully chosen for intended use and efficiency.

The strategy I am proposing for World Wind will be bounding box checks then rigorous checks using winding rule for holes and outer ring, that is if I don't get lazy and choose to use NTS instead, or just tag any quads being rendered using Direct-X ( filled polygons at altitude) and use DirectX picking.

No comments: