Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Triangulation algorithm anybody?

Posted on 2004-04-09
6
Medium Priority
?
370 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 2000 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

[Webinar] Lessons on Recovering from Petya

Skyport is working hard to help customers recover from recent attacks, like the Petya worm. This work has brought to light some important lessons. New malware attacks like this can take down your entire environment. Learn from others mistakes on how to prevent Petya like worms.

Question has a verified solution.

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

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…
Introduction The parallel port is a very commonly known port, it was widely used to connect a printer to the PC, if you look at the back of your computer, for those who don't have newer computers, there will be a port with 25 pins and a small print…
This is my first video review of Microsoft Bookings, I will be doing a part two with a bit more information, but wanted to get this out to you folks.
In response to a need for security and privacy, and to continue fostering an environment members can turn to for support, solutions, and education, Experts Exchange has created anonymous question capabilities. This new feature is available to our Pr…
Suggested Courses

670 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