Re: [Algorithms] merging of points in 3D space

[Alen L. <al...@cr...>]

Here is what I use:

1) Do a qsort() on the array, using a weak lexicografic ordering as
comparison function. I.e.

if (x0-x1 < -EPSILON) return -1;
else if (x0-x1 > +EPSILON) return 1;
else if (y0-y1 < -EPSILON) return -1;
else if (y0-y1 > +EPSILON) return 1;
else if (z0-z1 < -EPSILON) return -1;
else if (z0-z1 > +EPSILON) return 1;
else return 0;

(This procedure is O(n log n).)

2) Then do a linear walk over the array comparing neighbors again and
eliminating those that are "equal", by the same comparison function. (This
procedure is O(n).)

The expected overal performance should be bounded by O(n log n).

HTH,

Alen


----- Original Message -----
From: "Peter Szinek" <sz...@po...>
To: <gda...@li...>
Sent: Friday, April 18, 2003 9:25 AM
Subject: [Algorithms] merging of points in 3D space


> Hello all,
>
> I am having the following problem:
>
> Consider an array of points in 3D given by (x, y, z). Every point is in
the
> array more times (5-6 times, does not really matter) but the problem is
that
> these points are not really the same - there are small differences between
their
> coordinates
> e.g. points with coordinates
>
> 1.000 1.000 1.000
> 0.999 1.001 1.000
> 1.000 1.002 0.989 etc
>
> are considered to represent the same point.
>
> Now, my question is, how to 'merge' these points into one (e.g. in the
previous
> example, keep only one such point) _VERY_ fast. The trivial algorithm is
far-far
> away (as usual) from the fast enough.
>
> Any help appreciated.
>
>
>
>
>
> --
> Best regards,
>  Peter                          mailto:sz...@po...
>
>
>
> -------------------------------------------------------
> This sf.net email is sponsored by:ThinkGeek
> Welcome to geek heaven.
> http://thinkgeek.com/sf
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=6188
>