Converting lines to polygons

I have a set of 2D lines that make up one or more polygons (which can share sides). Can anyone describe an algorithm that will give me the polygon vertices?
LVL 1
JamieRAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

bcladdCommented:
Coplanar lines are either coincident, parallel, or they intersect at a point. Assume you have the slope-intercept form of the line: the lines are coincident if the slope and intercept are the same. They are parallel if the slope is the same and they are not coincident. They intersect if they are neither of the above and the point of intersection is the point that satisfies the two simultaneous equations

  y = m*x + b
  y = n*x + c

where m,n are slopes and b,c are intercepts.

The union of the pair-wise intersection points of the lines is the collection of all of the vertices of all of the polygons formed by the lines.

Hope this helps, -bcl
0
ozoCommented:
How is your set of 2D lines represented?
0
JamieRAuthor Commented:
Each line is represented by it's two end points - a pair of (x, y) co-ordinates.

I'm nearly there I think. Each point (that potentially comprises a polygon) has two or more lines associated with it. Basically I navigate around each point always turning left (taking the line with the smallest relative angle). Once I reach the start point I output a polygon comprisied of each point visited. I only allow one journey down each line (in both directions) for dealing with polygons that overlap.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

ozoCommented:
That could work.   Do any of the lines intersect other than at their end points?  Can polygons that "overlap" share more than their borders?  
0
JamieRAuthor Commented:
Yes, two polygons can share one or more sides.
0
ozoCommented:
Sharing sides should pose no problem.  I was wondering if they could share area.
0
JamieRAuthor Commented:
Yes they can. I don't think this poses a problem either, but I'd be interested in your train of thought.
0
ozoCommented:
Actually I was wondering if you'd need to trace vertices of your polygons not in your list of endpoints but formed by the intersection of two of your line segments.
0
NetminderCommented:
Points (250) refunded and question closed.

Netminder
EE Admin
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Game Programming

From novice to tech pro — start learning today.