Re: Fortran to find nearest point from set in 3-D
- From: "Rob McDonald" <rob.a.mcdonald@xxxxxxxxx>
- Date: 16 Apr 2006 20:30:38 -0700
David.Paterson@xxxxxxxx wrote:
octree I know about, but k-d tree etc. are new to me. By the way, I
will have to do this 'proximal-point' problem hundreds of times with
different sets of points B.
Yes. Set A (the small one) comes from the triangular discretisation on
a set of surfaces and Set B (the big one) comes from the the corners of
a tetrahedral discretisation of 3-D space. Unfortunately all the
connectivity has been lost in the form that I have access to.
This means that the points in B are roughly equidistance apart, I may
even be able to give an 'a priori' maximum distance apart. If it helps,
call it 'D' for distance. I can also put hard upper and lower bounds on
each of the x, y and z of the triples (x,y,z) in B.
k-d tree is basically a binary tree where you rotate through each of
the dimensions on each level down the tree. So, the top level splits x
in half, the next level y, then z, then x again. A quick search should
lead to a lot of papers that discuss exactly the algorithms you need.
If you had the connectivity information, then you could be clever about
subsequent points. For each connected point in the small set, you
would have a good starting point. Without that information, you aren't
going to do any better than an octree or k-d tree binary search.
Even for a large problem, an octree approach should be really fast.
For a binary tree, each doubling of the number of points only requires
one additional bisection. An octree will scale similarly.
The bounds on B aren't much help beyond giving you a start on the bins
for your tree structure. If the points are approximately uniformly
distributed, then you could make a good guess at the required sizes of
the bins and do it all with some hackish statically allocated arrays.
Do you expect the closest points in A and B to be nearly coincident?
Might they be exactly coincident? If you could count on the pairs of
closest points being very nearly identical, there might be some clever
things you could do such as calculate a checksum, then you're searching
for an exact match in a single 'dimension'
Also, if you expect the closest match to be coincident points, you can
break the problem down using bounding boxes. For example, find the
bounding box of set A. Expand the bounds by a factor of the expected
point spacing. Then, reduce set B to the points falling withing the
box.
This can be carried further. Split the A box in half, grab the
corresponding A and B sets. Parallelize the problem to two processors.
This essentially mimics the octree approach, but on a somewhat ad-hoc
basis, made easier by expecting to find nearly coincident points....
Good luck,
Rob
.
- References:
- Fortran to find nearest point from set in 3-D
- From: David . Paterson
- Re: Fortran to find nearest point from set in 3-D
- From: Ronald Bruck
- Re: Fortran to find nearest point from set in 3-D
- From: David . Paterson
- Fortran to find nearest point from set in 3-D
- Prev by Date: Re: Fortran to find nearest point from set in 3-D
- Next by Date: Re: Reading a input in form of matrix
- Previous by thread: Re: Fortran to find nearest point from set in 3-D
- Next by thread: Re: Fortran to find nearest point from set in 3-D
- Index(es):
Relevant Pages
|
