Fast search for a number within tolernaces

J

Jonas Forssell

Gentlemen,

I have a set of three dimensional nodes - each with a position in
space (x,y,z).
I need to write a fast algorithm in Java to merge nodes that are close
- i.e. within a specific tolerance.

Easy way: Run through the array of nodes, check each node against
every other node and merge if needed. This will take an awful amount
of time when the array is 500.000 nodes or larger.

Smart way:?

Thanks for your help
 
I

Ingo R. Homann

Hi,
I have a set of three dimensional nodes - each with a position in
space (x,y,z).
I need to write a fast algorithm in Java to merge nodes that are close
- i.e. within a specific tolerance.

Easy way: Run through the array of nodes, check each node against
every other node and merge if needed. This will take an awful amount
of time when the array is 500.000 nodes or larger.

Smart way:?

Depends on how exact you need it. My first advance would be (*):

Take the first node and use it as first "merged node".
Take the second node and see, if it is within the tolerance to "merged
node". If yes, merge them, if not, use it as the second "merged node".
Continue this way with all other nodes.

When N is the number of nodes and M is the number of "merged nodes", the
algorithm needs O(N*M) steps, not O(N*N) as your algorithm.

(*) The disadvantage is that the result may depend on the "starting
value". Consider the (1D-)values 1,2,3 and a tolerance of 1. My
algorithm (starting with "1") will deliver (1,2),(3), whereas the
correct result would be (1,2,3).

I guess, if necessary, it should be possible (without to much
calculation costs) to modify my algorithm in that way, that it does not
use the starting value as the "center" of the "merged node". Instead it
might use the medium of all nodes within the "merged node" (which does
not help in the above example, because abs(medium(1,2)-3)=1.5 > 1). Or,
you may really calculate the maximum distance of the "new node" to all
nodes of the "merged node". (That would be much more expensive (although
even slightly better than your algorithm) and of course it also depends
a little bit on the starting value.)

Ciao,
Ingo
 
T

Thomas Weidenfeller

Jonas said:
I have a set of three dimensional nodes - each with a position in
space (x,y,z).
I need to write a fast algorithm in Java to merge nodes that are close
- i.e. within a specific tolerance.

Easy way: Run through the array of nodes, check each node against
every other node and merge if needed. This will take an awful amount
of time when the array is 500.000 nodes or larger.

Smart way:?

A better data structure for the nodes right from the beginning. For
example an octree structure - there are for sure others. Also, if it
makes sense for the application, a simpler metric (Manhattan metric
instead of euclidean metric) to calculate node distances.

/Thomas
 
W

Wibble

Jonas said:
Gentlemen,

I have a set of three dimensional nodes - each with a position in
space (x,y,z).
I need to write a fast algorithm in Java to merge nodes that are close
- i.e. within a specific tolerance.

Easy way: Run through the array of nodes, check each node against
every other node and merge if needed. This will take an awful amount
of time when the array is 500.000 nodes or larger.

Smart way:?

Thanks for your help
If all your nodes are equidistant, do you merge them into a single node?

Partition your space into a 3D matrix with each cube of a discrete size.
Merge nodes that are within the same cube. Thats O(n). You can use
a HashMap to model a sparse matrix. You can position the final node at
an average of the component positions.

Read a book on graphics like Foley&VanDamm. Theres lots of ways to
partition and filter 3D models that are more efficient and look better
than node merging.
 
J

Jonas Forssell

Wibble said:
If all your nodes are equidistant, do you merge them into a single node?

Partition your space into a 3D matrix with each cube of a discrete size.
Merge nodes that are within the same cube. Thats O(n). You can use
a HashMap to model a sparse matrix. You can position the final node at
an average of the component positions.

Read a book on graphics like Foley&VanDamm. Theres lots of ways to
partition and filter 3D models that are more efficient and look better
than node merging.

Thanks for your reply!
I understand now how to continue.
Appreciated
/Jonas
 
L

Lucy

Jonas Forssell said:
Gentlemen,

I have a set of three dimensional nodes - each with a position in
space (x,y,z).
I need to write a fast algorithm in Java to merge nodes that are close
- i.e. within a specific tolerance.

Easy way: Run through the array of nodes, check each node against
every other node and merge if needed. This will take an awful amount
of time when the array is 500.000 nodes or larger.

Smart way:?

Thanks for your help

How do you do a merge? If you set the x,y,z values of the merged node
to be the average of the input nodes, you now have to go back and check
nodes that you have already passed because your new merged node might
be close enough to one of them as to trigger an additional merge.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top