Register to reply 
Algorithm for testing intersection of point and compound polygon 
Share this thread: 
#1
Nov1612, 05:52 PM

P: 17

I'm trying to find a reasonably fast method for testing whether or not a point (x,y euclidean coordinate system) lies inside a (preferably convex, concave or complex  though different methods for each would be OK) compound polygon with edges consisting of line segments, arcs and/or elliptical arcs (elliptical arcs may be rotated in addition to having a start and end angle). I've already written the algorithms for edge and volumetric intersections of Points, Lines, Rays, LineSegments, Arcs, EllipticalArcs, Circles, Ellipses, Rectangle, Polygons and every combination thereof (also edgebased intersections of CompoundPolygons)  so have plenty of algorithms to call from, however I would prefer something a bit cleaner than testing the number of hits along rays cast from the test point to all surrounding points if that can be avoided. Does anyone know of a better solution to this problem?



#2
Nov2012, 07:24 AM

P: 280

A way to do it would be to calculate the areas of all the triangles defined by that point and each two successive vertices. You can do this in an algorithm by using the cross product. If the point is inside the polygon, this sum will equal the area of the polygon, otherwise it will not. Since your polygon is convex, I'm pretty sure that this is guaranteed.



#3
Nov2012, 07:00 PM

Sci Advisor
PF Gold
P: 1,381

Assuming that the nodes of the polygon are given and each of the lines/arcs is defined by a function you can determine:
A decent algorithm is to compare the sides of the polygon to the Y (vertical) coordinate of the test point. Retain the x coordinate values. If the number of intersections is 2, then test the x coordinates of the intersections against the x coordinate of the point. This assumes that you have a function to generate the coordinate from the y coord using the nodes of the polygon. This is O(n) for the case line segments only, where n=nodes in the polygon. I've not tried it for what you are attempting. This is based on work by D R Finley. see: http://alienryderflex.com/polygon/ 


#4
Nov2412, 04:11 AM

P: 17

Algorithm for testing intersection of point and compound polygon
Cast a ray starting at the point being tested to the midpoint of each edge (drawing through a virtual linesegment at the start and end points of each edge, not following the arc/ellipticalarc if one exists) and count the number of intersections after merging any intersecting points and linesegments of the detected intersections into a single linesegment and thereby counting it as a single intersection. If all intersection counts are odd and nonzero the point is inside the compoundpolygon, otherwise it is outside. It may be slower than ideal, but I wanted to get the algorithm correct and move on to the next one before optimizing them all (working on the joys of compoundpolygon and [rectangle,polygon,compoundpolygon] intersections now)  the first two should be relatively simple (already have polygon[arc,ellipticalarc,circle,ellipserectangle] intersection code written in a similarly mutable and accurate manner) but the compoundpolygon/compoundpolygon intersections might be a bit of a chore. Again, thanks for the tips. 


Register to reply 
Related Discussions  
Algorithm for cutting a polygon into specific shapes  Differential Geometry  5  
Line intersection algorithm optimization  Engineering, Comp Sci, & Technology Homework  0  
Among the six measurements of the boiling point of a silsicon compound  Set Theory, Logic, Probability, Statistics  2  
Formula/Algorithm to apply force to an arbitrary point on a polygon  Classical Physics  15  
Testing a Lanczos (tridiagonalization) algorithm  Linear & Abstract Algebra  8 