1 /**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2009-2011 Sandro Santilli <strk@kbt.io>
7 * Copyright (C) 2008-2010 Safe Software Inc.
8 * Copyright (C) 2005-2007 Refractions Research Inc.
9 * Copyright (C) 2001-2002 Vivid Solutions Inc.
10 *
11 * This is free software; you can redistribute and/or modify it under
12 * the terms of the GNU Lesser General Public Licence as published
13 * by the Free Software Foundation.
14 * See the COPYING file for more information.
15 *
16 **********************************************************************
17 *
18 * Last port: operation/buffer/BufferBuilder.java r378 (JTS-1.12)
19 *
20 **********************************************************************/
21
22 #include <geos/geom/CoordinateSequenceFactory.h>
23 #include <geos/geom/GeometryFactory.h>
24 #include <geos/geom/Location.h>
25 #include <geos/geom/Geometry.h>
26 #include <geos/geom/Polygon.h>
27 #include <geos/geom/GeometryCollection.h>
28 #include <geos/geom/LineString.h>
29 #include <geos/geom/MultiLineString.h>
30 #include <geos/operation/buffer/BufferBuilder.h>
31 #include <geos/operation/buffer/OffsetCurveBuilder.h>
32 #include <geos/operation/buffer/OffsetCurveSetBuilder.h>
33 #include <geos/operation/buffer/BufferSubgraph.h>
34 #include <geos/operation/buffer/SubgraphDepthLocater.h>
35 #include <geos/operation/overlay/OverlayOp.h>
36 #include <geos/operation/overlay/snap/SnapOverlayOp.h>
37 #include <geos/operation/overlay/PolygonBuilder.h>
38 #include <geos/operation/overlay/OverlayNodeFactory.h>
39 #include <geos/operation/valid/RepeatedPointRemover.h>
40 #include <geos/operation/linemerge/LineMerger.h>
41 #include <geos/algorithm/LineIntersector.h>
42 #include <geos/noding/IntersectionAdder.h>
43 #include <geos/noding/SegmentString.h>
44 #include <geos/noding/MCIndexNoder.h>
45 #include <geos/noding/NodedSegmentString.h>
46 #include <geos/geom/Position.h>
47 #include <geos/geomgraph/PlanarGraph.h>
48 #include <geos/geomgraph/Label.h>
49 #include <geos/geomgraph/Node.h>
50 #include <geos/geomgraph/Edge.h>
51 #include <geos/util/GEOSException.h>
52 #include <geos/io/WKTWriter.h> // for debugging
53 #include <geos/util/IllegalArgumentException.h>
54 #include <geos/profiler.h>
55 #include <geos/util/Interrupt.h>
56
57 #include <cassert>
58 #include <vector>
59 #include <iomanip>
60 #include <algorithm>
61 #include <iostream>
62
63 // Debug single sided buffer
64 //#define GEOS_DEBUG_SSB 1
65
66 #ifndef GEOS_DEBUG
67 #define GEOS_DEBUG 0
68 #endif
69
70 #ifndef JTS_DEBUG
71 #define JTS_DEBUG 0
72 #endif
73
74 //using namespace std;
75 using namespace geos::geom;
76 using namespace geos::geomgraph;
77 using namespace geos::noding;
78 using namespace geos::algorithm;
79 using namespace geos::operation::overlay;
80 using namespace geos::operation::linemerge;
81
82 namespace {
83
84 // Debug routine
85 template <class Iterator>
86 std::unique_ptr<Geometry>
convertSegStrings(const GeometryFactory * fact,Iterator it,Iterator et)87 convertSegStrings(const GeometryFactory* fact, Iterator it, Iterator et)
88 {
89 std::vector<Geometry*> lines;
90 while(it != et) {
91 const SegmentString* ss = *it;
92 LineString* line = fact->createLineString(ss->getCoordinates()->clone().release());
93 lines.push_back(line);
94 ++it;
95 }
96 return std::unique_ptr<Geometry>(fact->buildGeometry(lines.begin(), lines.end()));
97 }
98
99 }
100
101 namespace geos {
102 namespace operation { // geos.operation
103 namespace buffer { // geos.operation.buffer
104
105 #if PROFILE
106 static Profiler* profiler = Profiler::instance();
107 #endif
108
109 int
depthDelta(const Label & label)110 BufferBuilder::depthDelta(const Label& label)
111 {
112 Location lLoc = label.getLocation(0, Position::LEFT);
113 Location rLoc = label.getLocation(0, Position::RIGHT);
114 if(lLoc == Location::INTERIOR && rLoc == Location::EXTERIOR) {
115 return 1;
116 }
117 else if(lLoc == Location::EXTERIOR && rLoc == Location::INTERIOR) {
118 return -1;
119 }
120 return 0;
121 }
122
~BufferBuilder()123 BufferBuilder::~BufferBuilder()
124 {
125 delete li; // could be NULL
126 delete intersectionAdder;
127 }
128
129 /*public*/
130 Geometry*
bufferLineSingleSided(const Geometry * g,double distance,bool leftSide)131 BufferBuilder::bufferLineSingleSided(const Geometry* g, double distance,
132 bool leftSide)
133 {
134 // Returns the line used to create a single-sided buffer.
135 // Input requirement: Must be a LineString.
136 const LineString* l = dynamic_cast< const LineString* >(g);
137 if(!l) {
138 throw util::IllegalArgumentException("BufferBuilder::bufferLineSingleSided only accept linestrings");
139 }
140
141 // Nothing to do for a distance of zero
142 if(distance == 0) {
143 return g->clone().release();
144 }
145
146 // Get geometry factory and precision model.
147 const PrecisionModel* precisionModel = workingPrecisionModel;
148 if(!precisionModel) {
149 precisionModel = l->getPrecisionModel();
150 }
151
152 assert(precisionModel);
153 assert(l);
154
155 geomFact = l->getFactory();
156
157 // First, generate the two-sided buffer using a butt-cap.
158 BufferParameters modParams = bufParams;
159 modParams.setEndCapStyle(BufferParameters::CAP_FLAT);
160 modParams.setSingleSided(false); // ignore parameter for areal-only geometries
161 std::unique_ptr<Geometry> buf;
162
163 // This is a (temp?) hack to workaround the fact that
164 // BufferBuilder BufferParamaters are immutable after
165 // construction, while we want to force the end cap
166 // style to FLAT for single-sided buffering
167 {
168 BufferBuilder tmp(modParams);
169 buf.reset(tmp.buffer(l, distance));
170 }
171
172 // Create MultiLineStrings from this polygon.
173 std::unique_ptr<Geometry> bufLineString(buf->getBoundary());
174
175 #ifdef GEOS_DEBUG_SSB
176 std::cerr << "input|" << *l << std::endl;
177 std::cerr << "buffer|" << *bufLineString << std::endl;
178 #endif
179
180 // Then, get the raw (i.e. unnoded) single sided offset curve.
181 OffsetCurveBuilder curveBuilder(precisionModel, modParams);
182 std::vector< CoordinateSequence* > lineList;
183
184 {
185 std::unique_ptr< CoordinateSequence > coords(g->getCoordinates());
186 curveBuilder.getSingleSidedLineCurve(coords.get(), distance,
187 lineList, leftSide, !leftSide);
188 coords.reset();
189 }
190
191 // Create a SegmentString from these coordinates.
192 SegmentString::NonConstVect curveList;
193 for(unsigned int i = 0; i < lineList.size(); ++i) {
194 CoordinateSequence* seq = lineList[i];
195
196 // SegmentString takes ownership of CoordinateSequence
197 SegmentString* ss = new NodedSegmentString(seq, nullptr);
198 curveList.push_back(ss);
199 }
200 lineList.clear();
201
202
203 // Node these SegmentStrings.
204 Noder* noder = getNoder(precisionModel);
205 noder->computeNodes(&curveList);
206
207 SegmentString::NonConstVect* nodedEdges = noder->getNodedSubstrings();
208
209 // Create a geometry out of the noded substrings.
210 std::vector< Geometry* >* singleSidedNodedEdges =
211 new std::vector< Geometry* >();
212 singleSidedNodedEdges->reserve(nodedEdges->size());
213 for(std::size_t i = 0, n = nodedEdges->size(); i < n; ++i) {
214 SegmentString* ss = (*nodedEdges)[i];
215
216 Geometry* tmp = geomFact->createLineString(
217 ss->getCoordinates()->clone().release()
218 );
219 delete ss;
220
221 singleSidedNodedEdges->push_back(tmp);
222 }
223
224 delete nodedEdges;
225
226 for(size_t i = 0, n = curveList.size(); i < n; ++i) {
227 delete curveList[i];
228 }
229 curveList.clear();
230
231 std::unique_ptr<Geometry> singleSided(geomFact->createMultiLineString(
232 singleSidedNodedEdges));
233
234 #ifdef GEOS_DEBUG_SSB
235 std::cerr << "edges|" << *singleSided << std::endl;
236 #endif
237
238 // Use the boolean operation intersect to obtain the line segments lying
239 // on both the butt-cap buffer and this multi-line.
240 //Geometry* intersectedLines = singleSided->intersection( bufLineString );
241 // NOTE: we use Snapped overlay because the actual buffer boundary might
242 // diverge from original offset curves due to the addition of
243 // intersections with caps and joins curves
244 using geos::operation::overlay::snap::SnapOverlayOp;
245 std::unique_ptr<Geometry> intersectedLines = SnapOverlayOp::overlayOp(*singleSided, *bufLineString,
246 OverlayOp::opINTERSECTION);
247
248 #ifdef GEOS_DEBUG_SSB
249 std::cerr << "intersection" << "|" << *intersectedLines << std::endl;
250 #endif
251
252 // Merge result lines together.
253 LineMerger lineMerge;
254 lineMerge.add(intersectedLines.get());
255 auto mergedLines = lineMerge.getMergedLineStrings();
256
257 // Convert the result into a std::vector< Geometry* >.
258 std::vector< Geometry* >* mergedLinesGeom = new std::vector< Geometry* >();
259 const Coordinate& startPoint = l->getCoordinatesRO()->front();
260 const Coordinate& endPoint = l->getCoordinatesRO()->back();
261 while(!mergedLines.empty()) {
262 // Remove end points if they are a part of the original line to be
263 // buffered.
264 CoordinateSequence::Ptr coords(mergedLines.back()->getCoordinates());
265 if(nullptr != coords.get()) {
266 // Use 98% of the buffer width as the point-distance requirement - this
267 // is to ensure that the point that is "distance" +/- epsilon is not
268 // included.
269 //
270 // Let's try and estimate a more accurate bound instead of just assuming
271 // 98%. With 98%, the episilon grows as the buffer distance grows,
272 // so that at large distance, artifacts may skip through this filter
273 // Let the length of the line play a factor in the distance, which is still
274 // going to be bounded by 98%. Take 10% of the length of the line from the buffer distance
275 // to try and minimize any artifacts.
276 const double ptDistAllowance = std::max(distance - l->getLength() * 0.1, distance * 0.98);
277 // Use 102% of the buffer width as the line-length requirement - this
278 // is to ensure that line segments that is length "distance" +/-
279 // epsilon is removed.
280 const double segLengthAllowance = 1.02 * distance;
281
282 size_t front = 0;
283 size_t back = coords->size() - 1;
284 size_t sz = back - front + 1;
285
286 // Clean up the front of the list.
287 // Loop until the line's end is not inside the buffer width from
288 // the startPoint.
289 while (sz > 1 && coords->getAt(front).distance(startPoint) < ptDistAllowance) {
290 // Record the end segment length.
291 double segLength = coords->getAt(front).distance(coords->getAt(front + 1));
292
293 // Stop looping if there are no more points, or if the segment
294 // length is larger than the buffer width.
295 if(sz <= 1 || segLength > segLengthAllowance) {
296 break;
297 }
298
299 // If the first point is less than buffer width away from the
300 // reference point, then delete the point.
301 front++;
302 sz--;
303 }
304 while(sz > 1 && coords->getAt(front).distance(endPoint) < ptDistAllowance) {
305 double segLength = coords->getAt(front).distance(coords->getAt(front + 1));
306 if(sz <= 1 || segLength > segLengthAllowance) {
307 break;
308 }
309 front++;
310 sz--;
311 }
312 // Clean up the back of the list.
313 while(sz > 1 && coords->getAt(back).distance(startPoint) < ptDistAllowance) {
314 double segLength = coords->getAt(back).distance(coords->getAt(back - 1));
315
316 if(sz <= 1 || segLength > segLengthAllowance) {
317 break;
318 }
319 back--;
320 sz--;
321 }
322 while(sz > 1 && coords->getAt(back).distance(endPoint) < ptDistAllowance) {
323 double segLength = coords->getAt(back).distance(coords->getAt(back - 1));
324
325 if(sz <= 1 || segLength > segLengthAllowance) {
326 break;
327 }
328 back--;
329 sz--;
330 }
331
332 if (sz > 1) {
333 if (sz < coords->size()) {
334 // Points were removed; make a new CoordinateSequence
335 auto seqFactory = geomFact->getCoordinateSequenceFactory();
336
337 auto newSeq = seqFactory->create(sz, coords->getDimension());
338
339 for (size_t i = 0; i < sz; i++) {
340 newSeq->setAt(coords->getAt(i + front), i);
341 }
342
343 coords = std::move(newSeq);
344 }
345
346 // Add the coordinates to the resultant line string.
347 mergedLinesGeom->push_back(geomFact->createLineString(coords.release()));
348 }
349 }
350
351 mergedLines.pop_back();
352 }
353
354 // Clean up.
355 if(noder != workingNoder) {
356 delete noder;
357 }
358 buf.reset();
359 singleSided.reset();
360 intersectedLines.reset();
361
362 if(mergedLinesGeom->size() > 1) {
363 return geomFact->createMultiLineString(mergedLinesGeom);
364 }
365 else if(mergedLinesGeom->size() == 1) {
366
367 Geometry* single = (*mergedLinesGeom)[0];
368 delete mergedLinesGeom;
369 return single;
370 }
371 else {
372 delete mergedLinesGeom;
373 return geomFact->createLineString().release();
374 }
375 }
376
377 /*public*/
378 Geometry*
buffer(const Geometry * g,double distance)379 BufferBuilder::buffer(const Geometry* g, double distance)
380 // throw(GEOSException *)
381 {
382 const PrecisionModel* precisionModel = workingPrecisionModel;
383 if(precisionModel == nullptr) {
384 precisionModel = g->getPrecisionModel();
385 }
386
387 assert(precisionModel);
388 assert(g);
389
390 // factory must be the same as the one used by the input
391 geomFact = g->getFactory();
392
393 {
394 // This scope is here to force release of resources owned by
395 // OffsetCurveSetBuilder when we're doing with it
396
397 OffsetCurveBuilder curveBuilder(precisionModel, bufParams);
398 OffsetCurveSetBuilder curveSetBuilder(*g, distance, curveBuilder);
399
400 GEOS_CHECK_FOR_INTERRUPTS();
401
402 std::vector<SegmentString*>& bufferSegStrList = curveSetBuilder.getCurves();
403
404 #if GEOS_DEBUG
405 std::cerr << "OffsetCurveSetBuilder got " << bufferSegStrList.size()
406 << " curves" << std::endl;
407 #endif
408 // short-circuit test
409 if(bufferSegStrList.empty()) {
410 return createEmptyResultGeometry();
411 }
412
413 #if GEOS_DEBUG
414 std::cerr << "BufferBuilder::buffer computing NodedEdges" << std::endl;
415 #endif
416
417 computeNodedEdges(bufferSegStrList, precisionModel);
418
419 GEOS_CHECK_FOR_INTERRUPTS();
420
421 } // bufferSegStrList and contents are released here
422
423 #if GEOS_DEBUG > 1
424 std::cerr << std::endl << edgeList << std::endl;
425 #endif
426
427 Geometry* resultGeom = nullptr;
428 std::unique_ptr< std::vector<Geometry*> > resultPolyList;
429 std::vector<BufferSubgraph*> subgraphList;
430
431 try {
432 PlanarGraph graph(OverlayNodeFactory::instance());
433 graph.addEdges(edgeList.getEdges());
434
435 GEOS_CHECK_FOR_INTERRUPTS();
436
437 createSubgraphs(&graph, subgraphList);
438
439 #if GEOS_DEBUG
440 std::cerr << "Created " << subgraphList.size() << " subgraphs" << std::endl;
441 #if GEOS_DEBUG > 1
442 for(size_t i = 0, n = subgraphList.size(); i < n; i++) {
443 std::cerr << std::setprecision(10) << *(subgraphList[i]) << std::endl;
444 }
445 #endif
446 #endif
447
448 GEOS_CHECK_FOR_INTERRUPTS();
449
450 {
451 // scope for earlier PolygonBuilder cleanupt
452 PolygonBuilder polyBuilder(geomFact);
453 buildSubgraphs(subgraphList, polyBuilder);
454
455 resultPolyList.reset(polyBuilder.getPolygons());
456 }
457
458 // Get rid of the subgraphs, shouldn't be needed anymore
459 for(size_t i = 0, n = subgraphList.size(); i < n; i++) {
460 delete subgraphList[i];
461 }
462 subgraphList.clear();
463
464 #if GEOS_DEBUG
465 std::cerr << "PolygonBuilder got " << resultPolyList->size()
466 << " polygons" << std::endl;
467 #if GEOS_DEBUG > 1
468 for(size_t i = 0, n = resultPolyList->size(); i < n; i++) {
469 std::cerr << (*resultPolyList)[i]->toString() << std::endl;
470 }
471 #endif
472 #endif
473
474 // just in case ...
475 if(resultPolyList->empty()) {
476 return createEmptyResultGeometry();
477 }
478
479 // resultPolyList ownership transferred here
480 resultGeom = geomFact->buildGeometry(resultPolyList.release());
481
482 }
483 catch(const util::GEOSException& /* exc */) {
484
485 // In case they're still around
486 for(size_t i = 0, n = subgraphList.size(); i < n; i++) {
487 delete subgraphList[i];
488 }
489 subgraphList.clear();
490
491 throw;
492 }
493
494 return resultGeom;
495 }
496
497 /*private*/
498 Noder*
getNoder(const PrecisionModel * pm)499 BufferBuilder::getNoder(const PrecisionModel* pm)
500 {
501 // this doesn't change workingNoder precisionModel!
502 if(workingNoder != nullptr) {
503 return workingNoder;
504 }
505
506 // otherwise use a fast (but non-robust) noder
507
508 if(li) { // reuse existing IntersectionAdder and LineIntersector
509 li->setPrecisionModel(pm);
510 assert(intersectionAdder != nullptr);
511 }
512 else {
513 li = new LineIntersector(pm);
514 intersectionAdder = new IntersectionAdder(*li);
515 }
516
517 MCIndexNoder* noder = new MCIndexNoder(intersectionAdder);
518
519 #if 0
520 /* CoordinateArraySequence.cpp:84:
521 * virtual const geos::Coordinate& geos::CoordinateArraySequence::getAt(size_t) const:
522 * Assertion `pos<vect->size()' failed.
523 */
524
525 Noder* noder = new IteratedNoder(pm);
526
527 Noder noder = new MCIndexSnapRounder(pm);
528 Noder noder = new ScaledNoder(
529 new MCIndexSnapRounder(new PrecisionModel(1.0)),
530 pm.getScale());
531 #endif
532
533 return noder;
534
535 }
536
537 /* private */
538 void
computeNodedEdges(SegmentString::NonConstVect & bufferSegStrList,const PrecisionModel * precisionModel)539 BufferBuilder::computeNodedEdges(SegmentString::NonConstVect& bufferSegStrList,
540 const PrecisionModel* precisionModel) // throw(GEOSException)
541 {
542 Noder* noder = getNoder(precisionModel);
543
544 #if JTS_DEBUG
545 geos::io::WKTWriter wktWriter;
546 wktWriter.setTrim(true);
547 std::cerr << "before noding: "
548 << wktWriter.write(
549 convertSegStrings(geomFact, bufferSegStrList.begin(),
550 bufferSegStrList.end()).get()
551 ) << std::endl;
552 #endif
553
554 noder->computeNodes(&bufferSegStrList);
555
556 SegmentString::NonConstVect* nodedSegStrings = \
557 noder->getNodedSubstrings();
558
559 #if JTS_DEBUG
560 std::cerr << "after noding: "
561 << wktWriter.write(
562 convertSegStrings(geomFact, bufferSegStrList.begin(),
563 bufferSegStrList.end()).get()
564 ) << std::endl;
565 #endif
566
567
568 for(SegmentString::NonConstVect::iterator
569 i = nodedSegStrings->begin(), e = nodedSegStrings->end();
570 i != e;
571 ++i) {
572 SegmentString* segStr = *i;
573 const Label* oldLabel = static_cast<const Label*>(segStr->getData());
574
575 auto cs = operation::valid::RepeatedPointRemover::removeRepeatedPoints(segStr->getCoordinates());
576 delete segStr;
577 if(cs->size() < 2) {
578 // don't insert collapsed edges
579 // we need to take care of the memory here as cs is a new sequence
580 continue;
581 }
582
583 // Edge takes ownership of the CoordinateSequence
584 Edge* edge = new Edge(cs.release(), *oldLabel);
585
586 // will take care of the Edge ownership
587 insertUniqueEdge(edge);
588 }
589
590 delete nodedSegStrings;
591
592 if(noder != workingNoder) {
593 delete noder;
594 }
595 }
596
597 /*private*/
598 void
insertUniqueEdge(Edge * e)599 BufferBuilder::insertUniqueEdge(Edge* e)
600 {
601 //<FIX> MD 8 Oct 03 speed up identical edge lookup
602 // fast lookup
603 Edge* existingEdge = edgeList.findEqualEdge(e);
604 // If an identical edge already exists, simply update its label
605 if(existingEdge != nullptr) {
606 Label& existingLabel = existingEdge->getLabel();
607 Label labelToMerge = e->getLabel();
608
609 // check if new edge is in reverse direction to existing edge
610 // if so, must flip the label before merging it
611 if(! existingEdge->isPointwiseEqual(e)) {
612 labelToMerge = e->getLabel();
613 labelToMerge.flip();
614 }
615
616 existingLabel.merge(labelToMerge);
617
618 // compute new depth delta of sum of edges
619 int mergeDelta = depthDelta(labelToMerge);
620 int existingDelta = existingEdge->getDepthDelta();
621 int newDelta = existingDelta + mergeDelta;
622 existingEdge->setDepthDelta(newDelta);
623
624 // we have memory release responsibility
625 delete e;
626
627 }
628 else { // no matching existing edge was found
629
630 // add this new edge to the list of edges in this graph
631 edgeList.add(e);
632
633 e->setDepthDelta(depthDelta(e->getLabel()));
634 }
635 }
636
637 bool
BufferSubgraphGT(BufferSubgraph * first,BufferSubgraph * second)638 BufferSubgraphGT(BufferSubgraph* first, BufferSubgraph* second)
639 {
640 if(first->compareTo(second) > 0) {
641 return true;
642 }
643 else {
644 return false;
645 }
646 }
647
648 /*private*/
649 void
createSubgraphs(PlanarGraph * graph,std::vector<BufferSubgraph * > & subgraphList)650 BufferBuilder::createSubgraphs(PlanarGraph* graph, std::vector<BufferSubgraph*>& subgraphList)
651 {
652 std::vector<Node*> nodes;
653 graph->getNodes(nodes);
654 for(size_t i = 0, n = nodes.size(); i < n; i++) {
655 Node* node = nodes[i];
656 if(!node->isVisited()) {
657 BufferSubgraph* subgraph = new BufferSubgraph();
658 subgraph->create(node);
659 subgraphList.push_back(subgraph);
660 }
661 }
662
663 /*
664 * Sort the subgraphs in descending order of their rightmost coordinate
665 * This ensures that when the Polygons for the subgraphs are built,
666 * subgraphs for shells will have been built before the subgraphs for
667 * any holes they contain
668 */
669 std::sort(subgraphList.begin(), subgraphList.end(), BufferSubgraphGT);
670 }
671
672 /*private*/
673 void
buildSubgraphs(const std::vector<BufferSubgraph * > & subgraphList,PolygonBuilder & polyBuilder)674 BufferBuilder::buildSubgraphs(const std::vector<BufferSubgraph*>& subgraphList,
675 PolygonBuilder& polyBuilder)
676 {
677
678 #if GEOS_DEBUG
679 std::cerr << __FUNCTION__ << " got " << subgraphList.size() << " subgraphs" << std::endl;
680 #endif
681 std::vector<BufferSubgraph*> processedGraphs;
682 for(size_t i = 0, n = subgraphList.size(); i < n; i++) {
683 BufferSubgraph* subgraph = subgraphList[i];
684 Coordinate* p = subgraph->getRightmostCoordinate();
685 assert(p);
686
687 #if GEOS_DEBUG
688 std::cerr << " " << i << ") Subgraph[" << subgraph << "]" << std::endl;
689 std::cerr << " rightmost Coordinate " << *p;
690 #endif
691 SubgraphDepthLocater locater(&processedGraphs);
692 #if GEOS_DEBUG
693 std::cerr << " after SubgraphDepthLocater processedGraphs contain "
694 << processedGraphs.size()
695 << " elements" << std::endl;
696 #endif
697 int outsideDepth = locater.getDepth(*p);
698 #if GEOS_DEBUG
699 std::cerr << " Depth of rightmost coordinate: " << outsideDepth << std::endl;
700 #endif
701 subgraph->computeDepth(outsideDepth);
702 subgraph->findResultEdges();
703 #if GEOS_DEBUG
704 std::cerr << " after computeDepth and findResultEdges subgraph contain:" << std::endl
705 << " " << subgraph->getDirectedEdges()->size() << " DirecteEdges " << std::endl
706 << " " << subgraph->getNodes()->size() << " Nodes " << std::endl;
707 #endif
708 processedGraphs.push_back(subgraph);
709 #if GEOS_DEBUG
710 std::cerr << " added " << subgraph << " to processedGraphs, new size is "
711 << processedGraphs.size() << std::endl;
712 #endif
713 polyBuilder.add(subgraph->getDirectedEdges(), subgraph->getNodes());
714 }
715 }
716
717 /*private*/
718 geom::Geometry*
createEmptyResultGeometry() const719 BufferBuilder::createEmptyResultGeometry() const
720 {
721 geom::Geometry* emptyGeom = geomFact->createPolygon().release();
722 return emptyGeom;
723 }
724
725 } // namespace geos.operation.buffer
726 } // namespace geos.operation
727 } // namespace geos
728
729