Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there an easy and fast way of checking if a polygon is self-intersecting?

I have a System.Windows.Shapes.Polygon object, whose layout is determined completely by a series of points. I need to determine if this polygon is self-intersecting, i.e., if any of the sides of the polygon intersect any of the other sides at a point which is not a vertex.

Is there an easy/fast way to compute this?

like image 762
GWLlosa Avatar asked Feb 02 '11 15:02

GWLlosa


People also ask

Is polygon self-intersecting?

A polygon can be self-intersecting, meaning edges cross other edges. (The points of intersection are not vertices.) Regular polygons which are not self-intersecting are identified by an integer corresponding to the number of sides (or vertices) it contains.

Which polygon doesn't have self-intersecting sides?

A scalene polygon. Scalene means all sides are different lengths, so there will be no congruent sides.

How do you know if a polygon is simple?

In geometry, a simple polygon /ˈpɒlɪɡɒn/ is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments or "sides" that are joined pairwise to form a single closed path. If the sides intersect then the polygon is not simple.

What is a intersecting polygon?

Self-intersecting polygons, crossed polygons, or self-crossing polygons are polygons some of whose edges cross each other. They contrast with simple polygons, whose edges never cross. Some types of self-intersecting polygons are: the crossed quadrilateral, with four edges.


1 Answers

  • Easy, slow, low memory footprint: compare each segment against all others and check for intersections. Complexity O(n2).

  • Slightly faster, medium memory footprint (modified version of above): store edges in spatial "buckets", then perform above algorithm on per-bucket basis. Complexity O(n2 / m) for m buckets (assuming uniform distribution).

  • Fast & high memory footprint: use a spatial hash function to split edges into buckets. Check for collisions. Complexity O(n).

  • Fast & low memory footprint: use a sweep-line algorithm, such as the one described here (or here). Complexity O(n log n)

The last is my favorite as it has good speed - memory balance, especially the Bentley-Ottmann algorithm. Implementation isn't too complicated either.

like image 105
Daniel Gehriger Avatar answered Sep 20 '22 19:09

Daniel Gehriger