Re: Fast search for a number within tolernaces

Jonas Forssell wrote: 
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


--
The comp.lang.java.gui FAQ:
ftp://ftp.cs.uu.nl/pub/NEWS.ANSWERS/computer-lang/java/gui/faq
.

Relevant Pages

  • Re: My prime counting function
    ... If it is a Java program it can't go to infinity. ... ints longs and even ... Back when I thought that developing a really fast algorithm would ... prime up to 10^14 in about an hour, with todays computers it'd take ...
    (comp.lang.java.programmer)
  • Re: My prime counting function
    ... If it is a Java program it can't go to infinity. ... ints longs and even ... Back when I thought that developing a really fast algorithm would ... prime up to 10^14 in about an hour, with todays computers it'd take ...
    (comp.lang.java.programmer)