# Kstars

HTMesh.h
1/*
2 SPDX-FileCopyrightText: 2007 James B. Bowlin <bowlin@mindspring.com>
4*/
5
6// FIXME? We are needlessly copying the trixel data into the buffer during
7// indexing. One way to fix this is to give HTMesh next() and hasNext()
8// methods. This would also involve moving the convex and the range off the
9// stack and back to the heap when the indexing methods are called for indexing
10// and not drawing. Let's wait.
11
12#ifndef HTMESH_H
13#define HTMESH_H
14
15#include <cstdio>
16#include "typedef.h"
17
18class SpatialIndex;
19class RangeConvex;
20class MeshIterator;
21class MeshBuffer;
22
23/**
24 * @class HTMesh
25 * HTMesh was originally intended to be a simple interface to the HTM
26 * library for the KStars project that would hide some of the complexity. But
27 * it has gained some complexity of its own.
28 *
29 * The most complex addition was the routine that performs an intersection on a
30 * line segment, finding all the trixels that cover the line. Perhaps there is
31 * an easier and faster way to do it. Right now we convert to cartesian
32 * coordinates to take the cross product of the two input vectors in order to
33 * create a perpendicular which is used to form a very narrow triangle that
34 * contains the original line segment as one of its long legs.
35 *
36 * Error detection and prevention added a little bit more complexity. The raw
37 * HTM library is vulnerable to misbehavior if the polygon intersection routines
38 * are given duplicate consecutive points, including the first point of a
39 * polygon duplicating the last point. We test for duplicated points now. If
40 * they are found, we drop down to the intersection routine with one fewer
41 * vertices, ending at the line segment. If the two ends of a line segment are
42 * much close together than the typical edge of a trixel then we simply index
43 * each point separately and the result set is consists of the union of these
44 * two trixels.
45 *
46 * The final (I hope) level of complexity was the addition of multiple results
47 * buffers. You can set the number of results buffers in the HTMesh
48 * constructor. Since each buffer has to be able to hold one integer for each
49 * trixel in the mesh, multiple buffers can quickly eat up memory. The default
50 * is just one buffer and all routines that use the buffers default to using the
51 * just the first buffer.
52 *
53 * NOTE: all Right Ascensions (ra) and Declinations (dec) are in degrees.
54 */
55
56class HTMesh
57{
58 public:
59 /** @short constructor.
60 * @param level is passed on to the underlying SpatialIndex
61 * @param buildLevel is also passed on to the SpatialIndex
62 * @param numBuffers controls how many output buffers are created. Don't
63 * use more than require because they eat up mucho RAM. The default is
64 * just one output buffer.
65 */
66 HTMesh(int level, int buildLevel, int numBuffers = 1);
67
68 ~HTMesh();
69
70 /** @short returns the index of the trixel that contains the specified
71 * point.
72 */
73 Trixel index(double ra, double dec) const;
74
75 /** NOTE: The intersect() routines below are all used to find the trixels
76 * needed to cover a geometric object: circle, line, triangle, and
77 * quadrilateral. Since the number of trixels needed can be large and is
78 * not known a priori, you must construct a MeshIterator to iterate over
79 * the trixels that are the result of any of these 4 calculations.
80 *
81 * The HTMesh is created with one or more output buffers used for storing
82 * the results. You can specify which output buffer is to be used to hold
83 * the results by supplying an optional integer bufNum parameter.
84 */
85
86 /**
87 *@short finds the trixels that cover the specified circle
88 *@param ra Central ra in degrees
89 *@param dec Central dec in degrees
91 *@param bufNum the output buffer to hold the results
92 *@note You will need to supply unprecessed (ra, dec) in most
93 * situations. Please see SkyMesh::aperture()'s code before
94 * messing with this method.
95 */
96 void intersect(double ra, double dec, double radius, BufNum bufNum = 0);
97
98 /** @short finds the trixels that cover the specified line segment
99 */
100 void intersect(double ra1, double dec1, double ra2, double dec2, BufNum bufNum = 0);
101
102 /** @short find the trixels that cover the specified triangle
103 */
104 void intersect(double ra1, double dec1, double ra2, double dec2, double ra3, double dec3, BufNum bufNum = 0);
105
106 /** @short finds the trixels that cover the specified quadrilateral
107 */
108 void intersect(double ra1, double dec1, double ra2, double dec2, double ra3, double dec3, double ra4, double dec4,
109 BufNum bufNum = 0);
110
111 /** @short returns the number of trixels in the result buffer bufNum.
112 */
113 int intersectSize(BufNum bufNum = 0);
114
115 /** @short returns the total number of trixels in the HTM. This number
116 * is 8 * 4^level.
117 */
118 int size() const { return numTrixels; }
119
120 /** @short returns the mesh level.
121 */
122 int level() const { return m_level; }
123
124 /** @short sets the debug level which is used to print out intermediate
125 * results in the line intersection routine.
126 */
127 void setDebug(int debug) { htmDebug = debug; }
128
129 /** @short returns a pointer to the MeshBuffer specified by bufNum.
130 * Currently this is only used in the MeshIterator constructor.
131 */
132 MeshBuffer *meshBuffer(BufNum bufNum = 0);
133
134 void vertices(Trixel id, double *ra1, double *dec1, double *ra2, double *dec2, double *ra3, double *dec3);
135
136 private:
137 const char *name;
138 SpatialIndex *htm;
139 int m_level, m_buildLevel;
140 int numTrixels, magicNum;
141
142 // These store the result sets:
143 MeshBuffer **m_meshBuffer;
144 BufNum m_numBuffers;
145
147 double edge, edge10, eps;
148
149 int htmDebug;
150
151 /** @short fills the specified buffer with the intersection results in the
152 * RangeConvex.
153 */
154 bool performIntersection(RangeConvex *convex, BufNum bufNum = 0);
155
156 /** @short users can only use the allocated buffers
157 */
158 inline bool validBufNum(BufNum bufNum)
159 {
160 if (bufNum < m_numBuffers)
161 return true;
162 fprintf(stderr, "%s: bufNum: %d >= numBuffers: %d\n", name, bufNum, m_numBuffers);
163 return false;
164 }
165
166 /** @short used by the line intersection routine. Maybe there is a
167 * simpler and faster approach that does not require this conversion.
168 */
169 void toXYZ(double ra, double dec, double *x, double *y, double *z);
170};
171
172#endif
HTMesh was originally intended to be a simple interface to the HTM library for the KStars project tha...
Definition HTMesh.h:57
HTMesh(int level, int buildLevel, int numBuffers=1)
constructor.
Definition HTMesh.cpp:22
int size() const
returns the total number of trixels in the HTM.
Definition HTMesh.h:118
void setDebug(int debug)
sets the debug level which is used to print out intermediate results in the line intersection routine...
Definition HTMesh.h:127
Trixel index(double ra, double dec) const
returns the index of the trixel that contains the specified point.
Definition HTMesh.cpp:72
int level() const
returns the mesh level.
Definition HTMesh.h:122
int intersectSize(BufNum bufNum=0)
returns the number of trixels in the result buffer bufNum.
Definition HTMesh.cpp:262
void intersect(double ra, double dec, double radius, BufNum bufNum=0)
NOTE: The intersect() routines below are all used to find the trixels needed to cover a geometric obj...
Definition HTMesh.cpp:104
MeshBuffer * meshBuffer(BufNum bufNum=0)
returns a pointer to the MeshBuffer specified by bufNum.
Definition HTMesh.cpp:255
The sole purpose of a MeshBuffer is to hold storage space for the results of an HTM inetersection and...
Definition MeshBuffer.h:24
MeshIterator is a very lightweight class used to iterate over the result set of an HTMesh intersectio...
A spatial convex is composed of spatial constraints.
Definition RangeConvex.h:60
SpatialIndex is a quad tree of spherical triangles.
This file is part of the KDE documentation.