Services & ResourcesWolfram ForumsMathGroup Archive

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

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>