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
18using WFMath::CoordType;
19
20namespace Mercator
21{
22
23typedef WFMath::Point<2> Point2;
24typedef WFMath::Vector<2> Vector2;
25
26#ifndef NDEBUG
27static bool isZero(CoordType d)
28{
29 return (std::fabs(d) < WFMath::numeric_constants<CoordType>::epsilon());
30}
31#endif
32
34struct 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
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
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
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?
182template <class Clip>
183WFMath::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
224Area::Area(int layer, bool hole) :
225 m_layer(layer),
226 m_hole(hole)
227{
228}
229
230void Area::setShape(const WFMath::Polygon<2>& p)
231{
232 assert(p.isValid());
233 m_shape = p;
234 m_box = p.boundingBox();
235}
236
237bool 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
244WFMath::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
259bool 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 contains(WFMath::CoordType x, WFMath::CoordType z) const
Determine if a point is contained by the shape of this area.
Definition: Area.cpp:237
Area(int layer, bool hole)
Constructor.
Definition: Area.cpp:224
WFMath::Polygon< 2 > clipToSegment(const Segment &s) const
Clip the shape of this area to a given segment.
Definition: Area.cpp:244
bool checkIntersects(const Segment &s) const override
Definition: Area.cpp:259
void setShape(const WFMath::Polygon< 2 > &p)
Set the geometric shape of this area.
Definition: Area.cpp:230
WFMath::AxisBox< 2 > m_box
The bounding box of the geometric shape.
Definition: Effector.h:57
Class storing heightfield and other data for a single fixed size square area of terrain defined by fo...
Definition: Segment.h:37
WFMath::AxisBox< 2 > getRect() const
The 2d area covered by this segment.
Definition: Segment.cpp:337
Helper to clip points to a given range.
Definition: Area.cpp:74
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:84
BottomClip(CoordType t)
Definition: Area.cpp:78
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:94
CoordType bottomZ
Bottom of z range.
Definition: Area.cpp:104
Helper to clip points to a given range.
Definition: Area.cpp:109
CoordType leftX
Left of x range.
Definition: Area.cpp:141
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:129
LeftClip(CoordType t)
Definition: Area.cpp:113
Helper to clip points to a given range.
Definition: Area.cpp:146
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:166
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:156
RightClip(CoordType t)
Definition: Area.cpp:150
CoordType rightX
Right of x range.
Definition: Area.cpp:178
Helper to clip points to a given range.
Definition: Area.cpp:35
Point2 clip(const Point2 &u, const Point2 &v) const
Determine the point where a line crosses this clip.
Definition: Area.cpp:55
CoordType topZ
Top of z range.
Definition: Area.cpp:69
TopClip(CoordType t)
Definition: Area.cpp:39
bool inside(const Point2 &p) const
Check a point is outside this clip.
Definition: Area.cpp:45