mercator  0.4.0
A terrain generation library for the Worldforge system.
Area.cpp
1 // This file may be redistributed and modified only under the terms of
2 // the GNU General Public License (See COPYING for details).
3 // Copyright (C) 2005 Alistair Riddoch
4 
5 #ifdef HAVE_CONFIG_H
6 #include "config.h"
7 #endif
8 
9 #include "Area.h"
10 #include "Segment.h"
11 
12 #include <wfmath/intersect.h>
13 #include <iostream>
14 #include <cmath>
15 
16 #include <cassert>
17 
18 using WFMath::CoordType;
19 
20 namespace Mercator
21 {
22 
23 typedef WFMath::Point<2> Point2;
24 typedef WFMath::Vector<2> Vector2;
25 
26 #ifndef NDEBUG
27 static bool isZero(CoordType d)
28 {
29  return (std::fabs(d) < WFMath::numeric_constants<CoordType>::epsilon());
30 }
31 #endif
32 
34 struct TopClip
35 {
39  explicit TopClip(CoordType t) : topZ(t) { }
40 
45  bool inside(const Point2& p) const
46  {
47  return p.y() >= topZ;
48  }
49 
55  Point2 clip(const Point2& u, const Point2& v) const
56  {
57  CoordType dy = v.y() - u.y();
58  CoordType dx = v.x() - u.x();
59 
60  // shouldn't every happen - if dy iz zero, the line is horizontal,
61  // so either both points should be inside, or both points should be
62  // outside. In either case, we should not call clip()
63  assert(!isZero(dy));
64 
65  CoordType t = (topZ - u.y()) / dy;
66  return Point2(u.x() + t * dx, topZ);
67  }
69  CoordType topZ;
70 };
71 
73 struct BottomClip
74 {
78  explicit BottomClip(CoordType t) : bottomZ(t) { }
79 
84  bool inside(const Point2& p) const
85  {
86  return p.y() < bottomZ;
87  }
88 
94  Point2 clip(const Point2& u, const Point2& v) const
95  {
96  CoordType dy = v.y() - u.y();
97  CoordType dx = v.x() - u.x();
98  assert(!isZero(dy));
99 
100  CoordType t = (u.y() - bottomZ) / -dy;
101  return Point2(u.x() + t * dx, bottomZ);
102  }
104  CoordType bottomZ;
105 };
106 
108 struct LeftClip
109 {
113  explicit LeftClip(CoordType t) : leftX(t) { }
114 
119  bool inside(const Point2& p) const
120  {
121  return p.x() >= leftX;
122  }
123 
129  Point2 clip(const Point2& u, const Point2& v) const
130  {
131  CoordType dy = v.y() - u.y();
132  CoordType dx = v.x() - u.x();
133 
134  // shouldn't every happen
135  assert(!isZero(dx));
136 
137  CoordType t = (leftX - u.x()) / dx;
138  return Point2(leftX, u.y() + t * dy);
139  }
141  CoordType leftX;
142 };
143 
145 struct RightClip
146 {
150  explicit RightClip(CoordType t) : rightX(t) { }
151 
156  bool inside(const Point2& p) const
157  {
158  return p.x() < rightX;
159  }
160 
166  Point2 clip(const Point2& u, const Point2& v) const
167  {
168  CoordType dy = v.y() - u.y();
169  CoordType dx = v.x() - u.x();
170 
171  // shouldn't every happen
172  assert(!isZero(dx));
173 
174  CoordType t = (u.x() - rightX) / -dx;
175  return Point2(rightX, u.y() + t * dy);
176  }
178  CoordType rightX;
179 };
180 
181 // FIXME Why pass Clip by value?
182 template <class Clip>
183 WFMath::Polygon<2> sutherlandHodgmanKernel(const WFMath::Polygon<2>& inpoly, const Clip& clipper)
184 {
185  WFMath::Polygon<2> outpoly;
186 
187  if (!inpoly.isValid()) return inpoly;
188  std::size_t points = inpoly.numCorners();
189  if (points < 3) return outpoly; // i.e an invalid result
190 
191  Point2 lastPt = inpoly.getCorner(points - 1);
192  bool lastInside = clipper.inside(lastPt);
193 
194  for (std::size_t p = 0; p < points; ++p) {
195 
196  Point2 curPt = inpoly.getCorner(p);
197  bool inside = clipper.inside(curPt);
198 
199  if (lastInside) {
200  if (inside) {
201  // emit curPt
202  outpoly.addCorner(outpoly.numCorners(), curPt);
203  } else {
204  // emit intersection of edge with clip line
205  outpoly.addCorner(outpoly.numCorners(), clipper.clip(lastPt, curPt));
206  }
207  } else {
208  if (inside) {
209  // emit both
210  outpoly.addCorner(outpoly.numCorners(), clipper.clip(lastPt, curPt));
211  outpoly.addCorner(outpoly.numCorners(), curPt);
212  } else {
213  // don't emit anything
214  }
215  } // last was outside
216 
217  lastPt = curPt;
218  lastInside = inside;
219  }
220 
221  return outpoly;
222 }
223 
224 Area::Area(int layer, bool hole) :
225  m_layer(layer),
226  m_hole(hole)
227 {
228 }
229 
230 void Area::setShape(const WFMath::Polygon<2>& p)
231 {
232  assert(p.isValid());
233  m_shape = p;
234  m_box = p.boundingBox();
235 }
236 
237 bool Area::contains(CoordType x, CoordType z) const
238 {
239  if (!WFMath::Contains(m_box, Point2(x,z), false)) return false;
240 
241  return WFMath::Contains(m_shape, Point2(x,z), false);
242 }
243 
244 WFMath::Polygon<2> Area::clipToSegment(const Segment& s) const
245 {
246  // box reject
247  if (!checkIntersects(s)) return WFMath::Polygon<2>();
248 
249  WFMath::AxisBox<2> segBox(s.getRect());
250  WFMath::Polygon<2> clipped = sutherlandHodgmanKernel(m_shape, TopClip(segBox.lowCorner().y()));
251 
252  clipped = sutherlandHodgmanKernel(clipped, BottomClip(segBox.highCorner().y()));
253  clipped = sutherlandHodgmanKernel(clipped, LeftClip(segBox.lowCorner().x()));
254  clipped = sutherlandHodgmanKernel(clipped, RightClip(segBox.highCorner().x()));
255 
256  return clipped;
257 }
258 
259 bool Area::checkIntersects(const Segment& s) const
260 {
261  return m_shape.numCorners() && (WFMath::Intersect(m_shape, s.getRect(), false) ||
262  WFMath::Contains(s.getRect(), m_shape.getCorner(0), false));
263 }
264 
265 } // of namespace
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:45
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:84
WFMath::Polygon< 2 > clipToSegment(const Segment &s) const
Clip the shape of this area to a given segment.
Definition: Area.cpp:244
Helper to clip points to a given range.
Definition: Area.cpp:145
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:156
TopClip(CoordType t)
Definition: Area.cpp:39
WFMath::AxisBox< 2 > getRect() const
The 2d area covered by this segment.
Definition: Segment.cpp:337
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:94
Area(int layer, bool hole)
Constructor.
Definition: Area.cpp:224
RightClip(CoordType t)
Definition: Area.cpp:150
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:119
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:166
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:55
CoordType leftX
Left of x range.
Definition: Area.cpp:141
CoordType bottomZ
Bottom of z range.
Definition: Area.cpp:104
bool checkIntersects(const Segment &s) const override
Definition: Area.cpp:259
LeftClip(CoordType t)
Definition: Area.cpp:113
Class storing heightfield and other data for a single fixed size square area of terrain defined by fo...
Definition: Segment.h:37
CoordType rightX
Right of x range.
Definition: Area.cpp:178
Helper to clip points to a given range.
Definition: Area.cpp:108
WFMath::AxisBox< 2 > m_box
The bounding box of the geometric shape.
Definition: Effector.h:57
CoordType topZ
Top of z range.
Definition: Area.cpp:69
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:129
Helper to clip points to a given range.
Definition: Area.cpp:34
Helper to clip points to a given range.
Definition: Area.cpp:73
bool contains(WFMath::CoordType x, WFMath::CoordType z) const
Determine if a point is contained by the shape of this area.
Definition: Area.cpp:237
BottomClip(CoordType t)
Definition: Area.cpp:78
void setShape(const WFMath::Polygon< 2 > &p)
Set the geometric shape of this area.
Definition: Area.cpp:230