jhu.htmIndex
Class SpatialConvex

java.lang.Object
  |
  +--jhu.htmIndex.SpatialSign
        |
        +--jhu.htmIndex.SpatialConvex

public class SpatialConvex

extends SpatialSign

The SpatialConvex class encapsulates all the code for intersection and lookup. It represents a convex on the unit sphere (see SpatialDomain).

Field Summary

(package private) int	addlevel_
(package private) boolean	bitresult_
(package private) SpatialConstraint	boundingCircle_
(package private) java.util.List	constraints_
(package private) java.util.List	corners_
(package private) java.util.List	flist_
(package private) java.util.BitSet	full_
(package private) SpatialIndex	index_
(package private) SpatialMarkup	markup_
(package private) java.util.BitSet	partial_
(package private) java.util.List	plist_

Fields inherited from class jhu.htmIndex.SpatialSign

mIXED, nEG, pOS, sign_, zERO

Constructor Summary

SpatialConvex()
Default Constructor

SpatialConvex(SpatialVector v1, SpatialVector v2, SpatialVector v3)
Constructor from a triangle Initialize domain from a triangle.

SpatialConvex(SpatialVector v1, SpatialVector v2, SpatialVector v3, SpatialVector v4)
Constructor from a rectangle Initialize convex from a rectangle.

Method Summary

void	add(SpatialConstraint c) Add a constraint
(package private) void	doIntersect() Do the intersection (common function for overloaded intersect())
(package private) boolean	eSolve(SpatialVector v1, SpatialVector v2, int cIndex) eSolve: solve the quadratic equation for the edge v1,v2 of constraint[cIndex]
(package private) void	fillChildren(int nodeIndex) fillChildren: Mark the child nodes as markup.
SpatialConstraint	getConstraint(int c)
SpatialVector	getCorner(int c)
int	getNumberOfConstraints()
void	intersect(SpatialIndex idx, SpatialMarkup markup, java.util.BitSet partial, java.util.BitSet full) Intersect with index.
void	intersect(SpatialIndex idx, SpatialMarkup markup, java.util.List partial, java.util.List full) Same intersection, but the result is given in a list of nodes.
(package private) int	NC(int n, int m)
void	read(java.io.Reader in)
void	readRaDec(java.io.Reader in)
(package private) void	setfull(int id, int level) setfull: set the bitlist leaves at level maxlevel to full.
(package private) void	simplify() simplify: We have the following decision tree for the simplification of convexes: Always test two constraints against each other.
(package private) void	simplify0() simplify0: simplify zERO convexes.
(package private) boolean	testBoundingCircle(SpatialVector v0, SpatialVector v1, SpatialVector v2) Test if bounding circle intersects with a constraint
(package private) boolean	testConstraintInside(SpatialVector v0, SpatialVector v1, SpatialVector v2, int cIndex) Test for a constraint lying inside or outside of triangle
(package private) int	testConstraints(int i, int j) Test for constraint relative position; intersect, one in the other, disjoint.
(package private) boolean	testEdge(SpatialVector v0, SpatialVector v1, SpatialVector v2) testEdge: look whether one of the constraints intersects with one of the edges of node with the corners v0,v1,v2.
(package private) boolean	testEdge0(SpatialVector v0, SpatialVector v1, SpatialVector v2) testEdge0: test the edges of the triangle against the edges of the zERO convex.
(package private) boolean	testEdgeConstraint(SpatialVector v0, SpatialVector v1, SpatialVector v2, int cIndex) Test if a constraint intersects the edges
(package private) boolean	testHole(SpatialVector v0, SpatialVector v1, SpatialVector v2) testHole : look for 'holes', i.e.
(package private) short	testNode(int nodeIndex) the same routine as above, but for a given saved node
(package private) short	testNode(SpatialVector v0, SpatialVector v1, SpatialVector v2) test each SpatialQuadNode for intersections.
(package private) int	testOtherPosNone(SpatialVector v0, SpatialVector v1, SpatialVector v2) Look for any positive constraint that does not intersect the edges
(package private) void	testPartial(int level, int id, SpatialVector v0, SpatialVector v1, SpatialVector v2) test a triangle's subtriangles whether they are partial.
(package private) void	testSubTriangle(int level, int id, SpatialVector v0, SpatialVector v1, SpatialVector v2) testSubTriangle: call full or partial depending on result of testNode.
(package private) short	testTriangle(SpatialVector v0, SpatialVector v1, SpatialVector v2, int vsum) testTriangle: tests a triangle given by 3 vertices if it intersects the convex.
(package private) boolean	testVectorInside(SpatialVector v0, SpatialVector v1, SpatialVector v2, SpatialVector v) Test for a vector lying inside or outside of triangle For vectors abc, if (a ^ b * c) < 0, abc are ordered clockwise.
(package private) int	testVertex(int vIndex) Test if vertices are inside the convex for a saved node.
(package private) int	testVertex(SpatialVector v)
java.lang.String	toString()
(package private) short	triangleTest(int nodeIndex) triangleTest: this is the main test of a triangle vs a Convex.

Methods inherited from class jhu.htmIndex.SpatialSign

printSign

Methods inherited from class java.lang.Object

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

Field Detail

constraints_

java.util.List constraints_

corners_

java.util.List corners_

index_

SpatialIndex index_

markup_

SpatialMarkup markup_

boundingCircle_

SpatialConstraint boundingCircle_

addlevel_

int addlevel_

full_

java.util.BitSet full_

partial_

java.util.BitSet partial_

flist_

java.util.List flist_

plist_

java.util.List plist_

bitresult_

boolean bitresult_

Constructor Detail

SpatialConvex

public SpatialConvex()

Default Constructor

SpatialConvex

public SpatialConvex(SpatialVector v1,
                     SpatialVector v2,
                     SpatialVector v3)

Constructor from a triangle Initialize domain from a triangle. The corners of these vectors form a triangle, so we just add three ZERO convexes to the domain where the direction is given by the cross product of the corners. Of course, the sign has to be determined (on which side of the triangle are we?) If the three points lie on one line, no convexes are added.

SpatialConvex

public SpatialConvex(SpatialVector v1,
                     SpatialVector v2,
                     SpatialVector v3,
                     SpatialVector v4)

Constructor from a rectangle Initialize convex from a rectangle. The vectors that form a rectangle may be in any order, the code finds the edges by itself. If one of the vectors lies within the triangle formed by the other three vectors, the previous constructor is used.

Method Detail

add

public void add(SpatialConstraint c)

Add a constraint

simplify0

void simplify0()

simplify0: simplify zERO convexes. calculate corners of convex and the bounding circle. zERO convexes are made up of constraints which are all great circles. It can happen that some of the constraints are redundant. For example, if 3 of the great circles define a triangle as the convex which lies fully inside the half sphere of the fourth constraint, that fourth constraint is redundant and will be removed. The algorithm is the following: zero-constraints are half-spheres, defined by a single normalized vector v, pointing in the direction of that half-sphere. Two zero-constraints intersect at i = +- v x v 1,2 1 2 the vector cross product of their two defining vectors. The two vectors i1,2 are tested against every other constraint in the convex if they lie within their half-spheres. Those intersections i which lie within every other constraint, are stored into corners_. Constraints that do not have a single corner on them, are dropped.

simplify

void simplify()

simplify: We have the following decision tree for the simplification of convexes: Always test two constraints against each other. We have If both constraints are pOS If they intersect: keep both If one lies in the other: drop the larger one Else: disjunct. Empty convex, stop. If both constraints are nEG If they intersect or are disjunct: ok Else: one lies in the other, drop smaller 'hole' Mixed: one pOS, one nEG No intersection, disjunct: pOS is redundant Intersection: keep both pOS within nEG: empty convex, stop. nEG within pOS: keep both.

testConstraints

int testConstraints(int i,
                    int j)

Test for constraint relative position; intersect, one in the other, disjoint. testConstraints: Test for the relative position of two constraints. Returns 0 if they intersect Returns -1 if they are disjoint Returns 1 if j is in i Returns 2 if i is in j

intersect

public void intersect(SpatialIndex idx,
                      SpatialMarkup markup,
                      java.util.BitSet partial,
                      java.util.BitSet full)

Intersect with index. The partial and full bitlists for the result have to be given. The markup accelerates the intersection for the index that is in memory, but is not used for the dynamically built triangles. If the conves occupies a large percent of the area of the sphere, bitlists are the preferred result method.

intersect

public void intersect(SpatialIndex idx,
                      SpatialMarkup markup,
                      java.util.List partial,
                      java.util.List full)

Same intersection, but the result is given in a list of nodes. If the conves is very small, this is the preferred result method.

doIntersect

void doIntersect()

Do the intersection (common function for overloaded intersect())

triangleTest

short triangleTest(int nodeIndex)

triangleTest: this is the main test of a triangle vs a Convex. It will properly mark up the flags for the triangular node[index], and all its children

fillChildren

void fillChildren(int nodeIndex)

fillChildren: Mark the child nodes as markup.

setfull

void setfull(int id,
             int level)

setfull: set the bitlist leaves at level maxlevel to full. if we have still levels to go, recurse. Use the id to get the leaf node's index. See idbyname and namebyid for explanations.

testPartial

void testPartial(int level,
                 int id,
                 SpatialVector v0,
                 SpatialVector v1,
                 SpatialVector v2)

test a triangle's subtriangles whether they are partial. If level is nonzero, recurse: subdivide the triangle according to our rules and test each subdivision. (our rules are: each subdivided triangle has to be given ordered counter-clockwise, 0th index starts off new 0-node, 1st index starts off new 1-node, 2nd index starts off new 2-node middle triangle gives new 3-node.) if we are at the bottom, set this id's leafindex in partial bitlist.

testSubTriangle

void testSubTriangle(int level,
                     int id,
                     SpatialVector v0,
                     SpatialVector v1,
                     SpatialVector v2)

testSubTriangle: call full or partial depending on result of testNode.

testNode

short testNode(SpatialVector v0,
               SpatialVector v1,
               SpatialVector v2)

test each SpatialQuadNode for intersections. Calls testTriangle after having tested the vertices using testVertex.

testNode

short testNode(int nodeIndex)

the same routine as above, but for a given saved node

testTriangle

short testTriangle(SpatialVector v0,
                   SpatialVector v1,
                   SpatialVector v2,
                   int vsum)

testTriangle: tests a triangle given by 3 vertices if it intersects the convex. Here the whole logic of deciding whether it is partial, full, swallowed or unknown is handled.

testVertex

int testVertex(int vIndex)

Test if vertices are inside the convex for a saved node. makes use of the markup (this is where the speedup occurs)

testVertex

int testVertex(SpatialVector v)

testHole

boolean testHole(SpatialVector v0,
                 SpatialVector v1,
                 SpatialVector v2)

testHole : look for 'holes', i.e. negative constraints that have their centers inside the node with the three corners v0,v1,v2.

testEdge0

boolean testEdge0(SpatialVector v0,
                  SpatialVector v1,
                  SpatialVector v2)

testEdge0: test the edges of the triangle against the edges of the zERO convex. The convex is stored in corners_ so that the convex is always on the left-hand-side of an edge corners_(i) - corners_(i+1). (just like the triangles). This makes testing for intersections with the edges easy.

testEdge

boolean testEdge(SpatialVector v0,
                 SpatialVector v1,
                 SpatialVector v2)

testEdge: look whether one of the constraints intersects with one of the edges of node with the corners v0,v1,v2.

eSolve

boolean eSolve(SpatialVector v1,
               SpatialVector v2,
               int cIndex)

eSolve: solve the quadratic equation for the edge v1,v2 of constraint[cIndex]

testBoundingCircle

boolean testBoundingCircle(SpatialVector v0,
                           SpatialVector v1,
                           SpatialVector v2)

Test if bounding circle intersects with a constraint

testEdgeConstraint

boolean testEdgeConstraint(SpatialVector v0,
                           SpatialVector v1,
                           SpatialVector v2,
                           int cIndex)

Test if a constraint intersects the edges

testOtherPosNone

int testOtherPosNone(SpatialVector v0,
                     SpatialVector v1,
                     SpatialVector v2)

Look for any positive constraint that does not intersect the edges

testConstraintInside

boolean testConstraintInside(SpatialVector v0,
                             SpatialVector v1,
                             SpatialVector v2,
                             int cIndex)

Test for a constraint lying inside or outside of triangle

testVectorInside

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

Test for a vector lying inside or outside of triangle For vectors abc, if (a ^ b * c) < 0, abc are ordered clockwise. -> center c not inside triangle, since vertices are ordered counter-clockwise.

getConstraint

public SpatialConstraint getConstraint(int c)

getNumberOfConstraints

public int getNumberOfConstraints()

getCorner

public SpatialVector getCorner(int c)

NC

int NC(int n,
       int m)

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object

read

public void read(java.io.Reader in)
          throws java.io.IOException

readRaDec

public void readRaDec(java.io.Reader in)
               throws java.io.IOException