# Thread: Drawing the outer boundary of a polygon

1. Registered User
Join Date
Apr 2010
Location
Oslo, Norway
Posts
89

## Drawing the outer boundary of a polygon

I have a set of 3-n points in 2D in a coordinate-system, and I need to draw lines between them to form the outer boundary. The whole point is to avoid the lines crossing, avoiding the typical figure-8 shapes.
Does anyone know a way to order my coordinates in such a way that I can draw one line from one to the next all the way through without crossing paths?
I already have an array like
points[0].x=100;
points[0].y=125;
points[1].x=60;
points[1].y=50;
points[2].x=513;
points[2].y=915;
points[3].x=35;
points[3].y=107;

If it matters, all coordinates have a range of 0-1023.

Any takers?

2. Two thoughts.

First: If you're looking to follow the path as given, but correct for overlaps in some way, for each path, generate the equation for the line, and look for common points across all other lines segments in the polygon. If a common point is found, aside from the endpoint, insert the common point as a new point and remove all points between the point before the point that introduces the collision and the 2nd point of the line you collided with ... I think.

Suppose you have these lines:
AB
BC
CD
DE
EF
FA

And suppose DE introduces an overlap with BC. The overlap point, which we'll call X, then replaces "the point before the point" that introduces the problem, backtracking to the 2nd point in the line it collided with. So, we remove C and D. And we have:
AB
BX
XE
EF
FA

See:
https://docs.google.com/drawings/d/1...xfMbPo7IA/edit

Second: Convert each point into polar coordinates, indexing by theta as you go, and just connect the points in order of theta.

EDITS IN ORANGE
Last edited by svidgen; 03-28-2012 at 03:41 PM.

3. Registered User
Join Date
Apr 2010
Location
Oslo, Norway
Posts
89
Second: Convert each point into polar coordinates, indexing by theta as you go, and just connect the points in order of theta.

Indexing by Theta? I dont follow you, what is Theta?The angular coordinate or the radial coordinate? Or is Theta a function of the two?

4. Angular. Sorry if that's not commonly referred to using theta. It's been years since I've seen this stuff.

5. Registered User
Join Date
Apr 2010
Location
Oslo, Norway
Posts
89
Well, regardless of which terms are commonly referred to as theta or not, I must thank you for pointing me in the right direction. I have never before done ANYTHING like this, not even heard about Polar Coordinates before, but the result now is that it did the trick perfectly!

So thank you

#### Thread Information

##### Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•