Re: Fast search for a number within tolernaces

Wibble <Wibble@xxxxxxxxxxxxxx> wrote in message news:<68SdnWQAmfy0HDjfRVn-hA@xxxxxxx>...
> 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.

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

Relevant Pages

  • Re: Fast search for a number within tolernaces
    ... Partition your space into a 3D matrix with each cube of a discrete size. ... a HashMap to model a sparse matrix. ... an average of the component positions. ...
    (comp.lang.java.programmer)
  • Re: Proposed enhancements to MD
    ... The attached patch is for the partition ... >, Adaptec, and many others must continue to support new ... >> the partitions on an array and properly boot them as it would boot a ... root fs exists on array, but md didn't see them show up, ...
    (Linux-Kernel)
  • Re: Adding another Raid - How Best to go about it.
    ... It's _almost_ as easy to create the array at BIOS level. ... so the layout and use(size of parts, %free space, files on it). ... I would adjust the swapfile on the OS partition to RAM+20MB ... Plug in drives, ...
    (microsoft.public.windows.server.sbs)
  • 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)