Path finding

First, pick a direction for all your turns, either clockwise or counter-clockwise.

Extend a ray from the selected point out somewhere. Eventually you'll hit a line.

Turn and follow that line until you hit your first intersection.

Do {
Turn the direction you picked at first until you hit another line
Record the vertex
Follow line to next intersection
} while ( not at starting point )


done.

You'll need to add error checking for cases where the polygon isn't closed, where two lines are colinear, and any other weird cases your teacher data set may require.

frob.

ok, i see how to pick a direction and follow the polygon lines in that direction, but how would i find an intersection? whould i incriment across the line little by little to find one? or what?

Quote:

Original post by EvilKnuckles666 ok, i see how to pick a direction and follow the polygon lines in that direction, but how would i find an intersection? whould i incriment across the line little by little to find one? or what?

You said in your first post that you are given a set of Points and the Lines that connect them.
Two Lines intersect when they both share the same Point.

So you already have a listing of all Possible intersections. It's just a matter of searching through them.
Or if you want to be clever about it, assemble a Graph of Points connected by Lines and do some transversal stuff. Tho brute force list searching is probably OK based on the size of your example drawing.

P.S. Homework?

It might not be that simple. Take a look at the green circles where the lines intersect:



If the red lines don't have points at those intersections, then you won't be able to detect them just checking for equal points. You'll need to first find possible intersection points between lines and subdivide them. Use a parametized line intersection algorithm for this, internet resources on the topic are abound.

It also appears you're performing what is known as flood filling. Although your assignment is to find the bounding polygon and not actually perform the filling, in many cases that's probably as extra step that makes the problem more difficult since a lot of flood filling algorithms will implicitely determine the bounding shape just by filling it in.

this isn't homework, it's a project the company i'm working for is trying to figure out.

I can find the path of any polygon, what's the part i need help on is places where more lines intersect at one point (ex: the green circles Zipster has made), how would i go about figuring which line to follow and make sure it is the one that only filles in the closed area and not through any other lines.

As a first step, you need to perform the subdivision I mentioned in my first post to create those points where lines intersect at non-endpoints. Otherwise you don't be able to detect them. This process itself can be tricky because as you split lines you create more lines, and to do this efficiently you don't want to perform redundant intersection checks. For simple objects you might be able to get away with checking each line against every other line, and if there's an intersection splitting the line and replacing the old line with the two new lines. Theoretically it's an (I believe) O(n³) worst-case approach, but unless you're dealing with complex shapes with many intersections and hundreds of lines you should be fine.

As for determining which line to follow when you actually reach one of these intersections, it depends on which way the lines have been turning before you arrived there. After you finish walking the very first line, the second line will either "turn" left or right relative to the line you just finished traveling. You want to store this direction as you walk the rest of the lines, and it won't change as only the first two lines determine the overall turn. If you immediately reach an intersection after the first line (before you can determine a turn direction), then turn in the direction of the fill point (where you will start flood filling from). When you reach an intersection, always chose the line that turns the most in the stored direction. For instance, if you were turning left, then always chose the line that turns most to the left at an intersection. I haven't fully tested the algorithm but it sounds as though it would work.

ah, yes. thanks, that makes sense. i'll work on that, see how it goes.

OK, I have a very good solution to this, but with a little thought I've given it until now, it seems that it will require to do a precalculation on your data... or else it may be slow for realtime use. Is the data (vertices' positions and adjacency) static? Or they are created dynamically? And how many polygons are we looking at? average?

If I'm not mistaken, you want to be able to determine the smallest polygon that contains the point that determines where you must start filling.

1st way) The fastest way is to use extra memory, a buffer, to define an identical region as the one in which your original polygons are drawn. In the first step, iterate through all your polygons and draw them filled, using a constant color value ==1, but draw them additevely! In the end, reiterate through all the polygons, find their centroid, and read the color value at those positions from the buffer. That value is exactly how many polygons contain that specific one (minus one), and is a direct measure of how deeply "nested" that polygon is, within others. Now order the polygons in a list using this depth value. (smaller first)
Clear that buffer, and using the order you just found, iterate through all polygons, and draw them in the buffer using a unique color value for each one. When you click somewhere to start filling, simply read the color value at that position from the buffer and you'll read the id of the polygon you should fill. You can even halven the buffer's resolution with respect to the original dimensions and save 75% memory. It shouldn't be a problem.
I suppose you can draw on another DC somewhere off screen...

2nd way) This is the solution I was talking about in my previous reply. It's a concept of complex calculus. It's gonna be long but I think it's worth it. (imho)
The key in this approach is that you can find whether a test-point lies in any connected subset of the 2d plane, by integrating a function of the vector from that point, that sweeps the entire boundary of the subset. The resulting number should be real for finite subsets of the 2d plane and -simply put- it is the number of revolutions that a viewer (located at the test-point) must perform in order to keep looking at a 'vehicle' moving on the boundary of the set, in the direction given by its parametric form. It is called the 'winding number' of the set's boundary with respect to the test point and -as you can easily verify- it will be non-zero for all points that belong to that set, and zero for all points outside it. Thus it can provide means for determing whether a point lies within any area, as long as you have a parametric form for it, -or at least- be able to describe is a sum of parametric equations. In your case, these equations will be the line segments for the polys, and I believe the integration will be very fast since their parametric forms are the simplest possible (not to mention their derivatives!)

It breaks down to this:
1) Iterate through all polygons, and for each edge, find its parametric form with parameter 't' varying in {0,...,1}. This is:
c(t) = {x(t),y(t)} = startPoint + t*(endPoint - startPoint)

2) Find the contour integral of the complex function 1/(z-z0) over the boundary of the polygon, where z=x+iy and z0 is the test-point (x0,y0) in form z0 = x0+iy0.
To find the integral for the whole polygon, simply add the sums of the very same contour integral over each line segment.
For integration variables x,y this one gets down to adding all the quantities (for all edges 1 to j in the polygon):
TmpResult += IntegralOverLineSegment#j[ (x-x0)/( sqr(x-x0)+sqr(y-y0) )]dy, and
TmpResult -= IntegralOverLineSegment#j[ (y-y0)/( sqr(x-x0)+sqr(y-y0) )]dx

The integration limits are still 0 and 1, in both cases

3) Divide the total sum by 2pi

4) That is the winding number. If that number is non zero, the test point lies within your polygon. (In fact, given the parametric forms for the line segments, it should +1 or -1 for ccw or cw order of traversal) Meaning that the sweep vector from the test point performs one rotation around its head while traversing the polygon.

This is very powerful! I've seen this change values from 0 to like -10 for infitesimal changes in the test-point! And the best part is that it doesn't only work for polygons, *it works for any shape you can express as a sum of parametric equations*. If you want me to clarify any point in the whole process, I'd be happy to help. It's just a little difficult to make my point without any pictures or mathematical notation.

I better put an end here in case I have trouble with post length...

edit:
couple of clarifications

[Edited by - someusername on December 15, 2005 5:31:14 AM]

Now, you want to find the winding number for the point where the user clicked, but which polygon should you test? (This is the part about precalculating data, that I was talking about) The raw approach would be to iterate through all polygons and find the winding number for each one! Of course this is highly inefficient and furthermore it is possible that more than one polygons yield a winding number == 0. (if some are contained within each other)

I have two suggestions. If your scene contains a big number of polygons contained within each other, (for example, there around n major polygons that contain roughly (100/n)% of all other polygons each) I suggest you keep track of those n polygons and -when the user clicks somewhere- first check whether the winding number for each of those polys is non-zero. If it is zero, it means that the point lies outside that specific 'major polygon' therefore it cannot lie within any lower level polygon that it contains! Thus you should be able to discard roughly (100*(n-1)/n)% of all polygons by finding (n-1) winding numbers.
It is far more optimal than the brute force approach.

If your scene doesn't contain deeply nested polygons, you can try another alternative.
Split your scene in a virtual nXn grid (5X5 should be just fine, but it also depends on average size of your polys) and keep a record of all polygons that have at least one vertex within each particular square. (This is easy to do)
When the user clicks somewhere, find the winding number for each square on the grid (remember it's merely 4 line segments), and then test only those polygons that have at least one vertex in that piece of the grid! (if there are more than one) Voila!

There's a bunch of optimizations you can do in all these. For example, in the last example, the line segments of each square, are shared with its surrounding 8 squares, you don't have to calculate them over and over. Or use existing vertices from all polygons to recursively define non-visible polygons that contain all the others. E.g. in the beginning, define 2 polygons P1,P2 that cover the entire area and contain roughly 50% of all polygons each. Then break each of those into two polygons, total 4, (P11,P12, P21,P22) each containing 25%. And so on. To test a point, test against P1,P2. If it is P2 that contains the point, continue testing with P21 and P22... and so on...

If you want to implement this, feel free to ask anything, I'll try to help as much as possible. In the meantime I'll see if I can find closed form equations for the integrals in that interval, mentioned in the previous reply. You may end up getting away with the integration afterall, but there may be a chance that something new (and bad) may show up (like the complex Log, or sth) and may require that you calculate it yourself... I don't know if it'll be worth the tradeoff. I suppose though, the numeric integration should be quite fast. For the simple line segments 30-40 steps in the interval should be just fine. I'll see what I can do.


edit:

Quote:

I wrote in this reply: When the user clicks somewhere, find the winding number for each square on the grid (remember it's merely 4 line segments), and then test only those polygons that have at least one vertex in that piece of the grid!

I must have been out of my head... of course you don't need to find the winding numbers of all squares in the grid! Just find those of the polygons that have vertices in that piece of the grid

[Edited by - someusername on December 15, 2005 7:59:21 PM]

What started out so innocent has seemed to have turned into an insurmountable problem requiring graph theory and integral calculus [smile]

The irony here is that the most robust way to get the bounding polygon is probably a flood-fill-based algorithm, only so that you can return the polygon so it can be flood-filled! Which is why I asked earlier if this intermediary step is absolutely necessary.

OK, this is it... I give up! I managed to solve the integrals I was talking about symbolically, over line segments, (in order to avoid the need for numeric integration) and I was trying to optimise the mathematic operations needed. After A LOT of factorization and some identities, I managed to strip the final result to this:

WindingNumber = 1/(2(sqr(x1-x2)+sqr(y1-y2)))*(y2-y1)*( 2*(atanAtOne - atanAtZero)*(y1-y2) - (x1-x2)*myLog ) - 1/(2(sqr(x1-x2)+sqr(y1-y2)))*(x1-x2)*(2*(atanAtOne - atanAtZero)*(x1-x2)+(y1-y2)*myLog )
WindingNumber /= 2PI;

( the 'atanAtOne', 'atanAtZero' and myLog variables were roughly one line each! )
At that time, I was quite content, because I realized how the logarithm (the only part of the result that could impose complex values) is cancelled out of the equation, and thus tried to find an even simpler form.
You want to see what it gets down to?

WindingNumber = atanAtZero - atanAtOne [attention]

This merely says that the number I was looking for, is the difference of the angles from the test point to the segment's startpoint (paremeter == 0) and endpoint (parameter == 1) , which is quite obvious and I should had used it by definition to begin with!!! I think I can listen to Homer Simpson in my head... (doh!)

We force our way of thinking to be so 'linear' (given our specific knowledge on a subject) that -even when the solution is *that* obvious- you won't see it until you bump onto it blindfolded!
(It hit me hard, I admit!)

Anyway, the function's not that fancy anymore :) but here it is.


edit:
forgot to divide by 2pi
edit2:
I had made a mistake in the return statement.

[Edited by - someusername on December 16, 2005 7:03:34 AM]

Quote:

Original post by Anonymous Poster Quote: Original post by Zipster For simple objects you might be able to get away with checking each line against every other line, and if there's an intersection splitting the line and replacing the old line with the two new lines. Theoretically it's an (I believe) O(n3) worst-case approach, but unless you're dealing with complex shapes with many intersections and hundreds of lines you should be fine. Bently-Ottmann sweepline algorithm has better asymptotic performance.

There is a theoretically optimal algorithm from Bernard Chazelle and Herbert Edelsbrunner here which is O(n lg n + k) in worst-case time complexity, and O(n + k) in worst-case space. The adversarial worst-case input is n lines that all cross each other. (The odds of this happening with n randomly placed lines of uniformly distributed lengths in (0, s) inside a square with sides s approaches 1/((n!)ⁿ).)

Unfortunately, the algorithm is quite complicated (the paper is 54 pages, most of which is devoted to a proof of correctness and then one of optimality), and it involves a very abstruse construction called the "magic box". Thankfully, the authors do provide a pseudocode implementation, but it takes a good deal of effort to understand why and how it works.

Quote:

Original post by kSquared There is a theoretically optimal algorithm from Bernard Chazelle and Herbert Edelsbrunner here which is O(n lg n + k) in worst-case time complexity, and O(n + k) in worst-case space. The adversarial worst-case input is n lines that all cross each other. (The odds of this happening with n randomly placed lines of uniformly distributed lengths in (0, s) inside a square with sides s approaches 1/((n!)n).) Unfortunately, the algorithm is quite complicated (the paper is 54 pages, most of which is devoted to a proof of correctness and then one of optimality), and it involves a very abstruse construction called the "magic box". Thankfully, the authors do provide a pseudocode implementation, but it takes a good deal of effort to understand why and how it works.

This is the problem with theoretical computational geometry, where all arithmetic is exact and the concern is about asymptotic order with out regards to the constant. In most cases, a simpler algorithm with less optimal asymptotic order will be easier to implement and perform reasonably well. For example, Bently-Ottmann is relatively easy to implement (modulo taking care of the floating-point arithmetic issues).

I wonder when Chazelle will make available pseudocode for his O(n) triangulation algorithm? ;)