[Date Index]
[Thread Index]
[Author Index]
Re: Much faster ConvexHull implementation
*To*: mathgroup at smc.vnet.net
*Subject*: [mg55669] Re: Much faster ConvexHull implementation
*From*: "Carl K. Woll" <carlw at u.washington.edu>
*Date*: Sat, 2 Apr 2005 01:28:00 -0500 (EST)
*Organization*: University of Washington
*References*: <d1tvc0$rli$1@smc.vnet.net> <200503270742.CAA06233@smc.vnet.net> <opsoa9q5xpiz9bcq@monster.ma.dl.cox.net> <011401c53310$74dde680$6400a8c0@Main> <opsob4uhh3iz9bcq@monster.ma.dl.cox.net> <02a501c533ac$f76aa4c0$6400a8c0@Main> <opsoc793kbiz9bcq@monster.ma.dl.cox.net> <d2b547$79l$1@smc.vnet.net> <d2j9ld$s2$1@smc.vnet.net>
*Sender*: owner-wri-mathgroup at wolfram.com
"Ray Koopman" <koopman at sfu.ca> wrote in message
news:d2j9ld$s2$1 at smc.vnet.net...
> "Carl K. Woll" <carl at woll2woll.com> wrote in message
> news:<d2b547$79l$1 at smc.vnet.net>...
>> [...]
[snip]
> Here is the hull for 9 random points in the unit square:
>
> In[10]:= convex[pts =
> {{0.358243,0.363412},{0.105996,0.669358},{0.672295,0.0448138},
> {0.0124393,0.672149},{0.728004,0.311669},{0.90424,0.545403},
> {0.99939,0.160133},{0.749434,0.963945},{0.355428,0.0788455}}]
>
> Out[10]= {7,6,8,4,4,9,3}
>
> Such duplication occurs fairly often for random points.
> Is anyone else getting this? Have I copied something wrongly?
>
Ray,
Let me first mention that I have an older version of Mathematica, where the
built-in ConvexHull did seem to scale as O(n^2). However, I've been informed
that newer versions of Mathematica should have a ConvexHull which does scale
as O(n^2). So, getting my convex[] to work for you is probably not worth
your trouble. I should also mention that my convex[] function is just the 2D
Quickhull algorithm.
However, in case you are still interested, I've improved convex[] on my
machine so that it's about an order of magnitude faster for random points in
the unit square and 2 to 3 times faster for finding the convex hull of the
vertices of a convex polygon. In fact, it seems that the scaling is not much
worse than linear for my test cases with up to a million points. I suppose
this may be because at least part of the O(n log n) dependence is due to
sorting, and since Sort (as well as Ordering) is an extremely quick built-in
function, it takes extremely large data sets before Sort dominates the
scaling. I'm sure there are also pathological cases where the scaling would
be much worse, but I haven't spent the time to construct any. I could send a
notebook with this newer algorithm to you if you are interested in testing
it.
As far as your question on duplication, I don't have an answer. I took the
code you posted, and ran it on my computer, and I did not get any duplicate
points on your test input. I believe you may be getting duplicate points
only at the left and/or right edges of your data set. At any rate, if you
are interested in pursuing this further, please try out my newer convex[]
first to see if the problem persists.
Carl Woll
Prev by Date:
**webMathematica-based on-line learning system?**
Next by Date:
**Re: DifferenceOrder command**
Previous by thread:
**Re: Re: Much faster ConvexHull implementation**
Next by thread:
**Re: Much faster ConvexHull implementation**
| |