File indexing completed on 2024-04-28 07:31:40
0001 /* 0002 SPDX-FileCopyrightText: 2007 James B. Bowlin <bowlin@mindspring.com> 0003 SPDX-License-Identifier: BSD-3-Clause AND GPL-2.0-or-later 0004 */ 0005 0006 // FIXME? We are needlessly copying the trixel data into the buffer during 0007 // indexing. One way to fix this is to give HTMesh next() and hasNext() 0008 // methods. This would also involve moving the convex and the range off the 0009 // stack and back to the heap when the indexing methods are called for indexing 0010 // and not drawing. Let's wait. 0011 0012 #ifndef HTMESH_H 0013 #define HTMESH_H 0014 0015 #include <cstdio> 0016 #include "typedef.h" 0017 0018 class SpatialIndex; 0019 class RangeConvex; 0020 class MeshIterator; 0021 class MeshBuffer; 0022 0023 /** 0024 * @class HTMesh 0025 * HTMesh was originally intended to be a simple interface to the HTM 0026 * library for the KStars project that would hide some of the complexity. But 0027 * it has gained some complexity of its own. 0028 * 0029 * The most complex addition was the routine that performs an intersection on a 0030 * line segment, finding all the trixels that cover the line. Perhaps there is 0031 * an easier and faster way to do it. Right now we convert to cartesian 0032 * coordinates to take the cross product of the two input vectors in order to 0033 * create a perpendicular which is used to form a very narrow triangle that 0034 * contains the original line segment as one of its long legs. 0035 * 0036 * Error detection and prevention added a little bit more complexity. The raw 0037 * HTM library is vulnerable to misbehavior if the polygon intersection routines 0038 * are given duplicate consecutive points, including the first point of a 0039 * polygon duplicating the last point. We test for duplicated points now. If 0040 * they are found, we drop down to the intersection routine with one fewer 0041 * vertices, ending at the line segment. If the two ends of a line segment are 0042 * much close together than the typical edge of a trixel then we simply index 0043 * each point separately and the result set is consists of the union of these 0044 * two trixels. 0045 * 0046 * The final (I hope) level of complexity was the addition of multiple results 0047 * buffers. You can set the number of results buffers in the HTMesh 0048 * constructor. Since each buffer has to be able to hold one integer for each 0049 * trixel in the mesh, multiple buffers can quickly eat up memory. The default 0050 * is just one buffer and all routines that use the buffers default to using the 0051 * just the first buffer. 0052 * 0053 * NOTE: all Right Ascensions (ra) and Declinations (dec) are in degrees. 0054 */ 0055 0056 class HTMesh 0057 { 0058 public: 0059 /** @short constructor. 0060 * @param level is passed on to the underlying SpatialIndex 0061 * @param buildLevel is also passed on to the SpatialIndex 0062 * @param numBuffers controls how many output buffers are created. Don't 0063 * use more than require because they eat up mucho RAM. The default is 0064 * just one output buffer. 0065 */ 0066 HTMesh(int level, int buildLevel, int numBuffers = 1); 0067 0068 ~HTMesh(); 0069 0070 /** @short returns the index of the trixel that contains the specified 0071 * point. 0072 */ 0073 Trixel index(double ra, double dec) const; 0074 0075 /** NOTE: The intersect() routines below are all used to find the trixels 0076 * needed to cover a geometric object: circle, line, triangle, and 0077 * quadrilateral. Since the number of trixels needed can be large and is 0078 * not known a priori, you must construct a MeshIterator to iterate over 0079 * the trixels that are the result of any of these 4 calculations. 0080 * 0081 * The HTMesh is created with one or more output buffers used for storing 0082 * the results. You can specify which output buffer is to be used to hold 0083 * the results by supplying an optional integer bufNum parameter. 0084 */ 0085 0086 /** 0087 *@short finds the trixels that cover the specified circle 0088 *@param ra Central ra in degrees 0089 *@param dec Central dec in degrees 0090 *@param radius Radius of the circle in degrees 0091 *@param bufNum the output buffer to hold the results 0092 *@note You will need to supply unprecessed (ra, dec) in most 0093 * situations. Please see SkyMesh::aperture()'s code before 0094 * messing with this method. 0095 */ 0096 void intersect(double ra, double dec, double radius, BufNum bufNum = 0); 0097 0098 /** @short finds the trixels that cover the specified line segment 0099 */ 0100 void intersect(double ra1, double dec1, double ra2, double dec2, BufNum bufNum = 0); 0101 0102 /** @short find the trixels that cover the specified triangle 0103 */ 0104 void intersect(double ra1, double dec1, double ra2, double dec2, double ra3, double dec3, BufNum bufNum = 0); 0105 0106 /** @short finds the trixels that cover the specified quadrilateral 0107 */ 0108 void intersect(double ra1, double dec1, double ra2, double dec2, double ra3, double dec3, double ra4, double dec4, 0109 BufNum bufNum = 0); 0110 0111 /** @short returns the number of trixels in the result buffer bufNum. 0112 */ 0113 int intersectSize(BufNum bufNum = 0); 0114 0115 /** @short returns the total number of trixels in the HTM. This number 0116 * is 8 * 4^level. 0117 */ 0118 int size() const { return numTrixels; } 0119 0120 /** @short returns the mesh level. 0121 */ 0122 int level() const { return m_level; } 0123 0124 /** @short sets the debug level which is used to print out intermediate 0125 * results in the line intersection routine. 0126 */ 0127 void setDebug(int debug) { htmDebug = debug; } 0128 0129 /** @short returns a pointer to the MeshBuffer specified by bufNum. 0130 * Currently this is only used in the MeshIterator constructor. 0131 */ 0132 MeshBuffer *meshBuffer(BufNum bufNum = 0); 0133 0134 void vertices(Trixel id, double *ra1, double *dec1, double *ra2, double *dec2, double *ra3, double *dec3); 0135 0136 private: 0137 const char *name; 0138 SpatialIndex *htm; 0139 int m_level, m_buildLevel; 0140 int numTrixels, magicNum; 0141 0142 // These store the result sets: 0143 MeshBuffer **m_meshBuffer; 0144 BufNum m_numBuffers; 0145 0146 double degree2Rad; 0147 double edge, edge10, eps; 0148 0149 int htmDebug; 0150 0151 /** @short fills the specified buffer with the intersection results in the 0152 * RangeConvex. 0153 */ 0154 bool performIntersection(RangeConvex *convex, BufNum bufNum = 0); 0155 0156 /** @short users can only use the allocated buffers 0157 */ 0158 inline bool validBufNum(BufNum bufNum) 0159 { 0160 if (bufNum < m_numBuffers) 0161 return true; 0162 fprintf(stderr, "%s: bufNum: %d >= numBuffers: %d\n", name, bufNum, m_numBuffers); 0163 return false; 0164 } 0165 0166 /** @short used by the line intersection routine. Maybe there is a 0167 * simpler and faster approach that does not require this conversion. 0168 */ 0169 void toXYZ(double ra, double dec, double *x, double *y, double *z); 0170 }; 0171 0172 #endif