Identifying enclosed regions
Author
If I have several line segments (just lines for, but eventually curves too) how could I identify enclosed areas?
Okay, I made this up right now, so hopefully it works.
Okay, first you need to find all the intersections between lines (line segments, whatever). Something like:
Each intersection is the child of two lines touching at a point. Each line is given an int ID; So when you say a parent is '5', it really means its parent is the line with ID five (in some other array you have made). Also give each intersection an ID.
Okay, so now you just choose a random intersection. Call it "root". From this root node, find all other intersections that include the parents. From each of these nodes, find all the intersections that include those parents. From each of those child nodes, recurse backwards up the tree. If any of the previous nodes have an identical ID, you have found an enclosed area, and you can stop going to the children of that node.
Continue going from each node to all possible connecting nodes (one with one identical parent). Eventually you will create all possible enclosed areas.
If you count the number of nodes up until an identical node ID, you can even see what shape the enclosed area takes. 3 nodes up means a triangle, 4 a quadralateral, etc, etc.
Hopefully that made sense. Try drawing it on paper with like 3 or four lines. It should make sense there.
Fairly bruteforce, but again, I made it up on the spot.
Okay, first you need to find all the intersections between lines (line segments, whatever). Something like:
typedef line int;typedef struct _intersection{ vertex3 point; line parents[2]; int ID;} intersection;Each intersection is the child of two lines touching at a point. Each line is given an int ID; So when you say a parent is '5', it really means its parent is the line with ID five (in some other array you have made). Also give each intersection an ID.
Okay, so now you just choose a random intersection. Call it "root". From this root node, find all other intersections that include the parents. From each of these nodes, find all the intersections that include those parents. From each of those child nodes, recurse backwards up the tree. If any of the previous nodes have an identical ID, you have found an enclosed area, and you can stop going to the children of that node.
Continue going from each node to all possible connecting nodes (one with one identical parent). Eventually you will create all possible enclosed areas.
If you count the number of nodes up until an identical node ID, you can even see what shape the enclosed area takes. 3 nodes up means a triangle, 4 a quadralateral, etc, etc.
Hopefully that made sense. Try drawing it on paper with like 3 or four lines. It should make sense there.
Fairly bruteforce, but again, I made it up on the spot.
Anyone else have a better method for this? I cant get it out of my head, but I cant come up with anything less bruteforce...
just a wild guess...
maybe you could try something with Voronoi diagrams. The end points in the line segments are used to generate the diagram or maybe the center of the line segment.
or maybe you could adept the existing algorithm for voronoi diagram generation to your case.
maybe looking at this gives you more ideas.
maybe you could try something with Voronoi diagrams. The end points in the line segments are used to generate the diagram or maybe the center of the line segment.
or maybe you could adept the existing algorithm for voronoi diagram generation to your case.
maybe looking at this gives you more ideas.
Will the segments meet at start and end points only, like:
or will some overlap like this
|||||_________or will some overlap like this
| | --|----- |
It's easy IF you can access the verteces in a consistant order: say, clockwise, or counterclockwise. Just add up the signed areas under each segment.
More detail:
For now let's say that order is clockwise. Imagine an axis below the lowest vertex. Then, measure the area undereath the first segment. To help visualize, imagine that that segment is at the top of the figure, going from left to right. Now add the area under the next one, and so on. Now here's the catch that makes it work: curves that go from right to left have NEGATIVE areas.
You can switch everything and use a counterclowise order too, of course.
I think this works in all cases, but I'd need to think about it for a while to make sure. If it does indeed work, there's probably a formal proof out there somewhere.
More detail:
For now let's say that order is clockwise. Imagine an axis below the lowest vertex. Then, measure the area undereath the first segment. To help visualize, imagine that that segment is at the top of the figure, going from left to right. Now add the area under the next one, and so on. Now here's the catch that makes it work: curves that go from right to left have NEGATIVE areas.
You can switch everything and use a counterclowise order too, of course.
I think this works in all cases, but I'd need to think about it for a while to make sure. If it does indeed work, there's probably a formal proof out there somewhere.
Terran, I hate to sound ignorant, but how does that identify enclosed regions? All you seem to be doing is finding the total area of...something. What that something is...well, I have no freakin clue. :D
Author
ok thanks for the help so far, I think I figured it out based on visage's comments.
The first step in the algorithm would be to split up all intersecting lines into multiple, touching lines, this way we only have two cases: free floating lines and 'touching at the end points' lines.
then for each line x, we recursively traverse every line that touches its endpoint ON ONE SIDE, until we reach line x again, or until we reached an endpoint that doesnt continue.
If the recursion doesn't take us back to line x, then it is not an enclosed region.
This is done for every line in the scene.
Various optimizations can of course be done to remove certain lines from being examined again, however you gotta keep in mind that one line can be a part of 2 regions (at most), so you wouldn't want to disregard a line after finding it is a part of one region. Each line would be given a region counter that is incremented whenever it is found to be part of a region. Once that counter reaches 2, it can be safely removed from the set of lines, because the regions that it makes have already been identified. But even still, in most cases every line will be traversed with it being the top level line (x), hence when a region is identified, we should check whether it is a region thats already been found (when another line was x).
Thanks for the help!
The first step in the algorithm would be to split up all intersecting lines into multiple, touching lines, this way we only have two cases: free floating lines and 'touching at the end points' lines.
then for each line x, we recursively traverse every line that touches its endpoint ON ONE SIDE, until we reach line x again, or until we reached an endpoint that doesnt continue.
If the recursion doesn't take us back to line x, then it is not an enclosed region.
This is done for every line in the scene.
Various optimizations can of course be done to remove certain lines from being examined again, however you gotta keep in mind that one line can be a part of 2 regions (at most), so you wouldn't want to disregard a line after finding it is a part of one region. Each line would be given a region counter that is incremented whenever it is found to be part of a region. Once that counter reaches 2, it can be safely removed from the set of lines, because the regions that it makes have already been identified. But even still, in most cases every line will be traversed with it being the top level line (x), hence when a region is identified, we should check whether it is a region thats already been found (when another line was x).
Thanks for the help!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
