Find polygons from set of lines

Question

I'm working in 2D.

My user can draw some lines & line-segments, which I store in a custom object class, but basically in startX-Y & endX-Y.

Now I want to find, actually only the polygon where the ball is inside, but after reading and researching about some algoirthms etc. I think I have to find all polygons and serach after that the right one.

Is there anyone with some example code, c#, java objective-c !? I tried several times with some pseudo-code explanations, I don't get it.

Answer 1

Overview

There are a number of different interesting questions at play here:

1. Given you have a set of lines on the screen, and the user places their finger from an arbitrary point and drags it to an arbitrary end point, we need to form a new line which does not cross over lines and where the start and end point actually lie on existing lines or on borders.

2. The next question is how do we maintain an active set of "relevant" line segments which form the convex hull which the ball resides in.

3. Finally given we have an active set of line segments how do we find the area of this shape.

Now It seems you've already answered part 1. So we focus on parts 2 and 3.

For part 2, we will also be interested in asking:

4. If we have a convex hull and a point, how do we determine if that point is in the hull.

We refer to here for the solution to 4 Find if a point is inside a convex hull for a set of points without computing the hull itself

The full implementation can be done efficiently if you are careful with the data structures you are using. This is left as a simple exercise. Let me know if I have done something incorrect here or you do not understand something. I look forward to playing your game when its ready!

Solution to Part 3

In fact 3 is easy from 2, since if we know the active set of line segments containing the ball (this is a list of pairs of tuples ((x_1start,y_1start), (x_1end, y1_end))), there are two ways to compute the area. The first is to do a straightforward algorithm to compute the area of the convex hull formed by all start and end points in this list of tuples. Look up more sophisticated algorithms for area, but if you cannot find one, note that the hull with n sides has n-2 non-overlapping triangles, and the area of triangles is easy to compute (http://www.mathopenref.com/polygontriangles.html). Note:

area = abs((x1-x2)*(y1-y3)-(y1-y2)*(x1-x3)) for triangle (x1,y1)(x2,y2)(x3,y3)

Now if you sort all (x,y) points by their angle about the positive x axis, then we simply fix the first point, and consecutively walk through the remaining pairs and find the areas of those triangles. Left as an easy exercise why this sorting step is required (hint: draw a picture).

Solution to Part 2

Now the tough part is 2. Given that we have an active set of line segments enclosing the ball, how do we add a new line, and then adjust the size and number of line segments inside our active set. Note that at the beginning of the game there are precisely 4 lines in the active set which are the borders of the screen (this will be our base case if you like induction).

Now suppose we have an arbitrary active set containing the ball, and the user adds a new line, we assume it hits exactly two existing line segments and does not cross any line segments (by part 1 algorithm). Now we need to modify the active set. By algorithm 1, we know which line segments are hit by this point. So the only way that the active set can change is if both line segments hit by this point are in the active set (draw a picture to see this fact).

Now assume that the new line segment hits two lines inside the active set (this means it essentially splits the active set into two convex hulls). If we maintain our active set in a rotated order (that is to say we ensure that it is always sorted by angle about the positive x axis), we simply need to add our new points in a way that maintains this sorted ordering. So for instance suppose our points of the active set (collapsing line segments to single lines) are:

[(x1, y1), (x2, y2), (x3, y3), ..., (xn, yn), (x1, y1)]

And we want to add the new line segment ((x', y'), (x'', y'')), and our new set looks like:

[(x1, y1), (x2, y2), (x', y'), (x3, y3), ..., (xn, yn), (x'', y''), (x1, y1)]

Then there are now two convex hulls that are formed:

1. [(x1, y1), (x2, y2), (x', y'), (x'', y''), (x1, y1)]
2. [(x', y'), (x3, y3), ..., (xn, yn), (x'', y'')]

So the only remaining question is which is our new active set. Simply use algorithm 4.

Data Structures for Part 2

First we need the classes line segment and point (im avoiding implementing things like equals, hashcode for simplicity):

class Point {
    public int x;
    public int y;
}

class LineSegment {
    public Point lineStart;
    public Point lineEnd;
}

Now we can represent our active set datastructure:

class ActiveSet {
    public List<Line> thesortedlist;
}

Now we first initialize our active set with four lines and denote the center of the screen as (0,0):

LineSegment TopBorder = new LineSegment(new Point(10, 10), new Point(-10, 10));
LineSegment LftBorder = new LineSegment(new Point(-10, 10), new Point(-10, -10));
LineSegment BtmBorder = new LineSegment(new Point(-10, -10), new Point(10, -10));
LineSegment RightBorder = new LineSegment(new Point(10, -10), new Point(10, 10));

ActiveSet activeset = new ActiveSet();
activeSet.theActiveLines.add(TopBorder);
activeSet.theActiveLines.add(LftBorder);
activeSet.theActiveLines.add(BtmBorder);
activeSet.theActiveLines.add(RightBorder);

Now say the user adds a line from point (0, 10) to (10, 0), so this is a diagonal (call it newSegment) and the new active set will look like:

------
-     -
-       -
-        -
-         -
-         -
-  B      -
-         -
-----------

Note the cut in the upper right corner, and B denotes the ball. Now by algorithm 1 we know that lines TopBorder and RightBorder are hit. Now both of these are inside the activeset (we can test membership faster by using a hashmap). Now we need to form two activesets as follows:

ActiveSet activesetLeft = new ActiveSet();
ActiveSet activesetRight = new ActiveSet();

Now in order to build these sets proceed as follows:

List<LineSegment> leftsegments = activeset.GetSegmentsBetween(TopBorder,
                                                              RightBorder);

List<RightSegment> rightsegments = activeset.GetSegmentsBetween(RightBorder,
                                                                TopBorder);

This function GetSegmentsBetween(LineSegment firstline, LineSegment secondline) should just locate firstline in the list and then return all elements until it finds secondline (this may need to do two passes through the list). It should not include these firstline or secondline in its return value. Now suppose we have activesetLeft and activesetright, we need to do the following:

activesetLeft.append(new Line(secondLine.lineStart, newSegment.lineStart));
activesetLeft.append(newSegment);
activesetLeft.append(new Line(newSegment.lineEnd, firstLine.lineEnd));

activesetRight.append(new Line(firstLine.lineStart, newSegment.lineEnd));
activesetRight.append(new Line(newSegment.lineEnd, newSegment.lineStart));
activesetRight.append(new Line(newSegment.lineStart, secondLine.lineEnd)); 

It is really hard to understand in code, but the order of everything above is important, sicne we want to maintain sorted going in counterclockwise order.

It is left as an exercise how you can speed this up (in fact you dont need to build two active sets, just first figure out if the ball is above or below the new segment and build the left or right activeset accordingly).