Re: Extracting polygons from a given set of lines
- From: Kenneth Sloan <KennethRSloan@xxxxxxxxx>
- Date: Thu, 01 Jan 2009 18:14:37 -0600
ivan wrote:
hi,
is there an algorithm that you could recommend, which could extract
all polygons from a given set of lines?
polygons are 2D quads. to be precise, we could define them as a part
of the surface enclosed by four different lines from each side (each
line can be longer than the coresponding side of a quad).
here's an image to clarify what i mean:
http://www.nequamstudios.com/ivan/poligoni.jpg
('lines' are drawn in thin green, and polygons in thick blue. there
are exactly 3 polygons in this picture: two smaller ones, and a big
one the size of both of them)
i've written a function that does what i need, but the algorithm
complexity is far too great, and thus isn't practical for almost any
use (O(n^4)).
so that's why i need to know if there's anything that i can search for
to help me... :-)
thanks,
ivan
Looks like a job for Sweepline:
use a Priority Queue to hold Vertices and process each vertex from
bottom to top of your environment
Initially, load the PQ with the LOWER endpoint of each line segment (Note: figure out how to handle horizontal lines). Then, start processing vertices in the PQ as follows:
When you process the LOWER endpoint of each line:
a) make the line segment ACTIVE
b) look for intersections of this line segment with all other ACTIVE
line segments (insert those intersections into the PQ)
When you process an intersection:
a) CLOSE the polygon below the intersection (if there is one)
b) OPEN a new polygon above the intersection (you don't know if this
polygon will complete, or not
When you process the UPPER endpoint of each line:
a) make the line segment INACTIVE
When the PQ is empty - discard all of the open polygons
Note that I have assumed that an intersection will never be exactly AT a line segment endpoint. If that can happen - figure out how to handle it.
For well-behaved scenes, this should be <<O(n^4).
--
Kenneth Sloan KennethRSloan@xxxxxxxxx
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/
.
- Follow-Ups:
- References:
- Prev by Date: Extracting polygons from a given set of lines
- Next by Date: Re: Extracting polygons from a given set of lines
- Previous by thread: Extracting polygons from a given set of lines
- Next by thread: Re: Extracting polygons from a given set of lines
- Index(es):
Relevant Pages
|
Loading
