source: Revenant/marslib/include/mars_geometry.h@ 7ef8ec4

port/mars-tycoon
Last change on this file since 7ef8ec4 was 80a6a52, checked in by Jonathan Neufeld <support@…>, 3 years ago

Get to a compile state for terrain procedural generation
  • Property mode set to 100755
File size: 6.9 KB
Line 
1#pragma once
2
3#include <vector>
4#include <limits>
5
6#include "mars_linalg.h"
7#include "mars_ptr.h"
8
9namespace mars
10{
11 class GuideEx : public std::exception {};
12
13 template <typename V, typename T>
14 class BasicGuide
15 {
16 public:
17 typedef typename std::vector< V > PointList;
18 typedef typename PointList::value_type Point;
19
20 class SegmentType : public PointList::const_iterator
21 {
22 private:
23 unsigned int _index;
24
25 public:
26 inline SegmentType () {}
27 inline SegmentType (const SegmentType & copy)
28 : PointList::const_iterator(copy), _index(copy._index) {}
29
30 inline SegmentType & operator++()
31 {
32 PointList::const_iterator::operator++();
33 ++_index;
34 return *this;
35 }
36 inline SegmentType operator++(int)
37 {
38 SegmentType old = *this;
39
40 PointList::const_iterator::operator++();
41 _index++;
42 return old;
43 }
44 inline SegmentType & operator--()
45 {
46 PointList::const_iterator::operator--();
47 --_index;
48 return *this;
49 }
50 inline SegmentType operator--(int)
51 {
52 SegmentType old = *this;
53
54 PointList::const_iterator::operator--();
55 _index--;
56 return old;
57 }
58 inline bool operator != (const SegmentType & other) const { return _index != other._index; }
59 inline bool operator == (const SegmentType & other) const { return _index == other._index; }
60
61 inline unsigned int index () const { return _index; }
62
63 private:
64 SegmentType (const typename PointList::const_iterator & i, unsigned int idx) : PointList::const_iterator(i), _index (idx) {}
65
66 friend class BasicGuide;
67 };
68
69 class DistanceType
70 {
71 public:
72 const SegmentType segment;
73 const T distance;
74 const V point;
75
76 private:
77 inline DistanceType (const V & p, const T dist, const SegmentType & seg)
78 : segment(seg), distance(dist), point(p) {}
79
80 friend class BasicGuide;
81
82 public:
83
84 inline float time () const
85 {
86 const T
87 a = MAGSQ(point - *segment),
88 b = MAGSQ(point - *(segment + 1));
89
90 return a / (a + b);
91 }
92 };
93
94 private:
95 inline T dist2Segment (
96 const mars::vector3D< T > & grSeg,
97 const mars::vector3D< T > & dp
98 ) const
99 {
100 return abs(MAGSQ(grSeg & dp) / MAGSQ(grSeg));
101 }
102 inline T dist2Segment (
103 const mars::vector2D< T > & grSeg,
104 const mars::vector2D< T > & dp
105 ) const
106 {
107 return abs(((grSeg & 1) * dp) / MAGSQ(grSeg));
108 }
109
110 protected:
111 PointList _points;
112
113 public:
114 inline BasicGuide (const PointList & points)
115 : _points (points) {}
116
117 inline BasicGuide (const Point & a, const Point & b)
118 {
119 _points.push_back(a);
120 _points.push_back(b);
121 }
122
123 inline const PointList & points () const { return _points; }
124 inline const Point & front () const { return _points.front(); }
125 inline const Point & back () const { return _points.back(); }
126 inline SegmentType begin () const { return SegmentType(_points.begin(), 0); }
127 inline SegmentType end () const { return SegmentType(_points.end(), _points.size()); }
128 void offsetBy (const V & p)
129 {
130 for (typename PointList::iterator i = _points.begin(); i != _points.end(); ++i)
131 *i += p;
132 }
133
134 inline DistanceType operator - (const V & p) const { return distance(p, _points.begin()); }
135 inline DistanceType distance (const V & p, const SegmentType & i) const
136 {
137 const SegmentType
138 inpt = nearestPoint(i, p),
139 insg = nearestSegmentHead(inpt, p);
140
141 return DistanceType
142 (
143 p,
144 dist2Segment(grad(insg), p - *insg),
145 insg
146 );
147 }
148
149 // Presuming that it was already determined that the specified point is closest to the point indicated by the specified iterator, this method
150 // determines the segment that the point is closer to, either the segment following or preceding the point indicated by the specified iterator
151 // NOTE: it is most sensible calling this method immediately after calling "nearestPoint" in order to determine the segment within this guide
152 // that is closest to an arbitrary point.
153 SegmentType nearestSegmentHead ( const SegmentType & from, const V & p) const
154 {
155 if (static_cast <typename PointList::const_iterator> (from) == _points.begin())
156 return from;
157 else
158 {
159 SegmentType ia = from, ib = from;
160
161 --ia;
162 ++ib;
163
164 if (static_cast <typename PointList::const_iterator> (ib) == _points.end())
165 return ia;
166 else
167 {
168 const T
169 ma = MAGSQ(*(ia) - p),
170 mb = MAGSQ(*(ib) - p);
171
172 if (ma < mb)
173 return ia;
174 else
175 return from;
176 }
177 }
178 }
179
180 // Iterates through all of the points in the guide and returns the iterator to the point that is closest to the specified point
181 SegmentType nearestPoint( SegmentType from, const V & p ) const
182 {
183 T mag = -1;
184 SegmentType iret, iend;
185
186 iend = iret = SegmentType(_points.end(), _points.size());
187
188 while (from != iend)
189 {
190 const T m = MAGSQ(*from - p);
191 if (mag < 0 || m < mag)
192 {
193 mag = m;
194 iret = from++;
195 } else
196 ++from;
197 }
198 return iret;
199 }
200
201 inline V grad (const typename PointList::const_iterator & seg) const
202 {
203 return tail(seg) - *seg;
204 }
205
206 // Returns the tail-end of the specified segment
207 inline V tail (typename PointList::const_iterator seg) const
208 {
209 typename PointList::const_iterator last = seg++;
210
211 return seg == end() ? *last : *seg;
212 }
213
214 inline BasicGuide & operator = (const PointList & points)
215 {
216 _points = points;
217 // XTODO: Implement QuadTree::clear()
218 // _qtree.clear();
219 return *this;
220 }
221 };
222
223 template <class Derived, typename V, typename T>
224 class TreeGuideNode;
225
226 template <class Derived, typename V, typename T>
227 class TreeGuideNode : public BasicGuide <V, T>
228 {
229 public:
230 typedef std::vector < ptr< Derived > > KidList;
231
232 private:
233 const TreeGuideNode * _parent;
234 KidList _kids;
235
236 public:
237 typedef typename std::vector< V > PointList;
238 typedef typename PointList::value_type Point;
239
240 inline TreeGuideNode (const PointList & points)
241 : BasicGuide<V, T> (points), _parent(NULL) {}
242
243 inline TreeGuideNode (const PointList & points, const TreeGuideNode & parent)
244 : BasicGuide<V, T>(points), _parent(&parent) {}
245
246 inline TreeGuideNode (const Point & a, const Point & b)
247 : BasicGuide<V, T>(a, b), _parent (NULL) {}
248
249 const TreeGuideNode & top () const
250 {
251 if (_parent == NULL)
252 return *this;
253 else
254 return _parent->top();
255 }
256
257 inline const TreeGuideNode * parent () const { return _parent; }
258 inline bool hasParent () const { return _parent != NULL; }
259
260 inline void addChild (const ptr< Derived > & child) { _kids.push_back(child); }
261
262 inline const typename KidList::const_iterator kidsBegin () const { return _kids.begin(); }
263 inline const typename KidList::const_iterator kidsEnd () const { return _kids.end(); }
264 inline const typename KidList::iterator kidsBegin () { return _kids.begin(); }
265 inline const typename KidList::iterator kidsEnd () { return _kids.end(); }
266 inline size_t kidsCount () const { return _kids.size(); }
267
268 void offsetBy (const V & p)
269 {
270 BasicGuide<V, T>::offsetBy(p);
271
272 for (typename KidList::iterator i = _kids.begin(); i != _kids.end(); ++i)
273 (*i)->offsetBy(p);
274 }
275 };
276
277}
Note: See TracBrowser for help on using the repository browser.