Anyone up for a CS/Math/Geometry challenge?

[bryce777]

Here's the problem:
Come up with an efficient algorithm to take a group of randomly placed points and create a simple polygon out of them.

I'll define a simple polygon as a collection of non-intersecting, closed line segments which have no 'holes' in them. So, a square or a pentagon is one, but a triangle with a hole in it isn't. A simple polygon can look like lots of things, though, even a picture of your cat if it is complex enough.

This was a problem I was given the other day, and I thought it was pretty neat, and the solution to it is even neater. I have a decent proof for it, but I need to have it looked at further to know for sure.
------------------
system specs:
Voodoo 5 5500 agp
tyan 1834d tiger 133 dual 800eb 133mhz FSB
via chipset 133 via apollo pro (don't make this mistake)
256 MB RAM
2 maxtor 60gig ata100 drives
promise ata100 controller
liteon 52 truex cdrom
Linksys ethernet 10/100
Soundblaster Live! (what's so exciting about it??) value edition
300watt power supply (inwin)
about 7 pounds of fans (I'm not kidding)
Suse 7.1(god gnome is crappy compared to CDE)/win2000 based system

[This message has been edited by bryce777 (edited September 26, 2001).]

[jester22c]

Not sure exaclty what kind of format you're looking for this in, if you're going to use it for programming or just theoretically.

Store a decimal variable in accending order to each point starting with (xmin,ymix) going up to (xmax,ymax). Now you will have a list of points from bottom left to top right. This gives you a simple order to work with. Start with var1 and find point with shortest distance. Now use which ever draw function and set the limits as the coordinates. Now do the same for var2, and so on through the chain.

------------------
--Proud member of the OT Forum - May it rest in peace.
--My software doesn't have bugs, it just develops random features.
--Error: Keyboard not attached. Press F1 to continue.

[hobbes2112]

This is very much related to a Matlab Demo called the Traveling Salesman. This is in response to a larger piece of work called the Traveling Salesman Problem.

This gets pretty heavy into optimization and neural networks. A quick search on any engine will find you lots of info.

This is one of the cooler sites out there: Traveling Salesman (http://www.cs.rutgers.edu/~chvatal/tsp.html)

If you have Matlab, or have access you can run the demo for yourself. I would post the source code, but I think it is copyrighted.

------------------
May we never see an old friend
With a new face.

[CaTaLyST]

i am moving this to the programming forum.

------------------
chosos@nmu.edu
ICQ: 2852628

[Galen of Edgewood]

Originally posted by CaTaLyST:
i am moving this to the programming forum.



Bah! We already have one, CaTaLyST. :P

I'm gonna close this one to let the other one continue.

*click*

------------------
Don't you wish that life sometimes supported Control-Z?