Reputation: 11
In an arbitrary polygon, how do I detect freedom from intersection of any side by another?
I am drawing a polygon for the Traveling Salesman problem, and would like to test for non-intersection of any paths, as a means of adaptively halting the genetic search. I tried simply checking line segments or intersection, but sometimes I get an incorrect result, terminating the search even though one or more intersections remain.
Upvotes: 1
Views: 142
Answers (1)
Reputation: 16007
This problem is essentially equivalent to detecting intersections in an arbitrary set of line-segments.
For example, the bentley-ottmann algorithm can be used to solve this problem. Of course, you can terminate as soon as you find one intersection.
A naive check would just check every edge versus every other edge (that is not adjacent in the polygon, because those cannot intersect), but since you just need to find one intersection, the output-sensitive algorithms (like bentley-ottmann) can speed up your check quite a lot.
Upvotes: 1
Related Questions
- Determine if any 2D polygon (including convex or concave polygons) intersects with AABB bounding
- Is there an easy and fast way of checking if a polygon is self-intersecting?
- Detect 2 different cases of polygon self-intersection (intersection occurred inside or outside)
- How to test if a line intersects a convex polygon?
- How do I determine if two convex polygons intersect?
- How can I tell if two polygons intersect?
- How to efficiently test whether an arbitrary polygon intersects with a square?
- Algorithm to validate free polygon vertices for a non-intersecting shape
- How to detect if a polygon has self-intersections?
- How to determine if line intersect simple polygon?