Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
• Status: Solved
• Priority: Medium
• Security: Public
• Views: 372

# Triangulation algorithm anybody?

Hello!

I have to include simple triangulation algorithm in my program which does following:

1.) reads points (X,Y) values (I can do that naturally) - it's a 2D environment
2.) connects points with non-overlapping straight lines (as long it is possible)
3.) calculates sum of all lenghts of these lines that connect points to each other
4.) tries to find shorter sum of lengths - based on the optimization of the result which it got in step #2

algorithm has to be able to handle up to 1000 points
for larger sets of points (let's say more than 100) it has to have some sort of timeout while trying to optimize
the result - if it finds any better (shorter sum of lenghts) solution it changes the value of the result but if it
doesn't find anything else during this timeout period it just sticks to the result it got in step #2.

Just to imagine - here's the graphical example of input:
http://www.oloplan.com/tri/tri1.gif
and this is the output:
http://www.oloplan.com/tri/tri2.gif

(solution has to be numeric only - only the sum of all lenghts is required)

Thanx for any help!
0
jakac
• 2
1 Solution

Commented:
Jakac,

On the delphi for fun web page, you will finds lots of information , in particular, in the Advanced portion.

for Instance, there is the Fences & Traveling Salesman example.

which may be of interest to you because it has some code to draw a Simple Path connecting an arbitrary arrangement of points with no line crossings.

http://www.delphiforfun.org/Programs/Fences.htm

Check out all the other problems Gary has solved utilizing Delphi

Shane
0

Commented:
There also may be some useful nformation on EFG's website:

http://www.efg2.com

in particular, the mathematics page:

http://www.efg2.com/Lab/Library/mathematics.htm

Shane
0

Commented:
I think what you are trying to do is a deLauney triangulation. Googling for this will give you more than enough information for your needs.

Cheers,

Raymond.
0

## Featured Post

• 2
Tackle projects and never again get stuck behind a technical roadblock.