Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2005
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2005

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Much faster ConvexHull implementation

  • To: mathgroup at smc.vnet.net
  • Subject: [mg55576] Re: Much faster ConvexHull implementation
  • From: DrBob <drbob at bigfoot.com>
  • Date: Wed, 30 Mar 2005 03:21:13 -0500 (EST)
  • 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> <047e01c5342a$c9758480$6400a8c0@Main>
  • Reply-to: drbob at bigfoot.com
  • Sender: owner-wri-mathgroup at wolfram.com

Brilliant.

Initially, I thought, "That's cool, but the built-in handles higher dimensions." But actually, it doesn't, so faster than built-in is great!!

> It's best to make sure your default input format is InputForm when you copy
> the function below to your notebook. At least on my machine, copying the
> following code into a StandardForm input cell introduces invisible
> multiplications so that executing the code results in Null^9 and the code
> doesn't work.

After copying into a StandardForm cell, I believe it suffices to highlight the cell and press in succession Ctrl-Shift-I, Ctrl-Shift-N.

The issue didn't come up in my notebook, anyway. Possibly 5.1.1 no longer has this problem?

> toppart[pts_, line_, l_, r_] :=

I think using the letter l as a variable amounts to a cruel (but not unusual) eye test.

I couldn't find anywhere l was actually used, but couldn't be sure because "l" and "1" look so nearly identical -- and the number 1 is used several times in toppart and bottompart.

Converting to TraditionalForm helps, but I don't like the format. It seems odd that different font styles are used on the left and right sides of ":=", for instance, and {{pt_, index_Integer}} is displayed as a matrix, when clearly we don't intend it to be.

Anyways... I think toppart never uses l, and bottompart never uses r.

Bobby

On Tue, 29 Mar 2005 01:44:41 -0500, Carl K. Woll <carl at woll2woll.com> wrote:

> Hi all,
>
> Inspired by the "point in a convex hull" discussion, I noticed that the
> DiscreteMath`ComputationalGeometry` version of ConvexHull appears to scale
> as O(n^2) instead of O(n log n) which is the usual lower bound. So, for
> those who are interested, I will present a much faster convex hull
> implementation that seems to scale as O(n log n). To get an idea of the
> speed difference, on a random sample of 1000 points, my version of convex
> hull is 60 times faster. Of course, with larger samples, the disparity is
> even worse due to the different scaling behavior.
>
> The algorithm is very simple. Given a line and some points above the line,
> the function finds the point that is highest above the line. Then, it forms
> a left line and a right line to this point, finds the points above these
> lines and repeats. Do the same thing with a line and points below the line
> and you have the convex hull.
>
> The output of my version of convex hull gives the points in counterclockwise
> order and is identical to the built-in ConvexHull, except for the case where
> there are vertical lines at the right edge. In this case, my version of
> convex hull starts with the top end of the right vertical line and goes
> counterclockwise, whereas the built-in ConvexHull starts at the bottom end
> of the right vertical line and goes counterclockwise. Also, if there are
> vertical lines at the right or left edge with more than 2 points, then my
> version omits these extra points, while the built-in ConvexHull includes
> them.
>
> At any rate, my version of convex hull can be found below. Any comments are
> appreciated.
>
> Carl Woll
>
> It's best to make sure your default input format is InputForm when you copy
> the function below to your notebook. At least on my machine, copying the
> following code into a StandardForm input cell introduces invisible
> multiplications so that executing the code results in Null^9 and the code
> doesn't work.
>
> convex[pts_] := Module[{spts, ss, toppts, bottompts},
>  spts = Sort[Transpose[{N[pts], Range[Length[pts]]}]];
>  ss = Drop[Split[spts[[All,1,1]]], {2, -2}];
>  If[spts[[Length[ss[[1]]],1]] === spts[[1,1]],
>   topleftindex = {};
>   topleft = spts[[1,1]]; ,
>   topleftindex = {spts[[Length[ss[[1]]],2]]};
>   topleft = spts[[Length[ss[[1]]],1]];
>  ];
>  If[spts[[-Length[ss[[-1]]],1]] === spts[[-1,1]],
>   bottomrightindex = {};
>   bottomright = spts[[-1,1]]; ,
>   bottomrightindex = {spts[[-Length[ss[[-1]]],2]]};
>   bottomright = spts[[-Length[ss[[-1]]],1]];
>  ];
>  topline = Interpolation[{topleft, spts[[-1,1]]}, InterpolationOrder -> 1];
>  bottomline = Interpolation[{spts[[1,1]], bottomright},
> InterpolationOrder -> 1];
>  toppts = Cases[spts, {{x_, y_}, _} /; y - topline[x] > 0];
>  bottompts = Cases[spts, {{x_, y_}, _} /; y - bottomline[x] < 0];
>  Join[
>   Reverse[toppart[toppts, topline, Null, spts[[-1,2]]]],
>   topleftindex,
>   bottompart[bottompts, bottomline, spts[[1,2]], Null],
>   bottomrightindex
>  ]
> ]
>
> toppart[pts_, line_, l_, r_] := Module[{newpt, leftline, rightline, leftpts,
> rightpts},
>  newpt = Ordering[pts[[All,1,2]] - line[pts[[All,1,1]]], -1][[1]];
>  leftline = Interpolation[{leftend[line], pts[[newpt,1]]},
> InterpolationOrder -> 1];
>  rightline = Interpolation[{pts[[newpt,1]], rightend[line]},
> InterpolationOrder -> 1];
>  leftpts = Cases[Take[pts, newpt - 1], {{x_, y_}, _} /; y - leftline[x] >
> 0];
>  rightpts = Cases[Drop[pts, newpt], {{x_, y_}, _} /; y - rightline[x] > 0];
>  Join[ toppart[leftpts, leftline, l, pts[[newpt,2]]],
>    toppart[rightpts, rightline, pts[[newpt,2]], r]
>  ]
> ]
>
> toppart[{{pt_, index_Integer}}, line_, l_, r_] := {index, r}
> toppart[{}, line_, l_, r_] := {r}
>
> bottompart[pts_, line_, l_, r_] := Module[{newpt, leftline, rightline,
> leftpts, rightpts},
>  newpt = Ordering[pts[[All,1,2]] - line[pts[[All,1,1]]], 1][[1]];
>  leftline = Interpolation[{leftend[line], pts[[newpt,1]]},
> InterpolationOrder -> 1];
>  rightline = Interpolation[{pts[[newpt,1]], rightend[line]},
> InterpolationOrder -> 1];
>  leftpts = Cases[Take[pts, newpt - 1], {{x_, y_}, _} /; y - leftline[x] <
> 0];
>  rightpts = Cases[Drop[pts, newpt], {{x_, y_}, _} /; y - rightline[x] < 0];
>  Join[ bottompart[leftpts, leftline, l, pts[[newpt,2]]],
>    bottompart[rightpts, rightline, pts[[newpt,2]], r]
>  ]
> ]
>
> bottompart[{{pt_, index_Integer}}, line_, l_, r_] := {l, index}
> bottompart[{}, line_, l_, r_] := {l}
>
> leftend[interp_] := {#1, interp[#1]}&[interp[[1,1,1]]]
> rightend[interp_] := {#1, interp[#1]}&[interp[[1,1,2]]]
>
>
>
>
>



-- 
DrBob at bigfoot.com


  • Prev by Date: Re: symbolic quaternionic analysis
  • Next by Date: Re: subtle dumb question
  • Previous by thread: Much faster ConvexHull implementation
  • Next by thread: Re: Much faster ConvexHull implementation