Re: Vector Union

*To*: mathgroup at smc.vnet.net*Subject*: [mg23141] Re: Vector Union*From*: Jens-Peer Kuska <kuska at informatik.uni-leipzig.de>*Date*: Thu, 20 Apr 2000 03:20:59 -0400 (EDT)*Organization*: Universitaet Leipzig*References*: <8djl4o$7jh@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

Hi Russel, I overlooked you question, so my answer will be a bit late. I can't give you a n-dimensional version but the extension is easy if you know the dimension. The fastest version to find the unique $n$-dimensional points in a set is to use a tree of $2^n$ In three dimensions one can use $SamePrecision = 0.1*^-6; pointCount = 0; getIndex[p_List, p1_List] := Module[{index}, index = 1; If[p[[1]] < p1[[1]], index += 1]; If[p[[2]] < p1[[2]], index += 2]; If[p[[3]] < p1[[3]], index += 4]; index ] (* pointCount is fluid from MakeOctTree[] *) OctTreeInsert[p_List, {}] := {p, pointCount++, Table[{}, {8}], {}} OctTreeInsert[p_List, {p1_, i_Integer, l_, poly_List}] := Module[{index, delta, l1}, delta = p - p1; If[Abs[Dot[delta, delta]] < $SamePrecision, Return[{p1, i, l, poly}] ]; index = getIndex[p, p1]; l1 = OctTreeInsert[p, l[[index]]]; {p1, i, ReplacePart[l, l1, index], poly} ] and for the points pnts pointCount = 0; uniquePoints=Cases[Fold[OctTreeInsert[#2, #1] &, {}, pnts], {_?NumericQ, _?NumericQ, _?NumericQ}, Infinity] The speed gain depends on the number of points. MathGL3d uses an octtree to make a indexed point set form the vertex data. Typical for 10^4 points the usual search is to slow. A second advantage may be, that the octtree is incremental. You can add a k+1 point to your set and find quickly if it is already in the set. The Union/Sort[] versions need always the full set of points and can't be incremented without a new Sort[] call that consume (k+1)*Log[k+1] operations where the octtree need only Log[k+1] operations. For small point sets the overhead of the tree creation is to huge and the other versions maye work well. Also the memory for the tree is a constrain, because for a surface a maximum of 4 links may be used and four links are useless memory. In higher dimensions this becomes more dramatical. How ever for more than 10^4 points (with MathGL3d I have tryed 10^7) the octtree works excelent. Regards Jens Russell Towle wrote: > > The problem of finding a function to return the union of a list of > n-vectors which is at once *fast* and yet *unfailing* has beguiled me for > several years. I contrived a slow but unfailing 'vunion' function about > five years ago; made a not-so-slow and unfailing version a year ago; and > then found it to occasionally fail when Chop was applied to the vectors > without a second argument. >

**Follow-Ups**:**Re: Re: Vector Union***From:*Hartmut Wolf <hwolf@debis.com>