/src/geos/src/geomgraph/EdgeRing.cpp

Source
/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2011 Sandro Santilli <strk@kbt.io>
 * Copyright (C) 2005-2006 Refractions Research Inc.
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation.
 * See the COPYING file for more information.
 *
 **********************************************************************
 *
 * Last port: geomgraph/EdgeRing.java r428 (JTS-1.12+)
 *
 **********************************************************************/

#include <geos/util/Assert.h>
#include <geos/util/TopologyException.h>
#include <geos/algorithm/PointLocation.h>
#include <geos/algorithm/Orientation.h>
#include <geos/geomgraph/EdgeRing.h>
#include <geos/geomgraph/DirectedEdge.h>
#include <geos/geomgraph/DirectedEdgeStar.h>
#include <geos/geomgraph/Edge.h>
#include <geos/geomgraph/Node.h>
#include <geos/geomgraph/Label.h>
#include <geos/geom/Position.h>
#include <geos/geom/CoordinateSequence.h>
#include <geos/geom/GeometryFactory.h>
#include <geos/geom/LinearRing.h>
#include <geos/geom/Location.h>
#include <geos/geom/Envelope.h>
#include <geos/util.h>

#include <vector>
#include <cassert>
#include <iostream> // for operator<<

#ifndef GEOS_DEBUG
#define GEOS_DEBUG 0
#endif

using namespace geos::algorithm;
using namespace geos::geom;

namespace geos {
namespace geomgraph { // geos.geomgraph

EdgeRing::EdgeRing(DirectedEdge* newStart,
                   const GeometryFactory* newGeometryFactory)
    :
    startDe(newStart),
    geometryFactory(newGeometryFactory),
    holes(),
    maxNodeDegree(-1),
    edges(),
    label(Location::NONE), // new Label(Location::NONE)),
    ring(nullptr),
    isHoleVar(false),
    shell(nullptr)
{
    /*
     * Commented out to fix different polymorphism in C++ (from Java)
     * Make sure these calls are made by derived classes !
     */
    //computePoints(start);
    //computeRing();
#if GEOS_DEBUG
    std::cerr << "EdgeRing[" << this << "] ctor" << std::endl;
#endif
    testInvariant();
}

bool
EdgeRing::isIsolated()
{
    testInvariant();
    return (label.getGeometryCount() == 1);
}

bool
EdgeRing::isHole()
{
    testInvariant();

    // We can't tell if this is an hole
    // unless we computed the ring
    // see computeRing()
    assert(ring);

    return isHoleVar;
}


LinearRing*
EdgeRing::getLinearRing()
{
    testInvariant();
    return ring.get();
}

Label&
EdgeRing::getLabel()
{
    testInvariant();
    return label;
}

bool
EdgeRing::isShell()
{
    testInvariant();
    return (shell == nullptr);
}

EdgeRing*
EdgeRing::getShell()
{
    testInvariant();
    return shell;
}

void
EdgeRing::setShell(EdgeRing* newShell)
{
    shell = newShell;
    if(shell != nullptr) {
        shell->addHole(this);
    }
    testInvariant();
}

void
EdgeRing::addHole(EdgeRing* edgeRing)
{
    holes.emplace_back(edgeRing);
    testInvariant();
}

/*public*/
std::unique_ptr<Polygon>
EdgeRing::toPolygon(const GeometryFactory* p_geometryFactory)
{
    testInvariant();

    // We don't use "clone" here because
    // GeometryFactory::createPolygon really
    // wants a LinearRing
    auto shellLR = detail::make_unique<LinearRing>(*(getLinearRing()));
    if (holes.empty()) {
        return p_geometryFactory->createPolygon(std::move(shellLR));
    } else {
        std::size_t nholes = holes.size();
        std::vector<std::unique_ptr<LinearRing>> holeLR(nholes);
        for(std::size_t i = 0; i < nholes; ++i) {
            holeLR[i] = detail::make_unique<LinearRing>(*(holes[i]->getLinearRing()));
        }

        return p_geometryFactory->createPolygon(std::move(shellLR), std::move(holeLR));
    }
}

/*public*/
void
EdgeRing::computeRing()
{
    testInvariant();

    if(ring != nullptr) {
        return;    // don't compute more than once
    }
    auto coordSeq = detail::make_unique<CoordinateSequence>(std::move(pts));
    ring = geometryFactory->createLinearRing(std::move(coordSeq));
    isHoleVar = Orientation::isCCW(ring->getCoordinatesRO());

    testInvariant();
}

/*public*/
std::vector<DirectedEdge*>&
EdgeRing::getEdges()
{
    testInvariant();

    return edges;
}

/*protected*/
void
EdgeRing::computePoints(DirectedEdge* newStart)
// throw(const TopologyException &)
{
    startDe = newStart;
    DirectedEdge* de = newStart;
    bool isFirstEdge = true;
    do {
        //util::Assert::isTrue(de!=NULL,"EdgeRing::computePoints: found null Directed Edge");
        //assert(de!=NULL); // EdgeRing::computePoints: found null Directed Edge
        if(de == nullptr)
            throw util::TopologyException(
                "EdgeRing::computePoints: found null Directed Edge");

        if(de->getEdgeRing() == this)
            throw util::TopologyException(
                "Directed Edge visited twice during ring-building",
                de->getCoordinate());

        edges.push_back(de);
        const Label& deLabel = de->getLabel();
        assert(deLabel.isArea());
        mergeLabel(deLabel);
        addPoints(de->getEdge(), de->isForward(), isFirstEdge);
        isFirstEdge = false;
        setEdgeRing(de, this);
        de = getNext(de);
    }
    while(de != startDe);

    testInvariant();

}

/*public*/
int
EdgeRing::getMaxNodeDegree()
{

    testInvariant();

    if(maxNodeDegree < 0) {
        computeMaxNodeDegree();
    }
    return maxNodeDegree;
}

/*private*/
void
EdgeRing::computeMaxNodeDegree()
{
    maxNodeDegree = 0;
    DirectedEdge* de = startDe;
    do {
        Node* node = de->getNode();
        EdgeEndStar* ees = node->getEdges();
        DirectedEdgeStar* des = detail::down_cast<DirectedEdgeStar*>(ees);
        int degree = des->getOutgoingDegree(this);
        if(degree > maxNodeDegree) {
            maxNodeDegree = degree;
        }
        de = getNext(de);
    }
    while(de != startDe);
    maxNodeDegree *= 2;

    testInvariant();

}

/*public*/
void
EdgeRing::setInResult()
{
    DirectedEdge* de = startDe;
    do {
        de->getEdge()->setInResult(true);
        de = de->getNext();
    }
    while(de != startDe);

    testInvariant();

}

/*protected*/
void
EdgeRing::mergeLabel(const Label& deLabel)
{
    mergeLabel(deLabel, 0);
    mergeLabel(deLabel, 1);

    testInvariant();

}

/*protected*/
void
EdgeRing::mergeLabel(const Label& deLabel, uint8_t geomIndex)
{

    testInvariant();

    Location loc = deLabel.getLocation(geomIndex, Position::RIGHT);
    // no information to be had from this label
    if(loc == Location::NONE) {
        return;
    }

    // if there is no current RHS value, set it
    if(label.getLocation(geomIndex) == Location::NONE) {
        label.setLocation(geomIndex, loc);
        return;
    }
}

/*protected*/
void
EdgeRing::addPoints(Edge* edge, bool isForward, bool isFirstEdge)
{
    // EdgeRing::addPoints: can't add points after LinearRing construction
    assert(ring == nullptr);

    assert(edge);
    const CoordinateSequence* edgePts = edge->getCoordinates();

    assert(edgePts);
    std::size_t numEdgePts = edgePts->getSize();

    if(isForward) {
        if(isFirstEdge) {
            pts = *edgePts;
            return;
        } else {
            for(std::size_t i = 1; i < numEdgePts; ++i) {
                pts.add(edgePts->getAt(i));
            }
        }
    }

    else { // is backward
        std::size_t startIndex = numEdgePts - 1;
        if(isFirstEdge) {
            startIndex = numEdgePts;
        }
        for(std::size_t i = startIndex; i > 0; --i) {
            pts.add(edgePts->getAt(i - 1));
        }
    }

    testInvariant();
}

/*public*/
bool
EdgeRing::containsPoint(const Coordinate& p)
{
    testInvariant();

    assert(ring);

    const Envelope* env = ring->getEnvelopeInternal();
    assert(env);
    if(! env->contains(p)) {
        return false;
    }

    if(! PointLocation::isInRing(p, ring->getCoordinatesRO())) {
        return false;
    }

    for(const auto& hole : holes) {
        assert(hole);
        if(hole->containsPoint(p)) {
            return false;
        }
    }
    return true;
}

std::ostream&
operator<< (std::ostream& os, const EdgeRing& er)
{
    os << "EdgeRing[" << &er << "]: "
       << std::endl;
    return os;
}

} // namespace geos.geomgraph
} // namespace geos


Coverage Report

Created: 2026-01-22 06:39

Line	Count	Source
1		/**********************************************************************
2		*
3		* GEOS - Geometry Engine Open Source
4		* http://geos.osgeo.org
5		*
6		* Copyright (C) 2011 Sandro Santilli <strk@kbt.io>
7		* Copyright (C) 2005-2006 Refractions Research Inc.
8		* Copyright (C) 2001-2002 Vivid Solutions Inc.
9		*
10		* This is free software; you can redistribute and/or modify it under
11		* the terms of the GNU Lesser General Public Licence as published
12		* by the Free Software Foundation.
13		* See the COPYING file for more information.
14		*
15		**********************************************************************
16		*
17		* Last port: geomgraph/EdgeRing.java r428 (JTS-1.12+)
18		*
19		**********************************************************************/
20
21		#include <geos/util/Assert.h>
22		#include <geos/util/TopologyException.h>
23		#include <geos/algorithm/PointLocation.h>
24		#include <geos/algorithm/Orientation.h>
25		#include <geos/geomgraph/EdgeRing.h>
26		#include <geos/geomgraph/DirectedEdge.h>
27		#include <geos/geomgraph/DirectedEdgeStar.h>
28		#include <geos/geomgraph/Edge.h>
29		#include <geos/geomgraph/Node.h>
30		#include <geos/geomgraph/Label.h>
31		#include <geos/geom/Position.h>
32		#include <geos/geom/CoordinateSequence.h>
33		#include <geos/geom/GeometryFactory.h>
34		#include <geos/geom/LinearRing.h>
35		#include <geos/geom/Location.h>
36		#include <geos/geom/Envelope.h>
37		#include <geos/util.h>
38
39		#include <vector>
40		#include <cassert>
41		#include <iostream> // for operator<<
42
43		#ifndef GEOS_DEBUG
44		#define GEOS_DEBUG 0
45		#endif
46
47		using namespace geos::algorithm;
48		using namespace geos::geom;
49
50		namespace geos {
51		namespace geomgraph { // geos.geomgraph
52
53		EdgeRing::EdgeRing(DirectedEdge* newStart,
54		const GeometryFactory* newGeometryFactory)
55		:
56	0	startDe(newStart),
57	0	geometryFactory(newGeometryFactory),
58	0	holes(),
59	0	maxNodeDegree(-1),
60	0	edges(),
61	0	label(Location::NONE), // new Label(Location::NONE)),
62	0	ring(nullptr),
63	0	isHoleVar(false),
64	0	shell(nullptr)
65	0	{
66		/*
67		* Commented out to fix different polymorphism in C++ (from Java)
68		* Make sure these calls are made by derived classes !
69		*/
70		//computePoints(start);
71		//computeRing();
72		#if GEOS_DEBUG
73		std::cerr << "EdgeRing[" << this << "] ctor" << std::endl;
74		#endif
75	0	testInvariant();
76	0	}
77
78		bool
79		EdgeRing::isIsolated()
80	0	{
81	0	testInvariant();
82	0	return (label.getGeometryCount() == 1);
83	0	}
84
85		bool
86		EdgeRing::isHole()
87	0	{
88	0	testInvariant();
89
90		// We can't tell if this is an hole
91		// unless we computed the ring
92		// see computeRing()
93	0	assert(ring);
94
95	0	return isHoleVar;
96	0	}
97
98
99		LinearRing*
100		EdgeRing::getLinearRing()
101	0	{
102	0	testInvariant();
103	0	return ring.get();
104	0	}
105
106		Label&
107		EdgeRing::getLabel()
108	0	{
109	0	testInvariant();
110	0	return label;
111	0	}
112
113		bool
114		EdgeRing::isShell()
115	0	{
116	0	testInvariant();
117	0	return (shell == nullptr);
118	0	}
119
120		EdgeRing*
121		EdgeRing::getShell()
122	0	{
123	0	testInvariant();
124	0	return shell;
125	0	}
126
127		void
128		EdgeRing::setShell(EdgeRing* newShell)
129	0	{
130	0	shell = newShell;
131	0	if(shell != nullptr) {
132	0	shell->addHole(this);
133	0	}
134	0	testInvariant();
135	0	}
136
137		void
138		EdgeRing::addHole(EdgeRing* edgeRing)
139	0	{
140	0	holes.emplace_back(edgeRing);
141	0	testInvariant();
142	0	}
143
144		/public/
145		std::unique_ptr<Polygon>
146		EdgeRing::toPolygon(const GeometryFactory* p_geometryFactory)
147	0	{
148	0	testInvariant();
149
150		// We don't use "clone" here because
151		// GeometryFactory::createPolygon really
152		// wants a LinearRing
153	0	auto shellLR = detail::make_unique<LinearRing>(*(getLinearRing()));
154	0	if (holes.empty()) {
155	0	return p_geometryFactory->createPolygon(std::move(shellLR));
156	0	} else {
157	0	std::size_t nholes = holes.size();
158	0	std::vector<std::unique_ptr<LinearRing>> holeLR(nholes);
159	0	for(std::size_t i = 0; i < nholes; ++i) {
160	0	holeLR[i] = detail::make_unique<LinearRing>(*(holes[i]->getLinearRing()));
161	0	}
162
163	0	return p_geometryFactory->createPolygon(std::move(shellLR), std::move(holeLR));
164	0	}
165	0	}
166
167		/public/
168		void
169		EdgeRing::computeRing()
170	0	{
171	0	testInvariant();
172
173	0	if(ring != nullptr) {
174	0	return; // don't compute more than once
175	0	}
176	0	auto coordSeq = detail::make_unique<CoordinateSequence>(std::move(pts));
177	0	ring = geometryFactory->createLinearRing(std::move(coordSeq));
178	0	isHoleVar = Orientation::isCCW(ring->getCoordinatesRO());
179
180	0	testInvariant();
181	0	}
182
183		/public/
184		std::vector<DirectedEdge*>&
185		EdgeRing::getEdges()
186	0	{
187	0	testInvariant();
188
189	0	return edges;
190	0	}
191
192		/protected/
193		void
194		EdgeRing::computePoints(DirectedEdge* newStart)
195		// throw(const TopologyException &)
196	0	{
197	0	startDe = newStart;
198	0	DirectedEdge* de = newStart;
199	0	bool isFirstEdge = true;
200	0	do {
201		//util::Assert::isTrue(de!=NULL,"EdgeRing::computePoints: found null Directed Edge");
202		//assert(de!=NULL); // EdgeRing::computePoints: found null Directed Edge
203	0	if(de == nullptr)
204	0	throw util::TopologyException(
205	0	"EdgeRing::computePoints: found null Directed Edge");
206
207	0	if(de->getEdgeRing() == this)
208	0	throw util::TopologyException(
209	0	"Directed Edge visited twice during ring-building",
210	0	de->getCoordinate());
211
212	0	edges.push_back(de);
213	0	const Label& deLabel = de->getLabel();
214	0	assert(deLabel.isArea());
215	0	mergeLabel(deLabel);
216	0	addPoints(de->getEdge(), de->isForward(), isFirstEdge);
217	0	isFirstEdge = false;
218	0	setEdgeRing(de, this);
219	0	de = getNext(de);
220	0	}
221	0	while(de != startDe);
222
223	0	testInvariant();
224
225	0	}
226
227		/public/
228		int
229		EdgeRing::getMaxNodeDegree()
230	0	{
231
232	0	testInvariant();
233
234	0	if(maxNodeDegree < 0) {
235	0	computeMaxNodeDegree();
236	0	}
237	0	return maxNodeDegree;
238	0	}
239
240		/private/
241		void
242		EdgeRing::computeMaxNodeDegree()
243	0	{
244	0	maxNodeDegree = 0;
245	0	DirectedEdge* de = startDe;
246	0	do {
247	0	Node* node = de->getNode();
248	0	EdgeEndStar* ees = node->getEdges();
249	0	DirectedEdgeStar* des = detail::down_cast<DirectedEdgeStar*>(ees);
250	0	int degree = des->getOutgoingDegree(this);
251	0	if(degree > maxNodeDegree) {
252	0	maxNodeDegree = degree;
253	0	}
254	0	de = getNext(de);
255	0	}
256	0	while(de != startDe);
257	0	maxNodeDegree *= 2;
258
259	0	testInvariant();
260
261	0	}
262
263		/public/
264		void
265		EdgeRing::setInResult()
266	0	{
267	0	DirectedEdge* de = startDe;
268	0	do {
269	0	de->getEdge()->setInResult(true);
270	0	de = de->getNext();
271	0	}
272	0	while(de != startDe);
273
274	0	testInvariant();
275
276	0	}
277
278		/protected/
279		void
280		EdgeRing::mergeLabel(const Label& deLabel)
281	0	{
282	0	mergeLabel(deLabel, 0);
283	0	mergeLabel(deLabel, 1);
284
285	0	testInvariant();
286
287	0	}
288
289		/protected/
290		void
291		EdgeRing::mergeLabel(const Label& deLabel, uint8_t geomIndex)
292	0	{
293
294	0	testInvariant();
295
296	0	Location loc = deLabel.getLocation(geomIndex, Position::RIGHT);
297		// no information to be had from this label
298	0	if(loc == Location::NONE) {
299	0	return;
300	0	}
301
302		// if there is no current RHS value, set it
303	0	if(label.getLocation(geomIndex) == Location::NONE) {
304	0	label.setLocation(geomIndex, loc);
305	0	return;
306	0	}
307	0	}
308
309		/protected/
310		void
311		EdgeRing::addPoints(Edge* edge, bool isForward, bool isFirstEdge)
312	0	{
313		// EdgeRing::addPoints: can't add points after LinearRing construction
314	0	assert(ring == nullptr);
315
316	0	assert(edge);
317	0	const CoordinateSequence* edgePts = edge->getCoordinates();
318
319	0	assert(edgePts);
320	0	std::size_t numEdgePts = edgePts->getSize();
321
322	0	if(isForward) {
323	0	if(isFirstEdge) {
324	0	pts = *edgePts;
325	0	return;
326	0	} else {
327	0	for(std::size_t i = 1; i < numEdgePts; ++i) {
328	0	pts.add(edgePts->getAt(i));
329	0	}
330	0	}
331	0	}
332
333	0	else { // is backward
334	0	std::size_t startIndex = numEdgePts - 1;
335	0	if(isFirstEdge) {
336	0	startIndex = numEdgePts;
337	0	}
338	0	for(std::size_t i = startIndex; i > 0; --i) {
339	0	pts.add(edgePts->getAt(i - 1));
340	0	}
341	0	}
342
343	0	testInvariant();
344	0	}
345
346		/public/
347		bool
348		EdgeRing::containsPoint(const Coordinate& p)
349	0	{
350	0	testInvariant();
351
352	0	assert(ring);
353
354	0	const Envelope* env = ring->getEnvelopeInternal();
355	0	assert(env);
356	0	if(! env->contains(p)) {
357	0	return false;
358	0	}
359
360	0	if(! PointLocation::isInRing(p, ring->getCoordinatesRO())) {
361	0	return false;
362	0	}
363
364	0	for(const auto& hole : holes) {
365	0	assert(hole);
366	0	if(hole->containsPoint(p)) {
367	0	return false;
368	0	}
369	0	}
370	0	return true;
371	0	}
372
373		std::ostream&
374		operator<< (std::ostream& os, const EdgeRing& er)
375	0	{
376	0	os << "EdgeRing[" << &er << "]: "
377	0	<< std::endl;
378	0	return os;
379	0	}
380
381		} // namespace geos.geomgraph
382		} // namespace geos
383