14
$\begingroup$

I'm looking for the algorithm that determines the fact that a polygon has self intersection or hasn't. I'm not needed in calculation of the intersection points coordinates or how many intersection points there are.

$\endgroup$
  • 1
    $\begingroup$ The naïve algorithm is to compare each pair of edges to see whether they overlap. Do you want an optimal algorithm or have any interesting constraints (e.g. polygon endpoints on lattice points)? $\endgroup$ – Peter Taylor Nov 10 '11 at 9:10
  • $\begingroup$ No special constraints. I only need a very fast algorithm for this task. $\endgroup$ – shadeglare Nov 10 '11 at 10:05
  • $\begingroup$ Posssible duplicate of math.stackexchange.com/questions/52733/… $\endgroup$ – lhf Nov 10 '11 at 10:16
10
$\begingroup$

There is the obvious algorithm of comparing all pairs of edges, which is $O(n^2)$ but probably is ok for small polygons. There is the Bentley–Ottmann algorithm sweep algorithm, which is $O(n \log n)$ but is harder to implement and probably only needed if $n$ is large. I think there is a $O(n)$ algorithm by Chazelle, which is very likely to be impractical.

In any case, note that you can test whether two line segments intersect without finding the intersection point. It's a simple matter of comparing signs of a few determinants. See http://algs4.cs.princeton.edu/91primitives/.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Is the Chazelle one this one? $\endgroup$ – LarsW Jan 21 '19 at 22:11
  • 1
    $\begingroup$ @LarsW, yes, that paper: An Optimal Algorithm for Intersecting Line Segments in the Plane, B. Chazelle, H. Edelsbrunner, Journal ACM 39 (1992), 1-54. $\endgroup$ – lhf Jan 21 '19 at 22:32
1
$\begingroup$

The Shamos-Hoey algorithm is designed for the task of simply reporting whether a polygon has self-intersections or not.

There is an excellent writeup in this blog and there are many implementations available (include my own in javascript which also includes the original PDF of the paper).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.