Flood algorithm - find polygon containing a given point.

Question

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this:

struct Point2D {
    float x, y;
}

struct LineSegments {
    Point2D[] Segments;
}

function Main {
    LineSegments[] lineChart;
    // ...
}

This code ensures that Segments are interconnected line segments and my Main has multiple of those.

I am supposed to write the code that, given a Point2D, find the region formed by lineChart that encloses this point:

The region would be composed by the vertices (Point2D) of the polygon formed by the lines. So I need help to 1) calculate the intersections between lines to create the polygons and 2) verify if the point is contained in some polygon.

Answer 1

Answering a clarified question. I will explain the potentially exponential timed way to do this.

You need to know what a graph is. You need to know what a cycle is.

1) Create an array of all the intersection points of all the line segments.

Given two line segments $a$ and $b$, defined by points $(x_{a1}, y_{a1})$, $(x_{a2}, y_{a2})$, $(x_{b1}, y_{b1})$ and $(x_{b2}, y_{b2})$, if their intersection point exists then it is $(x_i, y_i)$ given by solving the simultaneous equations: $$\frac {x_i - x_{a1}}{y_i - y_{a1}} = \frac {x_{a2} - x_{a1}}{y_{a2} - y_{a1}}$$

$$\frac {x_i - x_{b1}}{y_i - y_{b1}} = \frac {x_{b2} - x_{b1}}{y_{b2} - y_{b1}}$$

Then you want to check that $(x_i, y_i)$ is within the rectangle formed by corners of the line segments to see if the point actually exists. You probably want to store the 2 line segments that produced the point in the array as well.

2) Create a graph of those points

Create a graph with the vertices being the points calculated in step 1. Each point is produced by 2 line segments. Create an edge (in the graph) between two points iff they share a line segment that produced them.

3) Create an array of all of the cycles in the graph

Call this array $C_1$.

This is the potentially exponential step, since an arbitrary graph potentially has an exponential number of cycles. There are better ways to do this if you know how to use a vector cross product to traverse the graph in a clockwise (or counterclockwise) manner, but since your input seems to be user generated, this shouldn't be a problem.

4) Create an array of all the cycles containing your user selected point

Call this array $C_2$.

This will use the point-cycle algorithm I described in the other answer.

5) Determine the cycle among $C_2$ that doesn't contain another cycle

There will be 1 cycle that doesn't contain another cycle geometrically, call it $D$. For this problem, a cycle geometrically contains another if one of its points is inside the other cycle. Use the algorithm from the other answer, similar to step 4, and only check those points which are unique to one or the other cycle. Note that it is possible for two cycles to contain each other, but there will only be 1 smallest cycle (you can see this visually). If all of the points of one cycle are part of another cycle, then consider the first contained by the second.

6) Recreate your "mesh"

$D$ is the polygon you are trying to create. Connect it's line segments and store them. However, you also want to consider possible exclusions. Consider two concentric circles. The user might click within the outer circle, but not within the inner circle. A flood fill wouldn't fill in the inner circle.

7) Calculate exclusions

Let $C_3$ be the the subset of $C_1$ that:

• Each cycle in $C_3$ is contained by $D$
• Each cycle in $C_3$ does not contain your user point

Let $C_4$ be the set of cycles in $C_3$ that are not contained another cycle in $C_3$ (I believe Bertrand Russell had a paradox along these lines...haha). Each cycle in $C_4$ is one you do not want to fill in with a flood fill. You probably want to store these also.

Answer 2

This is one of the old odd-even algorithms.

For a given lineChart LC, you want to check how many times a horizontal line passing through your point intersects a line segment in LC. Corners count as intersecting twice.

In a closed polygon, you will intersect an even number of times. If an even number of intersection points are to the left (or to the right) of your point, you are outside the polygon. If an odd number of intersection points are to the left (or to the right) of your point, you are inside LC.

---

Calculating the intersection of a line and a horizontal line is easy, with a line segment you have to check that you are actually "within" the desginated bounds.

If your horizontal line is $y = y_p$ and your two points of the line segment are $(x_1, y_1)$ and $(x_2, y_2)$, first check: $$\min(y_1, y_2) \le y_p \le \max(y_1, y_2)$$ or else there is no intersection point.

Then check if $y_1 = y_2$, if so you can choose any point on the line segment as your intersection point, such as $(x_1, y_1)$.

Otherwise you need to calculate the intersection point, $(x_i, y_i)$, of 2 lines: $$\frac {x_i - x_1}{y_i - y_1} = \frac{x_2 - x_1}{y_2 - y_1}$$

and solve for $x_i$ given that obviously $y_i = y_p$.

---

Edit : I realize now that your LC do not form independent polygons. That leaves the problem of combining your line segments into a polygon, which I'm not sure how to direct you on without more information on what exact assumptions you can make about your line segments.

---

Edit 2 : I strongly suggest against using float/double in any application. There are very few mathematical assumptions you can make about the result of the computations with this datatype. Professional drawing algorithms will use integers with very carefully chosen floor/ceil divides (or modulus), but a beginner can use a rational datatype for equally visually attractive results without a noticable increase in computation time.