PDA

View Full Version : polygons formed by lines



jxu
03-22-2001, 07:33 AM
Does anybody know how to do the following:
-- Given a set of lines in 2d space.
-- Get all enclosed polygons formed by these lines. Vertices of these polygons are the intersection points of these lines.

Please show the algorithm or point to right web site. Thanks.

ikk_flip
03-22-2001, 10:26 PM
I think I'm getting at what you were trying to say. UT tried their hand at that by making the Experimental 2D shape editor. But it was mostly a 2d poly, but through some nice extrusion processes, it could transform them into 3d polys. Don't attempt to create 3d objects out of 2d objects direct, it's impossible. Instead, extrude them, like the Unreal team did in their Unreal Editor.

Korval
03-22-2001, 10:39 PM
I think jxu wants something more along the lines of a selection tool. Like selecting all the polygons inside a square the user draws, only it is an arbituarily defined shape.

What you'll have to do, jxu, is project all the vertices in question into screen space and find the vertices that are enclosed within the shape. Then, from that, keep the polygons whose vertices are inside the enclosed space (this may vary depending on whether or not you want partial polygons as well).

jxu
03-23-2001, 04:43 AM
Thanks for both ikk_flip and Korval. However, neither of you answered my question. Maybe my question was not phrased clearly. Basically, I only have the data for these lines, but have no data for polygons. I need to construct all the enclosed polygons based on these lines. (Think of these lines as beams of a building floor and the enclosed polygons as parts of area . I need to apply the floor loads to these beams.)

DaViper
03-23-2001, 04:47 AM
do you have the eqatuins of the lines in coord system, or just basically some kind of model with these lines?

jxu
03-23-2001, 05:27 AM
I have end points' coordinates of these lines. These end points are to be the vertices of the polygons. Thanks.

DFrey
03-23-2001, 05:55 AM
Question, how many polygons do you see in the following image?
http://personal.lig.bellsouth.net/~dfrey/lines_dark.gif

3 or 5? How many do you want to see?

[This message has been edited by DFrey (edited 03-23-2001).]

jxu
03-23-2001, 07:13 AM
Thanks DFrey.
For the problem I am to solve, I see 3 polygons. Polygons formed out of these lines do not include the overlapped ones.

DFrey
03-23-2001, 07:47 AM
Ok, good, that makes it a bit easier as it eliminates concave polygons which can be a pain to deal with. You should notice that in this case each edge can at most be shared by two polygons (assuming none of the lines are colinear). And if you traverse all polygons in a single given order (all counter-clockwise or all clockwise) then that means each edge can at most contribute to a polygon in either a positive direction, or a negative direction, or both if shared between two polygons. So the idea is to eliminate edges and end points by finding the smallest polygons they bound. You can pick any of the edges then going in the positive direction, find the next edge adjacent to it that produces the smallest angle between the two. The edge that forms the smallest angle and turns in the positive direction is the next edge. You keep repeating this until you arrive at the first endpoint of the first edge (thus identifying the winding of a polygon). All the while incrementing each edge as having been traversed once. If an edge's count reaches two, that edge can be removed from the set of edges to consider. The whole process is repeated until all edges are exhausted.
There is one other case in which an edge can be removed from the set of edges. If either endpoint is a member of only one edge (because of other edges being removed earlier), then that edge can also be removed even though its count may not be two. Also note, that removing one edge may lead to other edges that can be removed.

[This message has been edited by DFrey (edited 03-23-2001).]

Kilam Malik
03-23-2001, 08:25 AM
Originally posted by DFrey:
There is one other case in which an edge can be removed from the set of edges. If either endpoint is a member of only one edge (because of other edges being removed earlier), then that edge can also be removed even though its count may not be two. Also note, that removing one edge may lead to other edges that can be removed.


... and you have to walk back all edges which have such a dead end until you can continue with the next higher angle.

jxu
03-23-2001, 10:53 AM
Thank you all very much, especially to DFrey. It is a great help to me. By the way, do you guys have a good computational geometry book to recommend, the one that our current topic might be discussed.