Re: Fast search for a number within tolernaces

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

Relevant Pages

  • Re: Fast search for a number within tolernaces
    ... >> of time when the array is 500.000 nodes or larger. ... > Partition your space into a 3D matrix with each cube of a discrete size. ... > a HashMap to model a sparse matrix. ...
    (comp.lang.java.programmer)
  • Analysis Server Incremental Update on Changing Dimensions
    ... Error during lazy aggregation of partition ... Broadcast_Response_2004_07 in cube Broadcast_Response: ... Microsoft Gold Certified Partner for Business Intelligence ...
    (microsoft.public.sqlserver.olap)
  • Re: Analysis Server Incremental Update on Changing Dimensions
    ... Error during lazy aggregation of partition ... Broadcast_Response_2004_07 in cube Broadcast_Response: ... incrementally update our changing Dimensions everyday. ...
    (microsoft.public.sqlserver.olap)
  • Re: Several Partitions vs Several Cubes
    ... > the work required to "merge" these cubes into 1 virtual cube and create ... With the partition option you must reprocess all partitions, ... > districts ("all districts" not available and no district comparison ...
    (microsoft.public.sqlserver.olap)
  • Re: Validating a cube prcoessing job
    ... thanks for the reply Dave. ... Then have your application bind to the cube ... > Being able to "unprocess" a partition is a new feature in 2005. ... >> Think of this as commiting a transaction in SQL. ...
    (microsoft.public.sqlserver.olap)