There's more than one way to do things | |
PerlMonks |
comment on |
( [id://3333]=superdoc: print w/replies, xml ) | Need Help?? |
How does the set of "unintersected edges" computed by your algorithm differ from a Delaunay triangulation? If the difference is insignificant for your application (or can be quickly computed), you might be better off starting with a fast Delaunay triangulation (e.g., using Qhull) and adapting its output to your needs.
Update: Take a look at Aurenhammer and Xu's "Optimal Triangulations". It points out that the greedy triangulation – what you are computing – is not necessarily the minimum-weight triangulation (MWT). The paper also notes, however, that for uniformly distributed point sets both the greedy and Delaunay triangulations yield satisfactory approximations to the MWT. Second update: The following code uses Qhull and computes an (approximate) DT-derived solution almost instantly:
Example: solve dump_301.yml. Output:
Cheers, Tom Moertel : Blog / Talks / CPAN / LectroTest / PXSL / Coffee / Movie Rating Decoder In reply to Delaunay triangulation
by tmoertel
|
|