Solved

Triangulation algorithm anybody?

Posted on 2004-04-09
6
362 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
  • 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
delphi custom sort exception 6 137
Run video youtube webbrowse 10 58
Tviruailstringtree sort multi columns on header click 1 54
update joined tables 2 32
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…
Introduction Raise your hands if you were as upset with FireMonkey as I was when I discovered that there was no TListview.  I use TListView in almost all of my applications I've written, and I was not going to compromise by resorting to TStringGrid…
This Micro Tutorial hows how you can integrate  Mac OSX to a Windows Active Directory Domain. Apple has made it easy to allow users to bind their macs to a windows domain with relative ease. The following video show how to bind OSX Mavericks to …
Video by: Mark
This lesson goes over how to construct ordered and unordered lists and how to create hyperlinks.

864 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

Need Help in Real-Time?

Connect with top rated Experts

23 Experts available now in Live!

Get 1:1 Help Now