gdalgorithms-list

[Algorithms] merging of points in 3D space

[Peter S. <sz...@po...>]

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...

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
>

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

[Jon W. <hp...@mi...>]

> 1.000 1.000 1.000
> 0.999 1.001 1.000
> 1.000 1.002 0.989 etc


Either sort by one axis, and then walk the list, merging points=20
that are close enough (you only need to look a certain distance=20
ahead in the list to find matches). This is vaguely N*sqrt(N) in=20
run-time, assuming number of neighbors you need to consider=20
grows as root of total number of verts.

Or round/quantize all points to even multiples of your weld=20
distance (typically, convert them all to shorts with the=20
appropriate scaling factor), and use a hash table to find=20
matches as you insert into the table. This is N run-time, in the=20
same sense as hashing is N in run-time.

Cheers,

				/ h+

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

[Charles B. <cb...@cb...>]

There's code for this in Galaxy.

At 09:57 AM 4/18/2003 -0700, Jon Watte wrote:
>
>> 1.000 1.000 1.000
>> 0.999 1.001 1.000
>> 1.000 1.002 0.989 etc
>
>
>Either sort by one axis, and then walk the list, merging points 
>that are close enough (you only need to look a certain distance 
>ahead in the list to find matches). This is vaguely N*sqrt(N) in 
>run-time, assuming number of neighbors you need to consider 
>grows as root of total number of verts.
>
>Or round/quantize all points to even multiples of your weld 
>distance (typically, convert them all to shorts with the 
>appropriate scaling factor), and use a hash table to find 
>matches as you insert into the table. This is N run-time, in the 
>same sense as hashing is N in run-time.
>

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com

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

[Richard F. <alg...@th...>]

1) if you are having a problem find out whether they are close enough to
merge, may I suggest you use a dynamic octree for finding out if they
are close, then adding an entry into the octree if it is a new vert...

a dynamic octree is very fast at picking out points in space...

2) if you are having problems deciding where to put the merged vertex,
then why not put it on the grid point where the distance between grid
points is the tolerance of the merge.

using the grid you can put a definite stop on the leaf size of your
octree...

if you use a grid, there is no reason why you cannot use a hash table
(might be quicker than an octree)

------------------------------------------------------------------------
-------
main(){char*a="main(){char*a=%c%s%c;printf(a,34,a,34);}";printf(a,34,a,3
4);}
------------------------------------------------------------------------
-------


> -----Original Message-----
> From: gda...@li... 
> [mailto:gda...@li...] On 
> Behalf Of Peter Szinek
> Sent: 18 April 2003 10:26
> To: gda...@li...
> 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
>