OctTrees, KDTrees and Vertically Aligned Data - Graphics

This is a discussion on OctTrees, KDTrees and Vertically Aligned Data - Graphics ; I've implemeted Nearest Neighbor searching for 3D points in OctTrees and KDTrees but because most of my data is vertically aligned on I'm having prpoblems. The OctTrees become to deep and are very slow. The KDTrees are fast but the ...

+ Reply to Thread
Results 1 to 6 of 6

OctTrees, KDTrees and Vertically Aligned Data

  1. Default OctTrees, KDTrees and Vertically Aligned Data

    I've implemeted Nearest Neighbor searching for 3D points in OctTrees
    and KDTrees but because most of my data is vertically aligned on I'm
    having prpoblems. The OctTrees become to deep and are very slow. The
    KDTrees are fast but the searching is cut short before the true
    closest points are found. They both work great when the data is
    randomly distributed. However for my application the data is from
    drill holes and only 95% of the time they are vertical so I can't
    depend on their orientation.

    Is there any way to improve the accuracy of the KDTree or speed up the
    OctTree with this sort of data?

    Mitch


  2. Default Re: OctTrees, KDTrees and Vertically Aligned Data

    MIW954@gmail.com wrote:

    > I've implemeted Nearest Neighbor searching for 3D points in OctTrees
    > and KDTrees but because most of my data is vertically aligned on I'm
    > having prpoblems. The OctTrees become to deep and are very slow. The
    > KDTrees are fast but the searching is cut short before the true
    > closest points are found.


    That's rather certainly not the k-d tree's fault. It's a bug in your
    nearest neighbor search.

    > drill holes and only 95% of the time they are vertical so I can't
    > depend on their orientation.


    What does it mean for data to "be vertical"? A 3D point has no
    direction, so it can't be vertical by itself.

  3. Default Re: OctTrees, KDTrees and Vertically Aligned Data

    > What does it mean for data to "be vertical"? A 3D point has no
    > direction, so it can't be vertical by itself.


    Sorry, I'm not a Mathmatician but a Geologist so my language is not
    100% correct. We tend to collect our data from drill holes that are
    vertical. In other words the X and Y coordinates are the same for each
    drill hole. A project may contain 100's of drill holes but not all of
    them are vertical. They may be straight but at a non-vertical
    orientation or they may not be straight at all.


  4. Default Re: OctTrees, KDTrees and Vertically Aligned Data

    MIW954@gmail.com wrote:

    > We tend to collect our data from drill holes that are
    > vertical. In other words the X and Y coordinates are the same for each
    > drill hole.


    .... usually.

    > A project may contain 100's of drill holes but not all of
    > them are vertical. They may be straight but at a non-vertical
    > orientation or they may not be straight at all.


    In other words, this kind of verticality is not really a guaranteed
    feature of your data.

    But that's not the most important question as far as nearest neighbor
    queries are concerned, anyway. The real questions would be:

    * Is there a pronounced bias to the direction of the vector from a point
    to its nearest neighbour? E.g., is the nearest neighbour predominantly
    found in the same drill hole's set, or predominantly in another one?

    * Will you be looking for nearest neighbors of points in the input set,
    or of arbitrary points?

    * What's the ratio of longest to shortest coordinate range of your
    dataset? All three ranges roughly the same? Or much longer than the
    others? Or shorter, maybe?

    E.g., if data points in each drill hole are much closer to each other
    than the distance to the next hole (which I presume they would be), the
    set of points with the same nearest neighbor is roughly a flat,
    polygonal disk. So the cells in your k-d tree should have roughly the
    shape of such polygonal disks, but a bit larger than those. That way,
    the nearest neighbor has a high probability of being in the same cell as
    the query point, otherwise it'll be in one of its neighbors.

  5. Default Re: OctTrees, KDTrees and Vertically Aligned Data

    On Jun 25, 1:24 pm, Hans-Bernhard Bröker <HBBroe...@t-online.de>
    wrote:
    > MIW...@gmail.com wrote:
    > In other words, this kind of verticality is not really a guaranteed
    > feature of your data.


    Excatly

    > But that's not the most important question as far as nearest neighbor
    > queries are concerned, anyway. The real questions would be:
    >
    > * Is there a pronounced bias to the direction of the vector from a point
    > to its nearest neighbour? E.g., is the nearest neighbour predominantly
    > found in the same drill hole's set, or predominantly in another one?


    No but as an option we might want to add a bias to the search (e.g.
    closest point in each sector, closest points in a plane, etc.).

    > * Will you be looking for nearest neighbors of points in the input set,
    > or of arbitrary points?


    An evenly spaced 3D array of voxels that cover all or part of the
    input data set.

    > * What's the ratio of longest to shortest coordinate range of your
    > dataset? All three ranges roughly the same? Or much longer than the
    > others? Or shorter, maybe?


    It will vary from project to project but usually the X and Y ranges
    will be close in value and the Z will be a the shortest range vy a
    factor of around 10 or more.

    >
    > E.g., if data points in each drill hole are much closer to each other
    > than the distance to the next hole (which I presume they would be), the
    > set of points with the same nearest neighbor is roughly a flat,
    > polygonal disk. So the cells in your k-d tree should have roughly the
    > shape of such polygonal disks, but a bit larger than those. That way,
    > the nearest neighbor has a high probability of being in the same cell as
    > the query point, otherwise it'll be in one of its neighbors.


    I understand what you're saying but there will be exceptions to this
    that I can't ignore.


  6. Default Re: OctTrees, KDTrees and Vertically Aligned Data

    MIW954@gmail.com wrote:

    >> * Will you be looking for nearest neighbors of points in the input set,
    >> or of arbitrary points?


    > An evenly spaced 3D array of voxels that cover all or part of the
    > input data set.


    In that case, the performance of the k-d tree itself may not be all that
    important. Odds are you can reuse the result from a nearby grid
    position as a very good guess of each new one. This general idea is
    called "coherence" in the literature on computer graphics.

    > I understand what you're saying but there will be exceptions to this
    > that I can't ignore.


    Exceptions of what kind: local violations of a given dataset's global
    structure, or whole datasets with overall structure completely unlike
    the typical?

+ Reply to Thread

Similar Threads

  1. WordML Right Aligned Tab
    By Application Development in forum XML SOAP
    Replies: 0
    Last Post: 08-09-2007, 09:29 AM
  2. Left-aligned Titles for Right-aligned Tables? Is this possible?
    By Application Development in forum Adobe Framemaker
    Replies: 1
    Last Post: 12-14-2006, 09:27 PM
  3. best way to vertically navigate?
    By Application Development in forum Editors
    Replies: 5
    Last Post: 08-02-2006, 03:18 PM
  4. [Vim] - Open help sub-window vertically
    By Application Development in forum Editors
    Replies: 3
    Last Post: 04-17-2006, 05:45 AM
  5. Flip Image Vertically
    By Application Development in forum basic.visual
    Replies: 1
    Last Post: 01-28-2004, 11:52 AM