how to determine if a line loops back on itself in 2d space, and finding points enclosed in that loop

Question

This is a problem which is hard to explain in words, though I have it easily captured in my head. Let me know if my explanation below isn't clear.

Let's say that a user is drawing on a 2d surface. They are drawing curves, with, say a mouse or stylus. Just so I'm clear on the definition, I'll say that a curve consists of a start-point (the point where the stylus is initially put down), intermediate points (points where the stylus dragged over) and an end point (the final point, where the user lifts the stylus off the surface).

How can I detect if the users curve creates some enclosed shape? For example, if you blur your eyes and look at the below drawings ( '.' denotes points on the curve, '0' denotes points not on the curve), the first one does create an enclosed space, the second one doesn't.

0000000000000000
0000..0000000000
000.00.000000000
00.000.000000000
00.00.0000000000
000...0000000000
0000000000000000

000.000000000000
0000.00000000000
00000.0000000000
00000...00000000
0000000.00000000
00000000.0000000
0000000000000000

Additionally, given some point (x1,y1), how can I determine if that point is inside or outside of the enclosed space?

Answer 1

For your second question:

the classical approach is to draw a line from x1,y1 to an edge of the screen and see how many times that line intersects your polygon. If the number is odd, its inside the shape, if its even then its outside. There are issues with the approach and single point edges, but I am sure you could find solutions/fixes online.

Answer 2

I gave +1 to Assaf but an alternative is to do some flood-filling, then check whether there are any points left in their original colour. Counting line-crossings is probably easier for vector artwork - the flood-fill approach may work better for bitmap graphics.

Answer 3

1) To detect if the path forms a loop, you could convert your points into a graph. You'll need to define your own heuristic to determine which points are connected by an edge ( For example, all adjacent points could be defined to be connected by an edge. Or, if your points are generated in a certain order, then consecutive points could be connected by an edge). Once you have your graph, you can google for a cycle detection algorithm to see if it makes a loop.

2) To determine which points are enclosed, you can take the points that comprise the loop and use them to define a polygon. Then google for a "point in polygon" algorithm and test all points within a certain range.