6

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science.
Eventually this seemed more suitable.

Anyway, some background first:
A closed curve, is a curve with no endpoints and which completely encloses an area.
A simple curve, is a curve that does not cross itself.

Example:

enter image description here

Now, given n ordered (x,y) coordinates that represents mouse movement, it is easy to determine if they form a closed curve (given an upper bound on the allowed distance between two points, of-course), but is there an algorithm that will determine whether or not the coordinates form a simple curve?

I tried to look online for an answer, but couldn't find relevant solutions.

Community
  • 1
so.very.tired
  • 163
  • 1
  • 4
  • 2
    I'm fairly sure you could easily perform a O(n^2) algorithm that cross checks each line segment with each other line segment for an intersection. At that point, break and you know it is not simple. If it were closed, you'd simply have to check the start and end points as well. – Neil May 22 '15 at 10:01
  • I know that closed curve can be determined in O(1), and I also thought about what you suggested for determining "simpleness", I just can't see how to do it in polynomial time, let alone O(n^2). – so.very.tired May 22 '15 at 10:07
  • The idea is simple. You're guaranteed that there are two line segments between two points which intersect if it isn't simple. So you check every combination of two line segments O(n^2) to see if they intersect and if they don't, you know it is simple. There may even be a way to do it in better time than O(n^2). – Neil May 22 '15 at 10:14
  • I'll write an answer I suppose. One moment. – Neil May 22 '15 at 10:20
  • Polygon windinin as used to determine facing and fill type d graphics engines might have some methodology and such you can investigate: see http://www.angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/Types/PolyFillType.htm for examples of winding based fill and https://en.m.wikipedia.org/wiki/Winding_number for some more general concepts. – Weaver May 23 '15 at 01:04

3 Answers3

4

You could argue that a curve is simple if there are no two line segments between points such that the lines intersect, meaning you could check if a curve is simple by verifying the absence of this condition.

The algorithm would look something like:

for each p1, p2 in pointlist
  for each p3, p4 in pointlist
     if line_segment(p1, p2) intersects line_segment(p3, p4)
        return false
return true

Note that p2 would be the successive point after p1 and similarly, p4 would be the successive point after p3. In order to avoid redundancy, points p3 and p4 could start after points p1 and p2. This should be easily done in O(n^2) time. Be careful in your check for intersection since at least once the lines will be the same (no dividing by zero).

If you have many such points, you could skip every other point and this algorithm will run 4 times faster at the small risk that a truly intersecting line may not be detected should the curve approach a tangent.

Neil
  • 22,670
  • 45
  • 76
  • About your last remark: shouldn't it be 2 times faster? – so.very.tired May 22 '15 at 10:46
  • Your surely meant `for each p1, p2 in pointlist` where p2 is the direct sucessor of p1 and `for each p3, p4 in pointlist` where p3 is a successor of p2 and p4 is the direct successor of p3. – Doc Brown May 22 '15 at 10:50
  • @DocBrown No. If I did that, p3 and p4 would always be the next line segment, but yes in that p2 succeeds p1 and p4 succeeds p3. – Neil May 22 '15 at 11:00
  • @Neil: please read my comment again. I made a distiction between "sucessor" and "direct successor", you probably missed that. – Doc Brown May 22 '15 at 11:02
  • @DocBrown I see what you mean by that now. Altered answer. – Neil May 22 '15 at 11:04
  • @so.very.tired It should be 4 times faster, because everytime you're running through the list, you do so twice as fast, and this compounds with the nested loop. – Neil May 22 '15 at 12:24
3

You can check each point pair P[i],P[i+1] against each point pair P[j],P[j+1]

If any of the lines segments they create intersect then the curve is not simple.

Naively check each line:

for(int i = 0; i < n-3; i++)
    for(int j = i+2; j < n-1; j++)
        if(doIntersect(new Line(P[i],P[i+1]), new Line(P[j],P[j+1]));

I skip checking P[i],P[i+1] against P[i+1],P[i+2] because they always intersect on the endpoint P[i+1]

This algorithm can be sped up by sorting the list of segments by left most x and then only check lines that have an endpoint left of the rightmost x of the current segment.

ratchet freak
  • 25,706
  • 2
  • 62
  • 97
1

The concept may be simple, but there are many devilish details.

To begin with, you have to stipulate that the numbers representing the points are exact, not approximations to some real curve, and that the outline consists of straight line segments, not an actual curve.

Second, boundary conditions are everywhere; if line AB touches line DEF only at point E, does that count as a cross or not? You need to consider the overall geometry of the figure. Consider a "C" shaped figure with a pseudopod extending from the back, around to enter the "mouth" of the C, and now gradually close the jaws of the C to meet at a single point.

ddyer
  • 4,060
  • 15
  • 18