forked from libgeos/geos
-
Notifications
You must be signed in to change notification settings - Fork 0
/
VoronoiTest.cpp
255 lines (215 loc) · 17.2 KB
/
VoronoiTest.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
//
// Test Suite for geos::triangulate::Voronoi
//
// tut
#include <tut/tut.hpp>
// geos
#include <geos/triangulate/quadedge/QuadEdge.h>
#include <geos/triangulate/quadedge/QuadEdgeSubdivision.h>
#include <geos/triangulate/IncrementalDelaunayTriangulator.h>
#include <geos/triangulate/VoronoiDiagramBuilder.h>
#include <geos/io/WKTWriter.h>
#include <geos/io/WKTReader.h>
#include <geos/io/WKBReader.h>
#include <geos/geom/GeometryCollection.h>
#include <geos/geom/GeometryFactory.h>
#include <geos/geom/CoordinateArraySequence.h>
//#include <stdio.h>
#include <iostream>
using namespace geos::triangulate;
using namespace geos::triangulate::quadedge;
using namespace geos::geom;
using namespace geos::io;
namespace tut {
//
// Test Group
//
// dummy data, not used
struct test_voronoidiag_data {
test_voronoidiag_data()
{
}
};
typedef test_group<test_voronoidiag_data> group;
typedef group::object object;
group test_voronoidiag_group("geos::triangulate::Voronoi");
std::unique_ptr<Geometry>
readTextOrHex(const char* wkt)
{
WKTReader wktreader;
WKBReader wkbreader;
std::string wktstr(wkt);
if ("01" == wktstr.substr(0, 2) || "00" == wktstr.substr(0, 2))
{
std::stringstream is(wkt);
return wkbreader.readHEX(is);
}
else
return wktreader.read(wktstr);
}
//helper function for running triangulation
void
runVoronoi(const char* sitesWkt, const char* expectedWkt, const double tolerance, const bool onlyEdges = false)
{
WKTWriter writer;
geos::triangulate::VoronoiDiagramBuilder builder;
std::unique_ptr<Geometry> sites(readTextOrHex(sitesWkt));
std::unique_ptr<Geometry> expected(readTextOrHex(expectedWkt));
std::unique_ptr<Geometry> results;
const GeometryFactory& geomFact(*GeometryFactory::getDefaultInstance());
builder.setSites(*sites);
//set Tolerance:
builder.setTolerance(tolerance);
if (onlyEdges) {
results = builder.getDiagramEdges(geomFact);
} else {
results = builder.getDiagram(geomFact);
}
results->normalize();
expected->normalize();
ensure_equals(results->getCoordinateDimension(), expected->getCoordinateDimension());
bool eq = results->equalsExact(expected.get(), 1e-7);
if(! eq) {
writer.setTrim(true);
std::cout << std::endl;
std::cout << " Expected: " << writer.write(expected.get()) << std::endl;
std::cout << " Obtained: " << writer.write(results.get()) << std::endl;
}
ensure(eq);
}
// Test Cases
// Basic Tests.
template<>
template<>
void object::test<1>
()
{
using geos::geom::CoordinateSequence;
Coordinate a(180, 300);
Coordinate b(300, 290);
Coordinate c(230, 330);
Coordinate d(244, 284);
geos::triangulate::VoronoiDiagramBuilder builder;
std::unique_ptr< std::vector<Coordinate> > v(new std::vector<Coordinate>());
v->push_back(a);
v->push_back(b);
v->push_back(c);
v->push_back(d);
geos::geom::CoordinateArraySequence seq(v.release());
builder.setSites(seq);
//getting the subdiv()
std::unique_ptr<QuadEdgeSubdivision> subdiv = builder.getSubdivision();
ensure_equals(subdiv->getTolerance(), 0);
//-- disable this test, since it depends on Subdiv frame size and so is brittle
//ensure_equals(subdiv->getEnvelope().toString(), "Env[-3540:4020,-3436:4050]");
}
// 1 - Case with a single point
template<>
template<>
void object::test<2>
()
{
const char* wkt = "MULTIPOINT ((150 200))";
const char* expected = "GEOMETRYCOLLECTION EMPTY";
runVoronoi(wkt, expected, 0);
}
template<>
template<>
void object::test<3>
()
{
const char* wkt = "MULTIPOINT ((150 200), (180 270), (275 163))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((25 38, 25 295, 221.20588235294116 210.91176470588235, 170.024 38, 25 38)), POLYGON ((400 369.6542056074766, 400 38, 170.024 38, 221.20588235294116 210.91176470588235, 400 369.6542056074766)), POLYGON ((25 295, 25 395, 400 395, 400 369.6542056074766, 221.20588235294116 210.91176470588235, 25 295)))";
runVoronoi(wkt, expected, 0);
}
template<>
template<>
void object::test<4>
()
{
const char* wkt = "MULTIPOINT ((280 300), (420 330), (380 230), (320 160))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((110 175.71428571428572, 110 500, 310.35714285714283 500, 353.515625 298.59375, 306.875 231.96428571428572, 110 175.71428571428572)), POLYGON ((590 204, 590 -10, 589.1666666666666 -10, 306.875 231.96428571428572, 353.515625 298.59375, 590 204)), POLYGON ((110 -10, 110 175.71428571428572, 306.875 231.96428571428572, 589.1666666666666 -10, 110 -10)), POLYGON ((310.35714285714283 500, 590 500, 590 204, 353.515625 298.59375, 310.35714285714283 500)))";
runVoronoi(wkt, expected, 0);
}
template<>
template<>
void object::test<5>
()
{
const char* wkt = "MULTIPOINT ((320 170), (366 246), (530 230), (530 300), (455 277), (490 160))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((110 -50, 110 349.02631578947364, 405.31091180866963 170.28550074738416, 392.35294117647055 -50, 110 -50)), POLYGON ((740 63.57142857142859, 740 -50, 392.35294117647055 -50, 405.31091180866963 170.28550074738416, 429.9147677857019 205.76082797008175, 470.12061711079946 217.7882187938289, 740 63.57142857142859)), POLYGON ((110 349.02631578947364, 110 510, 323.9438202247191 510, 429.9147677857019 205.76082797008175, 405.31091180866963 170.28550074738416, 110 349.02631578947364)), POLYGON ((323.9438202247191 510, 424.57333333333327 510, 499.70666666666665 265, 470.12061711079946 217.7882187938289, 429.9147677857019 205.76082797008175, 323.9438202247191 510)),POLYGON ((740 265, 740 63.57142857142859, 470.12061711079946 217.7882187938289, 499.70666666666665 265, 740 265)), POLYGON ((424.57333333333327 510, 740 510, 740 265, 499.70666666666665 265, 424.57333333333327 510)))";
runVoronoi(wkt, expected, 0);
}
//6. A little larger number of points
template<>
template<>
void object::test<6>
()
{
const char* wkt =
"MULTIPOINT ((280 200), (406 285), (580 280), (550 190), (370 190), (360 90), (480 110), (440 160), (450 180), (480 180), (460 160), (360 210), (360 220), (370 210), (375 227))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((-20 -102.27272727272727, -20 585, 111.9484126984127 585, 293.54906542056074 315.803738317757, 318.75 215, 323.2352941176471 179.11764705882354, 319.3956043956044 144.56043956043956, -20 -102.27272727272727)), POLYGON ((365 200, 365 215, 369.40909090909093 219.4090909090909, 414.2119205298013 206.2317880794702, 411.875 200, 365 200)), POLYGON ((365 215, 365 200, 323.2352941176471 179.11764705882354, 318.75 215, 365 215)), POLYGON ((-20 -210, -20 -102.27272727272727, 319.3956043956044 144.56043956043956, 388.972602739726 137.60273972602738, 419.55882352941177 102.64705882352942, 471.66666666666674 -210, -20 -210)), POLYGON ((319.3956043956044 144.56043956043956, 323.2352941176471 179.11764705882354, 365 200, 411.875 200, 410.29411764705884 187.35294117647058, 388.972602739726 137.60273972602738, 319.3956043956044 144.56043956043956)), POLYGON ((410.29411764705884 187.35294117647058, 411.875 200, 414.2119205298013 206.2317880794702, 431.62536593766146 234.01920096435336, 465 248.0047619047619, 465 175, 450 167.5, 410.29411764705884 187.35294117647058)), POLYGON ((365 215, 318.75 215, 293.54906542056074 315.803738317757, 339.6500765696784 283.1784073506891, 369.40909090909093 219.4090909090909, 365 215)), POLYGON ((111.9484126984127 585, 501.69252873563215 585, 492.5670391061452 267.4329608938547, 465 248.0047619047619, 431.62536593766146 234.01920096435336, 339.6500765696784 283.1784073506891, 293.54906542056074 315.803738317757, 111.9484126984127 585)), POLYGON ((369.40909090909093 219.4090909090909, 339.6500765696784 283.1784073506891, 431.62536593766146 234.01920096435336, 414.2119205298013 206.2317880794702, 369.40909090909093 219.4090909090909)), POLYGON ((388.972602739726 137.60273972602738, 410.29411764705884 187.35294117647058, 450 167.5, 450 127, 419.55882352941177 102.64705882352942, 388.972602739726 137.60273972602738)), POLYGON ((465 175, 465 248.0047619047619, 492.5670391061452 267.4329608938547, 505 255, 520.7142857142857 145, 495 145, 465 175)),POLYGON ((880 -169.375, 880 -210, 471.66666666666674 -210, 419.55882352941177 102.64705882352942, 450 127, 495 145, 520.7142857142857 145, 880 -169.375)), POLYGON ((450 167.5, 465 175, 495 145, 450 127, 450 167.5)), POLYGON ((501.69252873563215 585, 880 585, 880 130.00000000000006, 505 255, 492.5670391061452 267.4329608938547, 501.69252873563215 585)), POLYGON ((880 130.00000000000006, 880 -169.375, 520.7142857142857 145, 505 255, 880 130.00000000000006)))";
runVoronoi(wkt, expected, 0);
}
//Test with case of Tolerance:
template<>
template<>
void object::test<7>
()
{
const char* wkt =
"MULTIPOINT ((100 200), (105 202), (110 200), (140 230), (210 240), (220 190), (170 170), (170 260), (213 245), (220 190))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((-20 50, -20 380, -3.75 380, 105 235, 105 115, 77.14285714285714 50, -20 50)), POLYGON ((247 50, 77.14285714285714 50, 105 115, 145 195, 178.33333333333334 211.66666666666666, 183.51851851851853 208.7037037037037, 247 50)), POLYGON ((-3.75 380, 20.000000000000007 380, 176.66666666666666 223.33333333333334, 178.33333333333334 211.66666666666666, 145 195, 105 235, -3.75 380)), POLYGON ((105 115, 105 235, 145 195, 105 115)), POLYGON ((20.000000000000007 380, 255 380, 176.66666666666666 223.33333333333334, 20.000000000000007 380)), POLYGON ((255 380, 340 380, 340 240, 183.51851851851853 208.7037037037037, 178.33333333333334 211.66666666666666, 176.66666666666666 223.33333333333334, 255 380)), POLYGON ((340 240, 340 50, 247 50, 183.51851851851853 208.7037037037037, 340 240)))";
runVoronoi(wkt, expected, 6);
}
template<>
template<>
void object::test<8>
()
{
const char* wkt = "MULTIPOINT ((170 270), (177 275), (190 230), (230 250), (210 290), (240 280), (240 250))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((100 210, 100 360, 150 360, 200 260, 100 210)), POLYGON ((150 360, 250 360, 220 270, 200 260, 150 360)), POLYGON ((100 160, 100 210, 200 260, 235 190, 247 160, 100 160)), POLYGON ((220 270, 235 265, 235 190, 200 260, 220 270)), POLYGON ((250 360, 310 360, 310 265, 235 265, 220 270, 250 360)), POLYGON ((310 265, 310 160, 247 160, 235 190, 235 265, 310 265)))";
runVoronoi(wkt, expected, 10);
}
//Taking tolerance very very high
template<>
template<>
void object::test<9>
()
{
const char* wkt = "MULTIPOINT ((155 271), (150 360), (260 360), (271 265), (280 260), (270 370), (154 354), (150 260))";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((20 130, 20 310, 205 310, 215 299, 215 130, 20 130)), POLYGON ((205 500, 410 500, 410 338, 215 299, 205 310, 205 500)), POLYGON ((20 310, 20 500, 205 500, 205 310, 20 310)), POLYGON ((410 338, 410 130, 215 130, 215 299, 410 338)))";
runVoronoi(wkt, expected, 100);
}
//Validity issue and DD calculation
template<>
template<>
void object::test<10>
()
{
const char* wkt = "0104000080170000000101000080EC51B81E11A20741EC51B81E85A51C415C8FC2F528DC354001010000801F85EB5114A207415C8FC2F585A51C417B14AE47E1BA3540010100008085EB51B818A20741A8C64B3786A51C413E0AD7A3709D35400101000080000000001BA20741FED478E984A51C413E0AD7A3709D3540010100008085EB51B818A20741FED478E984A51C413E0AD7A3709D354001010000800AD7A37016A20741FED478E984A51C413E0AD7A3709D35400101000080000000001BA2074154E3A59B83A51C413E0AD7A3709D3540010100008085EB51B818A2074154E3A59B83A51C413E0AD7A3709D354001010000800AD7A37016A2074154E3A59B83A51C413E0AD7A3709D35400101000080000000001BA20741AAF1D24D82A51C413E0AD7A3709D3540010100008085EB51B818A20741AAF1D24D82A51C413E0AD7A3709D35400101000080F6285C8F12A20741EC51B81E88A51C414160E5D022DB354001010000802222222210A2074152B81EC586A51C414160E5D022DB354001010000804F1BE8B40DA2074152B81EC586A51C414160E5D022DB354001010000807B14AE470BA2074152B81EC586A51C414160E5D022DB354001010000802222222210A20741B81E856B85A51C414160E5D022DB354001010000804F1BE8B40DA20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA20741B81E856B85A51C414160E5D022DB35400101000080A70D74DA08A20741B81E856B85A51C414160E5D022DB35400101000080D4063A6D06A20741B81E856B85A51C414160E5D022DB354001010000807B14AE470BA207411F85EB1184A51C414160E5D022DB35400101000080A70D74DA08A207411F85EB1184A51C414160E5D022DB35400101000080D4063A6D06A207411F85EB1184A51C414160E5D022DB3540";
const char* expected =
"GEOMETRYCOLLECTION (POLYGON ((193602.7711332133 469345.898980198, 193604.4418848486 469348.6016666667, 193605.9466666667 469348.6016666667, 193605.9466666667 469347.7638144172, 193603.2325 469345.391, 193602.9475 469345.391, 193602.8169643859 469345.5051185583, 193602.7711332133 469345.898980198)), POLYGON ((193601.8569454336 469344.9208636514, 193601.865 469344.9666851849, 193602.2037556305 469345.52375, 193602.2585544897 469345.5401343054, 193602.4642389841 469345.148354316, 193602.4577210526 469345.065, 193602.0579897448 469344.3617689955, 193601.8569454336 469344.9208636514)), POLYGON ((193601.2583333333 469342.0043333333, 193601.2583333333 469345.18625, 193601.5616666667 469345.18625, 193601.8569454336 469344.9208636514, 193602.0579897448 469344.3617689955, 193602.0222507725 469343.9301164729, 193601.5161595486 469342.0043333333, 193601.2583333333 469342.0043333333)), POLYGON ((193600.8486366758 469348.6016666667, 193604.4418848486 469348.6016666667, 193602.7711332133 469345.898980198, 193602.3274661311 469345.7182269423, 193601.865 469346.1338755144, 193601.5616666667 469346.6791265432, 193600.8486366758 469348.6016666667)), POLYGON ((193599.3943641253 469348.6016666667, 193600.8486366758 469348.6016666667, 193601.5616666667 469346.6791265432, 193601.5616666667 469345.52375, 193601.2583333333 469345.52375, 193600.955 469345.7963755144, 193599.3943641253 469348.6016666667)), POLYGON ((193602.4577210526 469345.065, 193602.4642389841 469345.148354316, 193602.8169643859 469345.5051185583, 193602.9475 469345.391, 193602.9475 469345.065, 193602.4577210526 469345.065)), POLYGON ((193602.2585544897 469345.5401343054, 193602.3274661311 469345.7182269423, 193602.7711332133 469345.898980198, 193602.8169643859 469345.5051185583, 193602.4642389841 469345.148354316, 193602.2585544897 469345.5401343054)), POLYGON ((193602.0222507725 469343.9301164729, 193602.0579897448 469344.3617689955, 193602.4577210526 469345.065, 193602.9475 469345.065, 193602.9475 469344.739, 193602.0222507725 469343.9301164729)), POLYGON ((193601.865 469345.52375, 193601.865 469346.1338755144, 193602.3274661311 469345.7182269423, 193602.2585544897 469345.5401343054, 193602.2037556305 469345.52375, 193601.865 469345.52375)), POLYGON ((193601.5616666667 469345.18625, 193601.5616666667 469345.52375, 193601.865 469345.52375, 193601.865 469344.9666851849, 193601.8569454336 469344.9208636514, 193601.5616666667 469345.18625)), POLYGON ((193601.5161595486 469342.0043333333, 193602.0222507725 469343.9301164729, 193602.9475 469344.739, 193603.2325 469344.739, 193603.2325 469342.0043333333, 193601.5161595486 469342.0043333333)), POLYGON ((193598.2316666667 469345.18625, 193598.2316666667 469348.6016666667, 193599.3943641253 469348.6016666667, 193600.955 469345.7963755144, 193600.955 469345.18625, 193598.2316666667 469345.18625)), POLYGON ((193603.2325 469345.065, 193603.2325 469345.391, 193605.9466666667 469347.7638144172, 193605.9466666667 469345.065, 193603.2325 469345.065)), POLYGON ((193603.2325 469344.739, 193603.2325 469345.065, 193605.9466666667 469345.065, 193605.9466666667 469344.739, 193603.2325 469344.739)), POLYGON ((193603.2325 469342.0043333333, 193603.2325 469344.739, 193605.9466666667 469344.739, 193605.9466666667 469342.0043333333, 193603.2325 469342.0043333333)), POLYGON ((193602.9475 469345.065, 193602.9475 469345.391, 193603.2325 469345.391, 193603.2325 469345.065, 193602.9475 469345.065)), POLYGON ((193602.9475 469344.739, 193602.9475 469345.065, 193603.2325 469345.065, 193603.2325 469344.739, 193602.9475 469344.739)), POLYGON ((193601.5616666667 469345.52375, 193601.5616666667 469346.6791265432, 193601.865 469346.1338755144, 193601.865 469345.52375, 193601.5616666667 469345.52375)), POLYGON ((193601.2583333333 469345.18625, 193601.2583333333 469345.52375, 193601.5616666667 469345.52375, 193601.5616666667 469345.18625, 193601.2583333333 469345.18625)), POLYGON ((193600.955 469345.18625, 193600.955 469345.7963755144, 193601.2583333333 469345.52375, 193601.2583333333 469345.18625, 193600.955 469345.18625)), POLYGON ((193600.955 469342.0043333333, 193600.955 469345.18625, 193601.2583333333 469345.18625, 193601.2583333333 469342.0043333333, 193600.955 469342.0043333333)), POLYGON ((193598.2316666667 469342.0043333333, 193598.2316666667 469345.18625, 193600.955 469345.18625, 193600.955 469342.0043333333, 193598.2316666667 469342.0043333333)), POLYGON ((193601.865 469344.9666851849, 193601.865 469345.52375, 193602.2037556305 469345.52375, 193601.865 469344.9666851849)))";
runVoronoi(wkt, expected, 0);
}
// Consistency in the return value for edges
template<>
template<>
void object::test<11>
()
{
const char* wkt1 = "LINESTRING (10 10, 20 20)";
const char* expected1 = "MULTILINESTRING ((0 30, 30 0))";
const char* wkt2 = "LINESTRING (10 10, 20 20, 30 30)";
const char* expected2 = "MULTILINESTRING ((0 50, 50 0), (-10 40, 40 -10))";
runVoronoi(wkt1, expected1, 0, true);
runVoronoi(wkt2, expected2, 0, true);
}
} // namespace tut