Creating a polygon from a point set

[krukid]

Hi,

Sorry for the programming-style subject - I will bring it down to a geometrical problem further on.

Intro
I am a programmer and as such I know just enough about most Math, Geometry, Physics and so on to have my job done, but every now and then I get challenged with a task that requires me to dig into one of those areas. Today, however, I'm a little lost because I don't even know where to start. I'd appreciate if someone could point me in the right direction or any comments at all.

Task
There's a random set of points and I have to draw a polygon using all of those points so that every point has exactly two lines connected to it and none of the lines that are drawn intersect.

Purpose
In programming, a polygon is drawn as a sequence of lines connecting points given as an array: 1st-to-2nd, 2nd-to-3rd, ..., Nth-to-1st
This makes it possible, for example, to create an hourglass-shaped polygon with only 4 points supplied. The rule in "Task" section is aimed to ensure that, given points {(x, y): (0,0), (0,5), (5,0), (5,5)}, only a square can be formed.

Problem
Geometry-based solution I can think of would be to pick through the point set, drawing a line to another point that has 0 or 1 lines connected to it, but only if it won't prevent me from drawing non-intersecting lines in the future.
Thus, the problem I'm facing is: how can I find out that the line being drawn won't (or will) make it impossible to draw a non-intersecting line in the future?

Thanks.
-Victor

 

[wjm11]

Task
There's a random set of points and I have to draw a polygon using all of those points so that every point has exactly two lines connected to it and none of the lines that are drawn intersect.

Problem
Geometry-based solution I can think of would be to pick through the point set, drawing a line to another point that has 0 or 1 lines connected to it, but only if it won't prevent me to draw non-intersecting lines in the future.
Thus, the problem I'm facing is: how can I find out that the line being drawn won't (or will) make it impossible to draw a non-intersecting line in the future?

Comments:

Your “no intersection” approach implies testing for intersection between two lines but with a restricted domain. This would require that the equation for every possible line be calculated, followed by calculating intersections between lines, followed by checking if the intersection is in the domain of the line segment being tested. My guess is that this would not be an efficient algorithm.

An alternative approach might be to implement an “angular sweep” algorithm. It might work like this:

Pick an arbitrary starting point and make that your origin.
Calculate the angle from that starting point to all other points.
Connect the points in order of their angle sizes from the starting point.

Hope that helps.