jhu.htmIndex
Class SpatialIndex

java.lang.Object
  |
  +--jhu.htmIndex.SpatialIndex

public class SpatialIndex

extends java.lang.Object

The Spatial Index is a quad tree of spherical triangles. The tree is built in the following way: Start out with 8 triangles on the sphere using the 3 main circles to determine them. Then, every triangle can be decomposed into 4 new triangles by drawing main circles between midpoints of its edges:

.
.                            /\
.                           /  \
.                          /____\
.                         /\    /\
.                        /  \  /  \
.                       /____\/____\
.

This is how the quad tree is built up to a certain level by decomposing every triangle again and again. For a complete descrption, please go to the HTM index website

This implementation builds the index up to a specified level (maxlevel) You can specify that it should keep the first few levels in memory with the second constructor argument (buildlevel). The default buildlevel is 2.

Author:

Peter Kunszt

Field Summary

int	buildlevel_
(package private) static int	IOFFSET
int	maxlevel_

Constructor Summary

SpatialIndex(int maxlevel)
Constructor: give only the level to build - keeping 2 levels in memory by default

SpatialIndex(int maxlevel, int buildlevel)
Constructor : give the level of the index and optionally the level to build - i.e.

Method Summary

(package private) void	add(SpatialVector v, int i)
double	area(int ID) The area in steradians for a given index ID
double	area(SpatialVector n0, SpatialVector n1, SpatialVector n2) area: routine to precompute the area of a node uses Girard's formula: AREA = A+B+C - Pi
(package private) SpatialLayer	getLayer(int index)
(package private) SpatialQuadNode	getNode(int index)
(package private) SpatialVector	getVertex(int x)
int	idByLeafNumber(int n) return leaf id for a certain bitlist index.
static int	idByName(java.lang.String name) Translate ascii leaf name to a uint32 The following encoding is used: The string leaf name has the always the same structure, it begins with an N or S, indicating north or south cap and then numbers 0-3 follow indicating which child to descend into.
int	idByPoint(double ra, double dec) find a node by giving a ra,dec in degrees.
int	idByPoint(SpatialVector v) find a node by giving a vector.
(package private) boolean	isInside(SpatialVector v, SpatialVector v0, SpatialVector v1, SpatialVector v2) Test whether a vector v is inside a triangle v0,v1,v2.
(package private) boolean	isLeaf(int i)
int	leafCount() leafCount: return number of leaf nodes
int	leafNumberById(int id) return leaf number in bitlist for a certain ID.
(package private) void	makeNewLayer(int oldlayer) makeNewLayer: generate a new layer and the nodes in it Here it is where the construction actually happens, generating new triangles out of old ones.
static java.lang.String	nameById(int id) Translate uint32 to an ascii leaf name The encoding described above may be decoded again using the following procedure: Traverse the uint32 from left to right.
java.lang.String	nameByLeafNumber(int n) return name for a certain leaf index (to be used for name lookup from a bitlist).
java.lang.String	nameByPoint(double ra, double dec) find a node by giving a ra,dec in degrees.
java.lang.String	nameByPoint(SpatialVector vector) find a node by giving a vector.
int	newNode(int v1, int v2, int v3, int id, int parent) Make a new Node: insert a new node_[] into the list.
SpatialVector[]	nodeVertex(int leaf) nodeVertex: return the vectors of the vertices, based on a bitlist leaf index
int[]	nodeVertexIds(int idx) nodeVertex: return index of vertices for a node
(package private) int	noNodes()
(package private) int	noVertices()
int	nVertices() nVertices: return number of vertices
void	showVertices(java.io.PrintStream out) showVertices: print every vertex to the output stream
(package private) void	sortIndex() sortIndex: sort the index so that the first node is the invalid node (index 0), the next 8 nodes are the root nodes and then we put all the leaf nodes in the following block in ascending id-order.
(package private) SpatialVector	V(int index, int x)
(package private) void	vMax() vMax: compute the maximum number of vertices for the polyhedron after buildlevel of subdivisions and the total number of nodes that we store also, calculate the number of leaf nodes that we eventually have.

Methods inherited from class java.lang.Object

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

Field Detail

maxlevel_

public int maxlevel_

buildlevel_

public int buildlevel_

IOFFSET

static final int IOFFSET

Constructor Detail

SpatialIndex

public SpatialIndex(int maxlevel)

Constructor: give only the level to build - keeping 2 levels in memory by default

SpatialIndex

public SpatialIndex(int maxlevel,
                    int buildlevel)

Constructor : give the level of the index and optionally the level to build - i.e. the depth to keep in memory. if maxlevel - buildlevel > 0 , that many levels are generated on the fly each time the index is called.

Method Detail

showVertices

public void showVertices(java.io.PrintStream out)

showVertices: print every vertex to the output stream

nodeVertexIds

public int[] nodeVertexIds(int idx)

nodeVertex: return index of vertices for a node

nodeVertex

public SpatialVector[] nodeVertex(int leaf)

nodeVertex: return the vectors of the vertices, based on a bitlist leaf index

makeNewLayer

void makeNewLayer(int oldlayer)

makeNewLayer: generate a new layer and the nodes in it Here it is where the construction actually happens, generating new triangles out of old ones.

newNode

public int newNode(int v1,
                   int v2,
                   int v3,
                   int id,
                   int parent)

Make a new Node: insert a new node_[] into the list. The vertex indices are given by v1,v2,v3 and the id of the node is set.

area

public double area(int ID)

The area in steradians for a given index ID

area

public double area(SpatialVector n0,
                   SpatialVector n1,
                   SpatialVector n2)

area: routine to precompute the area of a node uses Girard's formula: AREA = A+B+C - Pi

vMax

void vMax()

vMax: compute the maximum number of vertices for the polyhedron after buildlevel of subdivisions and the total number of nodes that we store also, calculate the number of leaf nodes that we eventually have.

sortIndex

void sortIndex()

sortIndex: sort the index so that the first node is the invalid node (index 0), the next 8 nodes are the root nodes and then we put all the leaf nodes in the following block in ascending id-order. All the rest of the nodes is at the end.

idByName

public static int idByName(java.lang.String name)

Translate ascii leaf name to a uint32 The following encoding is used: The string leaf name has the always the same structure, it begins with an N or S, indicating north or south cap and then numbers 0-3 follow indicating which child to descend into. So for a depth-5-index we have strings like N012023 S000222 N102302 etc Each of the numbers correspond to 2 bits of code (00 01 10 11) in the uint32. The first two bits are 10 for S and 11 for N. For example N 0 1 2 0 2 3 11000110001011 = 12683 (dec) The leading bits are always 0. --- WARNING: This works only up to 15 levels. (we probably never need more than 7)

nameById

public static java.lang.String nameById(int id)

Translate uint32 to an ascii leaf name The encoding described above may be decoded again using the following procedure: Traverse the uint32 from left to right. Find the first 'true' bit. The first bit pair gives N (11) or S (10). The subsequent bit-pairs give the numbers 0-3: (00, 01, 10, 11). Example: In the first level there are 8 nodes, and we get the names from numbers 8 through 15 giving S0,S1,S2,S3,N0,N1,N2,N3. The order is always ascending starting from S0000.. to N3333... WARNING: if name is already allocated, a size of at least 17 is required.

idByPoint

public int idByPoint(SpatialVector v)

find a node by giving a vector. The ID of the node is returned.

isInside

boolean isInside(SpatialVector v,
                 SpatialVector v0,
                 SpatialVector v1,
                 SpatialVector v2)

Test whether a vector v is inside a triangle v0,v1,v2. Input triangle has to be sorted in a counter-clockwise direction.

leafCount

public int leafCount()

leafCount: return number of leaf nodes

nVertices

public int nVertices()

nVertices: return number of vertices

leafNumberById

public int leafNumberById(int id)

return leaf number in bitlist for a certain ID. Since the ID here means the number computed from the name, this is simply returning ID -leafCount().

idByLeafNumber

public int idByLeafNumber(int n)

return leaf id for a certain bitlist index. Same as the function above

nameByLeafNumber

public java.lang.String nameByLeafNumber(int n)

return name for a certain leaf index (to be used for name lookup from a bitlist). This function is simply shorthand for nameById(n + leafCount()).

idByPoint

public int idByPoint(double ra,
                     double dec)

find a node by giving a ra,dec in degrees.

nameByPoint

public java.lang.String nameByPoint(SpatialVector vector)

find a node by giving a vector. The ID of the node is returned.

nameByPoint

public java.lang.String nameByPoint(double ra,
                                    double dec)

find a node by giving a ra,dec in degrees.

getVertex

SpatialVector getVertex(int x)

V

SpatialVector V(int index,
                int x)

getNode

SpatialQuadNode getNode(int index)

getLayer

SpatialLayer getLayer(int index)

noNodes

int noNodes()

noVertices

int noVertices()

add

void add(SpatialVector v,
         int i)

isLeaf

boolean isLeaf(int i)