Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Converting lines to polygons

Posted on 2003-12-11
11
284 Views
Last Modified: 2010-04-07
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?
0
Comment
Question by:JamieR
11 Comments
 
LVL 11

Expert Comment

by:bcladd
ID: 9925267
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
 
LVL 84

Expert Comment

by:ozo
ID: 9933182
How is your set of 2D lines represented?
0
 
LVL 1

Author Comment

by:JamieR
ID: 9935427
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
Active Directory Webinar

We all know we need to protect and secure our privileges, but where to start? Join Experts Exchange and ManageEngine on Tuesday, April 11, 2017 10:00 AM PDT to learn how to track and secure privileged users in Active Directory.

 
LVL 84

Expert Comment

by:ozo
ID: 9954879
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
 
LVL 1

Author Comment

by:JamieR
ID: 9955787
Yes, two polygons can share one or more sides.
0
 
LVL 84

Expert Comment

by:ozo
ID: 9955846
Sharing sides should pose no problem.  I was wondering if they could share area.
0
 
LVL 1

Author Comment

by:JamieR
ID: 9955884
Yes they can. I don't think this poses a problem either, but I'd be interested in your train of thought.
0
 
LVL 84

Expert Comment

by:ozo
ID: 9955906
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
 
LVL 5

Accepted Solution

by:
Netminder earned 0 total points
ID: 10144470
Points (250) refunded and question closed.

Netminder
EE Admin
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
Two types of users will appreciate AOMEI Backupper Pro: 1 - Those with PCIe drives (and haven't found cloning software that works on them). 2 - Those who want a fast clone of their boot drive (no re-boots needed) and it can clone your drive wh…
With Secure Portal Encryption, the recipient is sent a link to their email address directing them to the email laundry delivery page. From there, the recipient will be required to enter a user name and password to enter the page. Once the recipient …

829 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question