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