File indexing completed on 2024-03-24 15:17:07
0001 #ifndef _RangeConvex_h 0002 #define _RangeConvex_h 0003 0004 //# Filename: RangeConvex.h 0005 //# 0006 //# Classes defined here: RangeConvex 0007 //# 0008 //# 0009 //# Author: Peter Z. Kunszt, based on A. Szalay's code 0010 //# 0011 //# Date: October 16, 1998 0012 //# 0013 //# SPDX-FileCopyrightText: 2000 Peter Z. Kunszt Alex S. Szalay, Aniruddha R. Thakar 0014 //# The Johns Hopkins University 0015 //# 0016 //# Modification History: 0017 //# 0018 //# Oct 18, 2001 : Dennis C. Dinge -- Replaced ValVec with std::vector 0019 //# 0020 0021 class RangeConvex; 0022 class SpatialConstraint; 0023 class SpatialSign; 0024 0025 #include "SpatialConstraint.h" 0026 #include "SpatialIndex.h" 0027 #include "SpatialSign.h" 0028 0029 #include <HtmRange.h> 0030 0031 typedef std::vector<uint64> ValueVectorUint64; 0032 0033 /** Enumerator. Define the return values of an intersection */ 0034 0035 enum SpatialMarkup 0036 { 0037 /// Uncertain 0038 dONTKNOW, 0039 /// Triangle partially intersected 0040 pARTIAL, 0041 /// All of the triangle is inside queried area 0042 fULL, 0043 /// Triangle is outside the queried area 0044 rEJECT 0045 }; 0046 0047 //######################################################################## 0048 //# 0049 //# Spatial Convex class 0050 //# 0051 /** 0052 A spatial convex is composed of spatial constraints. It does not 0053 necessarily define a continuous area on the sphere since it is a 0054 3D-convex of planar intersections which may intersect with the 0055 unit sphere at disjoint locations. Especially 'negative' 0056 constraints tend to tear 'holes' into the convex area. 0057 */ 0058 0059 class LINKAGE RangeConvex 0060 { 0061 public: 0062 /// Default Constructor 0063 RangeConvex(); 0064 0065 /// Constructor from a triangle 0066 RangeConvex(const SpatialVector *v1, const SpatialVector *v2, const SpatialVector *v3); 0067 0068 /// Constructor from a rectangle 0069 RangeConvex(const SpatialVector *v1, const SpatialVector *v2, const SpatialVector *v3, const SpatialVector *v4); 0070 0071 /// Add a constraint 0072 void add(SpatialConstraint &); 0073 0074 /// Simplify the convex, remove redundancies 0075 void simplify(); 0076 0077 /** Intersect with index. Result is given in a list of nodes. */ 0078 void intersect(const SpatialIndex *index, HtmRange *hr); 0079 0080 void setOlevel(int level) { olevel = level; }; 0081 0082 protected: 0083 HtmRange *hr; 0084 int olevel; 0085 Sign sign_ { zERO }; 0086 0087 // Do the intersection (common function for overloaded intersect()) 0088 // Simplification routine for zERO convexes. This is called by 0089 // simplify() in case we have all zERO constraints. 0090 void simplify0(); 0091 0092 // saveTrixel: saves the given htmid for later output 0093 void saveTrixel(uint64 htmid); 0094 0095 // testTrixel: Test the nodes of the index if the convex hits it 0096 // the argument gives the index of the nodes_ array to specify the QuadNode 0097 SpatialMarkup testTrixel(uint64 nodeIndex); 0098 0099 // test each quadnode for intersections. Calls testTriangle after having 0100 // tested the vertices using testVertex. 0101 SpatialMarkup testNode(uint64 id); 0102 0103 // SpatialMarkup testNode(const struct SpatialIndex::QuadNode *indexNode); 0104 SpatialMarkup testNode(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0105 0106 // testTriangle: tests a triangle given by 3 vertices if 0107 // it intersects the convex. Here the whole logic of deciding 0108 // whether it is partial, full, swallowed or unknown is handled. 0109 SpatialMarkup testTriangle(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2, int vsum); 0110 0111 // test a triangle's subtriangles whether they are partial. 0112 // If level is nonzero, recurse: subdivide the 0113 // triangle according to our rules and test each subdivision. 0114 // (our rules are: each subdivided triangle has to be given 0115 // ordered counter-clockwise, 0th index starts off new 0-node, 0116 // 1st index starts off new 1-node, 2nd index starts off new 2-node 0117 // middle triangle gives new 3-node.) 0118 // if we are at the bottom, set this id's leafindex in partial bitlist. 0119 void testPartial(size_t level, uint64 id, const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2, 0120 int previousPartials); 0121 0122 // Test for constraint relative position; intersect, one in the 0123 // other, disjoint. 0124 int testConstraints(size_t i, size_t j); 0125 0126 // Test if vertices are inside the convex for a node. 0127 int testVertex(const SpatialVector &v); 0128 int testVertex(const SpatialVector *v); 0129 0130 // testHole : look for 'holes', i.e. negative constraints that have their 0131 // centers inside the node with the three corners v0,v1,v2. 0132 bool testHole(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0133 0134 // testEdge0: test the edges of the triangle against the edges of the 0135 // zERO convex. The convex is stored in corners_ so that the convex 0136 // is always on the left-hand-side of an edge corners_(i) - corners_(i+1). 0137 // (just like the triangles). This makes testing for intersections with 0138 // the edges easy. 0139 bool testEdge0(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0140 0141 // testEdge: look whether one of the constraints intersects with one of 0142 // the edges of node with the corners v0,v1,v2. 0143 bool testEdge(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0144 0145 // eSolve: solve the quadratic equation for the edge v1,v2 of 0146 // constraint[cIndex] 0147 bool eSolve(const SpatialVector &v1, const SpatialVector &v2, size_t cIndex); 0148 0149 // Test if bounding circle intersects with a constraint 0150 bool testBoundingCircle(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0151 0152 // Test if a constraint intersects the edges 0153 bool testEdgeConstraint(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2, size_t cIndex); 0154 0155 // Look for any positive constraint that does not intersect the edges 0156 size_t testOtherPosNone(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2); 0157 0158 // Test for a constraint lying inside or outside of triangle 0159 bool testConstraintInside(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2, size_t cIndex); 0160 0161 // Test for a vector lying inside or outside of triangle 0162 bool testVectorInside(const SpatialVector &v0, const SpatialVector &v1, const SpatialVector &v2, SpatialVector &v); 0163 0164 std::vector<SpatialConstraint> constraints_; // The vector of constraints 0165 const SpatialIndex *index_; // A pointer to the index 0166 std::vector<SpatialVector> corners_; 0167 SpatialConstraint boundingCircle_; // For zERO convexes, the bc. 0168 size_t addlevel_; // additional levels to calculate 0169 ValueVectorUint64 *plist_; // list of partial node ids 0170 private: 0171 // Disallow copying and assignemnt 0172 RangeConvex(const RangeConvex &); 0173 RangeConvex &operator=(const RangeConvex &); 0174 }; 0175 0176 #endif