Solved

Triangulation algorithm anybody?

Posted on 2004-04-09
6
368 Views
Last Modified: 2010-04-05
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
Comment
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
  • Learn & ask questions
  • 2
6 Comments
 
LVL 11

Accepted Solution

by:
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

by:shaneholmes
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

by:rwilson032697
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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
In this tutorial I will show you how to use the Windows Speech API in Delphi. I will only cover basic functions such as text to speech and controlling the speed of the speech. SAPI Installation First you need to install the SAPI type library, th…
In this video we outline the Physical Segments view of NetCrunch network monitor. By following this brief how-to video, you will be able to learn how NetCrunch visualizes your network, how granular is the information collected, as well as where to f…
Monitoring a network: why having a policy is the best policy? Michael Kulchisky, MCSE, MCSA, MCP, VTSP, VSP, CCSP outlines the enormous benefits of having a policy-based approach when monitoring medium and large networks. Software utilized in this v…
Suggested Courses
Course of the Month11 days, 1 hour left to enroll

628 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question