Algorithm for testing intersection of point and compound polygon

In summary, the conversation discusses different methods for testing whether a point lies inside a compound polygon consisting of line segments, arcs, and elliptical arcs. The suggested solutions include calculating the areas of triangles using the cross product and counting the number of intersections of a ray cast from the test point to the edges of the polygon. The final solution involves casting a ray from the test point to the mid-point of each edge and counting the number of intersections, with all odd and non-zero counts indicating the point is inside the polygon. The conversation also mentions working on optimizing the algorithm for compound-polygon and rectangle-polygon intersections.
  • #1
Physt
49
1
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?
 
Physics news on Phys.org
  • #2
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
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
meldraft said:
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 said:
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.
 
  • #5


There are a few different approaches that could potentially be used to test the intersection of a point and a compound polygon. One option would be to use a ray casting algorithm, as mentioned in the question, which involves casting rays from the test point and counting the number of intersections with the edges of the polygon. This method can be efficient, but as the question mentions, it may not be the most elegant solution.

Another approach could be to use a point-in-polygon algorithm that takes into account the different types of edges in the compound polygon (line segments, arcs, elliptical arcs). This could involve breaking down the compound polygon into simpler shapes (such as triangles) and using existing point-in-polygon algorithms for those shapes. However, this may not be the most efficient solution depending on the complexity of the compound polygon.

A third option could be to use a spatial data structure, such as a quadtree or a k-d tree, to efficiently store and query the edges of the compound polygon. This would allow for a more optimized search for potential intersections with the test point, rather than checking every edge individually.

Ultimately, the best solution will depend on the specific characteristics of the compound polygon and the performance requirements of the application. It may be helpful to experiment with different approaches and compare their efficiency in order to determine the most suitable method for the given problem.
 

What is an algorithm for testing intersection of point and compound polygon?

An algorithm for testing intersection of point and compound polygon is a set of steps or rules used to determine if a given point lies within or outside of a compound polygon, which is a polygon made up of multiple polygons.

Why is it important to have an algorithm for testing intersection of point and compound polygon?

Having an algorithm for testing intersection of point and compound polygon allows for accurate and efficient determination of whether a point lies within or outside of a compound polygon. This can be useful in various applications such as map navigation, computer graphics, and geometric calculations.

What are the steps involved in the algorithm for testing intersection of point and compound polygon?

The steps involved in the algorithm for testing intersection of point and compound polygon typically include checking if the point is inside any of the polygons that make up the compound polygon, and if it is, checking if it is on the edge or vertex of the polygon. If not, the algorithm will move on to check the next polygon until a determination is made.

How accurate is the algorithm for testing intersection of point and compound polygon?

The accuracy of the algorithm for testing intersection of point and compound polygon depends on the precision of the calculations and the complexity of the compound polygon. With proper implementation and consideration of edge cases, the algorithm can provide accurate results.

Are there any limitations to the algorithm for testing intersection of point and compound polygon?

Yes, there can be limitations to the algorithm for testing intersection of point and compound polygon. For example, the algorithm may not work properly if the compound polygon is self-intersecting or has overlapping polygons. Additionally, the algorithm may not be suitable for very large or highly complex compound polygons.

Similar threads

Replies
1
Views
3K
  • General Math
Replies
7
Views
2K
  • STEM Academic Advising
Replies
13
Views
2K
  • Poll
  • Science and Math Textbooks
Replies
2
Views
5K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
5K
  • Astronomy and Astrophysics
2
Replies
45
Views
81K
Replies
15
Views
38K
Back
Top