

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object org.jcae.mesh.amibe.util.KdTree
public class KdTree
Quadtree structure to store 2D vertices. When adjacent relations have not yet been set, a quadtree is an efficient way to locate a point among a set of points and triangles.
Integer coordinates are used for two reasons: a better control on accuracy of geometrical operations, and simpler operations on vertex location because cells have power of two side length and bitwise operators can be used instead of floating point operations. The downside is that the conversion between double and integer coordinates must be known in advance, which is why constructor needs a bounding box as argument.
Each KdTree.Cell
contains either vertices or four children nodes
(some of them may be null
). A cell can contain at most
BUCKETSIZE
vertices (default is 10). When this number
is exceeded, the cell is splitted and vertices are stored in these children.
On the contrary, when all vertices are removed from a cell, it is deleted.
And when all children of a cell are null, this cell is removed.
Quadtree cells are very compact, they do not contain any locational
information. It is instead passed to the
KdTreeProcedure.action(Object, int, int[])
method.
This design had been chosen for performance reasons on large meshes, and in
practice it works very well because quadtrees are used for vertex location,
and no neighbourhood information is needed.
Quadtree traversal is performed by the walk(KdTreeProcedure)
method.
Here is an example to collect all vertices in a list:
public final class collectAllVerticesProcedure implements KdTreeProcedure { public CollectionvertexList = new ArrayList (); public final int action(Object o, int s, int [] i0) { Cell self = (Cell) o; if (self.nItems > 0) { for (int i = 0; i < self.nItems; i++) vertexList.add((Vertex) self.subCell[i]); } return KdTreeProcedure.OK; } }
This procedure is applied on all cells recursively in prefix order. If it
returns KdTreeProcedure.ABORT
, walk(KdTreeProcedure)
aborts its
processing immediately; KdTreeProcedure.OK
return value means that processing can
continue normally, and KdTreeProcedure.SKIPCHILD
return value means that children
nodes are skipped.
Distances between vertices can be computed either in Euclidian 2D space, or
with a Riemannian metrics. This is controlled by the
Mesh2D.pushCompGeom(int)
method.
Distances are computed in Euclidian 2D space when its argument is
an instance of Calculus2D
, and in
Riemannian metrics (see Metric2D
) when
it is an instance of Calculus3D
.
By default, distances are computed in Euclidian 2D space.
In Euclidian 2D space, vertices which have a distance to a point p
lower than d
are contained in a circle centered at p
with radius d
. With Riemannian metrics, this circle becomes
an ellipsis. This ellipsis is only determined by local properties of the
surface at point p
.
If we already found a point V1
at a distance d1
,
vertices which belong to a quadtree cell not intersecting this ellipsis
do not need to be considered.
Below is an algorithm to find the nearest vertex in the quadtree of a given
point p
:
dmin=Double.MAX_VALUE
, result=null
p
of vertices at a distance lower than dmin
,
then skip this cell and its children.p
and update dmin
and
result
if it is nearer than the current solution.
The implementation of getNearestVertex(Mesh, Vertex)
has two
differences:
getNearVertex(Mesh, Vertex)
.
This means that much more cells are skipped.
Nested Class Summary  

class 
KdTree.Cell

Field Summary  

int 
nCells
Number of cells. 
protected KdTree.Cell 
root
Root of the kdtree. 
double[] 
x0
Conversion between double and integer coordinates. 
Constructor Summary  

KdTree(double[] bbox)
Create a new KdTree of the desired size. 

KdTree(double[] bbox,
int bucketsize)
Create a new KdTree of the desired size. 

KdTree(int d)
Dummy constructor. 
Method Summary  

boolean 
add(Vertex v)
Add a vertex to the kdtree. 
double[] 
center()
Return the coordinates of the center of the grid. 
void 
double2int(double[] p,
int[] i)
Transform double coordinates into integer coordinates. 
java.util.Collection<Vertex> 
getAllVertices(int capacity)
Return a collection of all vertices. 
int 
getMaxLevel()

Vertex 
getNearestVertex(Mesh mesh,
Vertex v)
Return the nearest vertex stored in this Octree . 
Vertex 
getNearestVertexDebug(Mesh mesh,
Vertex v)
Slow implementation of getNearestVertex(Mesh, Vertex) . 
Vertex 
getNearVertex(Mesh mesh,
Vertex v)
Return a stored element of the Octree which is
near from a given vertex. 
void 
int2double(int[] i,
double[] p)
Transform integer coordinates into double coordinates. 
void 
remove(Vertex v)
Remove a vertex from the kdtree. 
void 
setup(double[] bbox)
Computes x0 adapted to this bounding box. 
boolean 
walk(KdTreeProcedure proc)
Perform an action on all cells in prefix order. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 

protected final KdTree.Cell root
public int nCells
public final double[] x0
Constructor Detail 

public KdTree(int d)
setup(double[])
before putting elements into it.
d
 dimension (2 or 3)public KdTree(double[] bbox)
KdTree
of the desired size.
bbox
 coordinates of bottomleft vertex and upperright verticespublic KdTree(double[] bbox, int bucketsize)
KdTree
of the desired size.
bbox
 coordinates of bottomleft vertex and upperright verticesbucketsize
 bucket sizeMethod Detail 

public final void setup(double[] bbox)
x0
adapted to this bounding box.
bbox
 coordinates of bottomleft vertex and upperright verticespublic void double2int(double[] p, int[] i)
p
 double coordinatesi
 integer coordinatespublic void int2double(int[] i, double[] p)
i
 integer coordinatesp
 double coordinatespublic double[] center()
public boolean add(Vertex v)
v
 the vertex being added.
true
if cell was full and had to be split, false
otherwise.public void remove(Vertex v)
v
 the vertex being removed.public java.util.Collection<Vertex> getAllVertices(int capacity)
capacity
 initial capacity of the Collection
.
public final boolean walk(KdTreeProcedure proc)
1
, processing aborts
immediately and false
is returned. If the
procedure returns 1
, cell children are not processed.
proc
 procedure to apply on each cell.
true
if all cells have been traversed, false
otherwise.KdTreeProcedure
public final Vertex getNearVertex(Mesh mesh, Vertex v)
Octree
which is
near from a given vertex. The algorithm is simplistic: the leaf
which would contains this node is retrieved. If it contains
vertices, the nearest one is returned (vertices in other leaves may
of course be nearer). Otherwise the nearest vertex from sibling
children is returned. The returned vertex is a good starting point
for getNearestVertex(Mesh, Vertex)
.
v
 the node to check.
public final Vertex getNearestVertex(Mesh mesh, Vertex v)
Octree
.
v
 the node to check.
public Vertex getNearestVertexDebug(Mesh mesh, Vertex v)
getNearestVertex(Mesh, Vertex)
.
This method should be called only for debugging purpose.
v
 the vertex to check.
public final int getMaxLevel()


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 