1 /**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2009 Sandro Santilli <strk@kbt.io>
7 *
8 * This is free software; you can redistribute and/or modify it under
9 * the terms of the GNU Lesser General Public Licence as published
10 * by the Free Software Foundation.
11 * See the COPYING file for more information.
12 *
13 **********************************************************************
14 *
15 * Last port: operation/buffer/BufferInputLineSimplifier.java r320 (JTS-1.12)
16 *
17 **********************************************************************/
18
19 #include <geos/operation/buffer/BufferInputLineSimplifier.h>
20 #include <geos/geom/CoordinateSequence.h> // for inlines
21 #include <geos/geom/CoordinateArraySequence.h> // for constructing the return
22 #include <geos/algorithm/Distance.h> // for use
23 #include <geos/algorithm/Orientation.h> // for use
24 #include <geos/util.h>
25
26 #include <memory>
27 #include <cmath>
28 #include <vector>
29
30 //#include <cassert>
31
32 using namespace geos::algorithm; // Orientation
33 using namespace geos::geom;
34 //using namespace geos::geomgraph; // DirectedEdge, Position
35
36 namespace geos {
37 namespace operation { // geos.operation
38 namespace buffer { // geos.operation.buffer
39
BufferInputLineSimplifier(const geom::CoordinateSequence & input)40 BufferInputLineSimplifier::BufferInputLineSimplifier(
41 const geom::CoordinateSequence& input)
42 :
43 inputLine(input),
44 angleOrientation(Orientation::COUNTERCLOCKWISE)
45 {}
46
47 /*public static*/
48 std::unique_ptr<geom::CoordinateSequence>
simplify(const geom::CoordinateSequence & inputLine,double distanceTol)49 BufferInputLineSimplifier::simplify(const geom::CoordinateSequence& inputLine,
50 double distanceTol)
51 {
52 BufferInputLineSimplifier simp(inputLine);
53 return simp.simplify(distanceTol);
54 }
55
56 /* public */
57 std::unique_ptr<geom::CoordinateSequence>
simplify(double nDistanceTol)58 BufferInputLineSimplifier::simplify(double nDistanceTol)
59 {
60 distanceTol = fabs(nDistanceTol);
61 if(nDistanceTol < 0) {
62 angleOrientation = Orientation::CLOCKWISE;
63 }
64
65 // rely on fact that boolean array is filled with false value
66 static const int startValue = INIT;
67 isDeleted.assign(inputLine.size(), startValue);
68
69 bool isChanged = false;
70 do {
71 isChanged = deleteShallowConcavities();
72 }
73 while(isChanged);
74
75 return collapseLine();
76 }
77
78 /* private */
79 bool
deleteShallowConcavities()80 BufferInputLineSimplifier::deleteShallowConcavities()
81 {
82 /*
83 * Do not simplify end line segments of the line string.
84 * This ensures that end caps are generated consistently.
85 */
86 size_t index = 1;
87
88 auto midIndex = findNextNonDeletedIndex(index);
89 auto lastIndex = findNextNonDeletedIndex(midIndex);
90
91 bool isChanged = false;
92 while(lastIndex < inputLine.size()) {
93 // test triple for shallow concavity
94 bool isMiddleVertexDeleted = false;
95 if(isDeletable(index, midIndex, lastIndex,
96 distanceTol)) {
97 isDeleted[midIndex] = DELETE;
98 isMiddleVertexDeleted = true;
99 isChanged = true;
100 }
101 // move simplification window forward
102 if(isMiddleVertexDeleted) {
103 index = lastIndex;
104 }
105 else {
106 index = midIndex;
107 }
108
109 midIndex = findNextNonDeletedIndex(index);
110 lastIndex = findNextNonDeletedIndex(midIndex);
111 }
112 return isChanged;
113 }
114
115 /* private */
116 size_t
findNextNonDeletedIndex(size_t index) const117 BufferInputLineSimplifier::findNextNonDeletedIndex(size_t index) const
118 {
119 std::size_t next = index + 1;
120 const std::size_t len = inputLine.size();
121 while(next < len && isDeleted[next] == DELETE) {
122 next++;
123 }
124 return next;
125 }
126
127 /* private */
128 std::unique_ptr<geom::CoordinateSequence>
collapseLine() const129 BufferInputLineSimplifier::collapseLine() const
130 {
131 auto coordList = new CoordinateArraySequence();
132
133 for(size_t i = 0, n = inputLine.size(); i < n; ++i) {
134 if(isDeleted[i] != DELETE) {
135 coordList->add(inputLine[i], false);
136 }
137 }
138
139 return std::unique_ptr<CoordinateSequence>(coordList);
140 }
141
142 /* private */
143 bool
isDeletable(size_t i0,size_t i1,size_t i2,double p_distanceTol) const144 BufferInputLineSimplifier::isDeletable(size_t i0, size_t i1, size_t i2,
145 double p_distanceTol) const
146 {
147 const Coordinate& p0 = inputLine[i0];
148 const Coordinate& p1 = inputLine[i1];
149 const Coordinate& p2 = inputLine[i2];
150
151 if(! isConcave(p0, p1, p2)) {
152 return false;
153 }
154 if(! isShallow(p0, p1, p2, p_distanceTol)) {
155 return false;
156 }
157
158 // MD - don't use this heuristic - it's too restricting
159 // if (p0.distance(p2) > distanceTol) return false;
160
161 return isShallowSampled(p0, p1, i0, i2, p_distanceTol);
162 }
163
164 /* private */
165 bool
isShallowConcavity(const geom::Coordinate & p0,const geom::Coordinate & p1,const geom::Coordinate & p2,double p_distanceTol) const166 BufferInputLineSimplifier::isShallowConcavity(const geom::Coordinate& p0,
167 const geom::Coordinate& p1,
168 const geom::Coordinate& p2,
169 double p_distanceTol) const
170 {
171 int orientation = Orientation::index(p0, p1, p2);
172 bool isAngleToSimplify = (orientation == angleOrientation);
173 if(! isAngleToSimplify) {
174 return false;
175 }
176
177 double dist = Distance::pointToSegment(p1, p0, p2);
178 return dist < p_distanceTol;
179 }
180
181 /* private */
182 bool
isShallowSampled(const geom::Coordinate & p0,const geom::Coordinate & p2,size_t i0,size_t i2,double p_distanceTol) const183 BufferInputLineSimplifier::isShallowSampled(const geom::Coordinate& p0,
184 const geom::Coordinate& p2,
185 size_t i0, size_t i2,
186 double p_distanceTol) const
187 {
188 // check every n'th point to see if it is within tolerance
189 auto inc = (i2 - i0) / NUM_PTS_TO_CHECK;
190 if(inc <= 0) {
191 inc = 1;
192 }
193
194 for(size_t i = i0; i < i2; i += inc) {
195 if(! isShallow(p0, p2, inputLine[i], p_distanceTol)) {
196 return false;
197 }
198 }
199 return true;
200 }
201
202 /* private */
203 bool
isShallow(const geom::Coordinate & p0,const geom::Coordinate & p1,const geom::Coordinate & p2,double p_distanceTol) const204 BufferInputLineSimplifier::isShallow(const geom::Coordinate& p0,
205 const geom::Coordinate& p1,
206 const geom::Coordinate& p2,
207 double p_distanceTol) const
208 {
209 double dist = Distance::pointToSegment(p1, p0, p2);
210 return dist < p_distanceTol;
211 }
212
213 /* private */
214 bool
isConcave(const geom::Coordinate & p0,const geom::Coordinate & p1,const geom::Coordinate & p2) const215 BufferInputLineSimplifier::isConcave(const geom::Coordinate& p0,
216 const geom::Coordinate& p1,
217 const geom::Coordinate& p2) const
218 {
219 int orientation = Orientation::index(p0, p1, p2);
220 bool p_isConcave = (orientation == angleOrientation);
221 return p_isConcave;
222 }
223
224 } // namespace geos.operation.buffer
225 } // namespace geos.operation
226 } // namespace geos
227
228