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