Solved

# Triangulation algorithm anybody?

Posted on 2004-04-09
367 Views
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
Question by:jakac
[X]
###### 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
• 2

LVL 11

Accepted Solution

shaneholmes earned 500 total points
ID: 10793630
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

LVL 11

Expert Comment

ID: 10794384
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

LVL 12

Expert Comment

ID: 10809191
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

Question has a verified solution.

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

### Suggested Solutions

This article explains how to create forms/units independent of other forms/units object names in a delphi project. Have you ever created a form for user input in a Delphi project and then had the need to have that same form in a other Delphi proj…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
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 …
Finding and deleting duplicate (picture) files can be a time consuming task. My wife and I, our three kids and their families all share one dilemma: Managing our pictures. Between desktops, laptops, phones, tablets, and cameras; over the last decade…
###### Suggested Courses
Course of the Month1 day, 16 hours left to enroll