Algorithm for testing intersection of point and compound polygon

[Physt]

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 edge-based 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?

 

[meldraft]

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.

 

[jim mcnamara]

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/

 

[Physt]

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.

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/

Thanks for the suggestions, I ended up solving this in the case of convex, concave and complex compound-polygons as follows if anyone is interested:

Cast a ray starting at the point being tested to the mid-point of each edge (drawing through a virtual line-segment at the start and end points of each edge, not following the arc/elliptical-arc if one exists) and count the number of intersections after merging any intersecting points and line-segments of the detected intersections into a single line-segment and thereby counting it as a single intersection. If all intersection counts are odd and non-zero the point is inside the compound-polygon, 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 compound-polygon and [rectangle,polygon,compound-polygon] intersections now) - the first two should be relatively simple (already have polygon-[arc,elliptical-arc,circle,ellipse-rectangle] intersection code written in a similarly mutable and accurate manner) but the compound-polygon/compound-polygon intersections might be a bit of a chore.

Again, thanks for the tips.