Re: convex hull implementation in 2D
- From: andreas.fabri@xxxxxxxxxxxxxxxxxxx
- Date: 13 Feb 2006 00:43:33 -0800
In CGAL, the Computational Geometry Algorithms Library
you find several implementations of 2D convex hull.
http://www.cgal.org/Manual/doc_html/cgal_manual/Convex_hull_2/Chapter_main.html
CGAL also adresses the robustness issues mentioned
by Dave, so it might be worth a look.
best regards,
andreas
Dave Eberly a écrit :
"John" <weekender_ny@xxxxxxxxx> wrote in message
news:1139674876.103627.291210@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Does someone have a superfast convex hull algorithm in 2D?
Is there a paper that compares different convex hull algorithms
and concludes which is fastest in practice? I'm looking for the
fastest convex hull algorithm for point sets < 100 points.
The issue is more complex than "fastest". In practice, folks
tend to run into problems with robustness when the algorithm
is implemented in floating point. You might find an algorithm
which is really fast, works on many data sets, but fails on other
data sets. The trade off when implementing an algorithm is
how much computation time can you give up in order to gain
robustness.
Are you willing to map your points to integers? You then avoid
the robustness issue (with a correctly implemented hull
algorithm) and get speed (no floating-point arithmetic), but you
loss some accuracy (hull of mapped points not the same as hull
of original points). If you map your floating-point values to
rational numbers, you do not lose accuracy, but now you get
a slower method because of the cost of exact rational arithmetic.
Other attempts to maintain some speed but gain robustness:
adaptive predicates (compute floating-point determinants with
the minimum number of bits per float to guarantee correct
sign classification) or filtered predicates (compute in floating-point
but if classification is potentially unreliable, switch to exact
rational arithmetic).
Because you have a small number of points, selection of an
algorithm based on asymptotic analysis is most likely out of
the question. Maybe you could download qhull and a few
other packages available online and run some test programs
to determine speed. My opinion for such test programs is
to include some data sets with collinear and coplanar points,
just to catch problems. John Ratcliff had done some testing
of packages like this and found that all packages had problems
with a few data sets (the failures were on different data sets
with different packages), even qhull. He used to have this
online (http://www.infiniplex.net/~jratcliff/ConvexHull.zip),
but unfortunately the link is now stale.
To finally offer some information that addresses your original
question, my experience was that the incremental hull
algorithm was slower than a divide-and-conquer approach
even on small data sets. I did not compare to Graham's
convex hull algorithm. You might try this one, also.
--
Dave Eberly
http://www.geometrictools.com
.
- References:
- convex hull implementation in 2D
- From: John
- Re: convex hull implementation in 2D
- From: Dave Eberly
- convex hull implementation in 2D
- Prev by Date: Re: Curve Generation Alogrithm
- Next by Date: Vacancy Postdoc 3D Shape Analysis
- Previous by thread: Re: convex hull implementation in 2D
- Next by thread: Programming Competition With Prize
- Index(es):
Relevant Pages
|
