Normally in academic papers/textbooks the algorithmic complexity is
derived symbolically, based on the characteristics and data structures
used in the algorithm. It's always seems like a bit of a black art to
me - the proofs are often much more complicated than the algorithm
(which may itself
Stefan Steiniger a écrit :
> Can I actually ask how Michael derived the algorithmic complexity
> empirical? - because if I ever see these things, for instance by M van
> Kreveld or in some optimiziation books (e.g. Z Michalewicz and DB Fogel
> 2000)- I don't get how this is really done (and prov
wow.. those geeky talks ;)
I would like to know much more about Comp Geom.
Can I actually ask how Michael derived the algorithmic complexity
empirical? - because if I ever see these things, for instance by M van
Kreveld or in some optimiziation books (e.g. Z Michalewicz and DB Fogel
2000)- I d
Right, I see the sorting step now. Out of curiosity, did you check to
see if it was any faster using an array and Collections.sort, rather
than a TreeSet? I would have thought building a tree was slower than
doing a single sort of an array, followed by removing duplicates by
traversing the ar
Hi
> I should have looked before I wrote - I just found the link you sent a
> while ago to your code (for others benefit -
> http://geo.michaelm.free.fr/OpenJUMP/resources/ ).
>
> So you are using Incremental insertion, with a Triangle- based data
> structure. It looks like your code handles Co
Michael,
I should have looked before I wrote - I just found the link you sent a
while ago to your code (for others benefit -
http://geo.michaelm.free.fr/OpenJUMP/resources/ ).
So you are using Incremental insertion, with a Triangle- based data
structure. It looks like your code handles Constr
One other thing the JTS API supports computing a Conformal Delaunay
Triangulation as well. This is done using the Incremental Insertion
algorithm to refine the triangulation. So this is a bit of a constraint
on the design and implementation. I'm not sure if CDTs are supported by
other D
Interesting comparison, Michael. Is your code online somewhere? What
algorithm does it use, and what data structure for the triangulation?
In the JTS API you don't have to create the triangles as a MultiPolygon
- that's just provided as a simple option for viewing them in the JTS
TestBuilder.
Thanks for the analysis Michael.
SS
2009/5/17 Michaël Michaud :
> Hi Martin,
>
> Today, I compared the new JTS triangulation api with the triangulation
> plugin I wrote some years ago.
> In my tests, I just compared speed for triangulation of a random set of
> points (no constraint, no real data)
Hi Martin,
Today, I compared the new JTS triangulation api with the triangulation
plugin I wrote some years ago.
In my tests, I just compared speed for triangulation of a random set of
points (no constraint, no real data).
Measures include initialization, triangulation, and feature(s) creation
Well, there certainly seems to be no shortage of Delaunay Triangulation
libraries - an embarassment of riches!
It seems like this would be a great opportunity to try and start
converging on some common solutions, or at least some common
understanding of requirements and issues. Obviously perfo
Dear friends,
To complete Thomas a new triangulation package has been developed by
Jean-Yves Martin (Professor at Ecole Centrale de Nantes). It will be fully
available in 2 weeks. The beta code is here :
http://geosysin.iict.ch/irstv-trac/browser/platform-contrib/jdelaunay.
It includes :
- DT
-
2009/4/29 Michaël Michaud
> Hi Martin,
>
> You may already know the benchmark done by Erwan's team with some java
> implementations (
> http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
> It eventually shows the triangulator I have written a few years ago
> (available on http:
2009/4/29 Michaël Michaud
> Hi Martin,
>
> You may already know the benchmark done by Erwan's team with some java
> implementations (
> http://conference.osgeo.org/index.php/foss4g/2008/paper/view/282/177)
> It eventually shows the triangulator I have written a few years ago
> (available on http:
14 matches
Mail list logo
