/src/geos/include/geos/operation/overlayng/OverlayLabeller.h

Source
/**********************************************************************
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.osgeo.org
 *
 * Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
 *
 * 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.
 *
 **********************************************************************/

#pragma once

#include <geos/export.h>
#include <geos/geom/Location.h>
#include <geos/operation/overlayng/OverlayGraph.h>

#include <vector>
#include <deque>

// Forward declarations
namespace geos {
namespace geom {
class Coordinate;
}
namespace operation {
namespace overlayng {
class OverlayLabel;
class OverlayGraph;
class OverlayEdge;
class InputGeometry;
}
}
}

namespace geos {      // geos.
namespace operation { // geos.operation
namespace overlayng { // geos.operation.overlayng


class GEOS_DLL OverlayLabeller {

private:

    // Members
    OverlayGraph* graph;
    InputGeometry* inputGeometry;
    std::vector<OverlayEdge*>& edges;

    /**
    * Finds a boundary edge for this geom, if one exists.
    */
    static OverlayEdge* findPropagationStartEdge(OverlayEdge* nodeEdge, uint8_t geomIndex);

    /**
    * At this point collapsed edges with unknown location
    * must be disconnected from the boundary edges of the parent
    * (because otherwise the location would have
    * been propagated from them).
    * This can occur with a collapsed hole or shell.
    * The edges can be labeled based on their parent ring role (shell or hole).
    * (This cannot be done earlier, because the location
    * based on the boundary edges must take precedence.
    * There are situations where a collapsed edge has a location
    * which is different to its ring role -
    * e.g. a narrow gore in a polygon, which is in
    * the interior of the reduced polygon, but whose
    * ring role would imply the location EXTERIOR.)
    *
    * Note that collapsed edges can NOT have location determined via a PIP location check,
    * because that is done against the unreduced input geometry,
    * which may give an invalid result due to topology collapse.
    *
    * The labeling is propagated to other connected linear edges,
    * since there may be NOT_PART edges which are connected,
    * and they can be labeled in the same way.
    * (These would get labeled anyway during subsequent disconnected labeling pass,
    * but may be more efficient and accurate to do it here.)
    */
    void labelCollapsedEdges();
    static void labelCollapsedEdge(OverlayEdge* edge, uint8_t geomIndex);

    /**
    * There can be edges which have unknown location
    * but are connected to a Line edge with known location.
    * In this case line location is propagated to the connected edges.
    */
    void labelConnectedLinearEdges();
    void propagateLinearLocations(uint8_t geomIndex);
    static void propagateLinearLocationAtNode(OverlayEdge* eNode, uint8_t geomIndex, bool isInputLine, std::deque<OverlayEdge*>& edgeStack);

    /**
    * Finds all OverlayEdges which are linear
    * (i.e. line or collapsed) and have a known location
    * for the given input geometry.
    */
    static std::vector<OverlayEdge*> findLinearEdgesWithLocation(const std::vector<OverlayEdge *> &edges, uint8_t geomIndex);

    /**
    * At this point there may still be edges which have unknown location
    * relative to an input geometry.
    * This must be because they are NOT_PART edges for that geometry,
    * and are disconnected from any edges of that geometry.
    * An example of this is rings of one geometry wholly contained
    * in another geometry.
    * The location must be fully determined to compute a
    * correct result for all overlay operations.
    *
    * If the input geometry is an Area the edge location can
    * be determined via a PIP test.
    * If the input is not an Area the location is EXTERIOR.
    */
    void labelDisconnectedEdges();

    /**
    * Determines the location of an edge relative to a target input geometry.
    * The edge has no location information
    * because it is disconnected from other
    * edges that would provide that information.
    * The location is determined by checking
    * if the edge lies inside the target geometry area (if any).
    */
    void labelDisconnectedEdge(OverlayEdge* edge, uint8_t geomIndex);

    /**
    * Determines the {@link Location} for an edge within an Area geometry
    * via point-in-polygon location.
    *
    * NOTE this is only safe to use for disconnected edges,
    * since the test is carried out against the original input geometry,
    * and precision reduction may cause incorrect results for edges
    * which are close enough to a boundary to become connected.
    */
    geom::Location locateEdge(uint8_t geomIndex, OverlayEdge* edge);

    /**
    * Determines the {@link Location} for an edge within an Area geometry
    * via point-in-polygon location,
    * by checking that both endpoints are interior to the target geometry.
    * Checking both endpoints ensures correct results in the presence of topology collapse.
    * <p>
    * NOTE this is only safe to use for disconnected edges,
    * since the test is carried out against the original input geometry,
    * and precision reduction may cause incorrect results for edges
    * which are close enough to a boundary to become connected.
    */
    geom::Location locateEdgeBothEnds(uint8_t geomIndex, OverlayEdge* edge);

    /**
    * Labels edges around nodes based on the arrangement
    * of incident area boundary edges.
    * Also propagates the labelling to connected linear edges.
    */
    void labelAreaNodeEdges(std::vector<OverlayEdge*>& nodes);



public:

    OverlayLabeller(OverlayGraph* p_graph, InputGeometry* p_inputGeometry)
        : graph(p_graph)
        , inputGeometry(p_inputGeometry)
        , edges(p_graph->getEdges())
    {}

    /**
    * Computes the topological labelling for the edges in the graph->
    */
    void computeLabelling();

    /**
    * Scans around a node CCW, propagating the side labels
    * for a given area geometry to all edges (and their sym)
    * with unknown locations for that geometry.
    */
    void propagateAreaLocations(OverlayEdge* nodeEdge, uint8_t geomIndex);

    void markResultAreaEdges(int overlayOpCode);

    /**
    * Marks an edge which forms part of the boundary of the result area.
    * This is determined by the overlay operation being executed,
    * and the location of the edge.
    * The relevant location is either the right side of a boundary edge,
    * or the line location of a non-boundary edge.
    */
    static void markInResultArea(OverlayEdge* e, int overlayOpCode);

    /**
    * Unmarks result area edges where the sym edge
    * is also marked as in the result.
    * This has the effect of merging edge-adjacent result areas,
    * as required by polygon validity rules.
    */
    void unmarkDuplicateEdgesFromResultArea();


};


} // namespace geos.operation.overlayng
} // namespace geos.operation
} // namespace geos


Coverage Report

Created: 2026-02-14 06:22

Line	Count	Source
1		/**********************************************************************
2		*
3		* GEOS - Geometry Engine Open Source
4		* http://geos.osgeo.org
5		*
6		* Copyright (C) 2020 Paul Ramsey <pramsey@cleverelephant.ca>
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		#pragma once
16
17		#include <geos/export.h>
18		#include <geos/geom/Location.h>
19		#include <geos/operation/overlayng/OverlayGraph.h>
20
21		#include <vector>
22		#include <deque>
23
24		// Forward declarations
25		namespace geos {
26		namespace geom {
27		class Coordinate;
28		}
29		namespace operation {
30		namespace overlayng {
31		class OverlayLabel;
32		class OverlayGraph;
33		class OverlayEdge;
34		class InputGeometry;
35		}
36		}
37		}
38
39		namespace geos { // geos.
40		namespace operation { // geos.operation
41		namespace overlayng { // geos.operation.overlayng
42
43
44		class GEOS_DLL OverlayLabeller {
45
46		private:
47
48		// Members
49		OverlayGraph* graph;
50		InputGeometry* inputGeometry;
51		std::vector<OverlayEdge*>& edges;
52
53		/**
54		* Finds a boundary edge for this geom, if one exists.
55		*/
56		static OverlayEdge* findPropagationStartEdge(OverlayEdge* nodeEdge, uint8_t geomIndex);
57
58		/**
59		* At this point collapsed edges with unknown location
60		* must be disconnected from the boundary edges of the parent
61		* (because otherwise the location would have
62		* been propagated from them).
63		* This can occur with a collapsed hole or shell.
64		* The edges can be labeled based on their parent ring role (shell or hole).
65		* (This cannot be done earlier, because the location
66		* based on the boundary edges must take precedence.
67		* There are situations where a collapsed edge has a location
68		* which is different to its ring role -
69		* e.g. a narrow gore in a polygon, which is in
70		* the interior of the reduced polygon, but whose
71		* ring role would imply the location EXTERIOR.)
72		*
73		* Note that collapsed edges can NOT have location determined via a PIP location check,
74		* because that is done against the unreduced input geometry,
75		* which may give an invalid result due to topology collapse.
76		*
77		* The labeling is propagated to other connected linear edges,
78		* since there may be NOT_PART edges which are connected,
79		* and they can be labeled in the same way.
80		* (These would get labeled anyway during subsequent disconnected labeling pass,
81		* but may be more efficient and accurate to do it here.)
82		*/
83		void labelCollapsedEdges();
84		static void labelCollapsedEdge(OverlayEdge* edge, uint8_t geomIndex);
85
86		/**
87		* There can be edges which have unknown location
88		* but are connected to a Line edge with known location.
89		* In this case line location is propagated to the connected edges.
90		*/
91		void labelConnectedLinearEdges();
92		void propagateLinearLocations(uint8_t geomIndex);
93		static void propagateLinearLocationAtNode(OverlayEdge* eNode, uint8_t geomIndex, bool isInputLine, std::deque<OverlayEdge*>& edgeStack);
94
95		/**
96		* Finds all OverlayEdges which are linear
97		* (i.e. line or collapsed) and have a known location
98		* for the given input geometry.
99		*/
100		static std::vector<OverlayEdge> findLinearEdgesWithLocation(const std::vector<OverlayEdge > &edges, uint8_t geomIndex);
101
102		/**
103		* At this point there may still be edges which have unknown location
104		* relative to an input geometry.
105		* This must be because they are NOT_PART edges for that geometry,
106		* and are disconnected from any edges of that geometry.
107		* An example of this is rings of one geometry wholly contained
108		* in another geometry.
109		* The location must be fully determined to compute a
110		* correct result for all overlay operations.
111		*
112		* If the input geometry is an Area the edge location can
113		* be determined via a PIP test.
114		* If the input is not an Area the location is EXTERIOR.
115		*/
116		void labelDisconnectedEdges();
117
118		/**
119		* Determines the location of an edge relative to a target input geometry.
120		* The edge has no location information
121		* because it is disconnected from other
122		* edges that would provide that information.
123		* The location is determined by checking
124		* if the edge lies inside the target geometry area (if any).
125		*/
126		void labelDisconnectedEdge(OverlayEdge* edge, uint8_t geomIndex);
127
128		/**
129		* Determines the {@link Location} for an edge within an Area geometry
130		* via point-in-polygon location.
131		*
132		* NOTE this is only safe to use for disconnected edges,
133		* since the test is carried out against the original input geometry,
134		* and precision reduction may cause incorrect results for edges
135		* which are close enough to a boundary to become connected.
136		*/
137		geom::Location locateEdge(uint8_t geomIndex, OverlayEdge* edge);
138
139		/**
140		* Determines the {@link Location} for an edge within an Area geometry
141		* via point-in-polygon location,
142		* by checking that both endpoints are interior to the target geometry.
143		* Checking both endpoints ensures correct results in the presence of topology collapse.
144		* <p>
145		* NOTE this is only safe to use for disconnected edges,
146		* since the test is carried out against the original input geometry,
147		* and precision reduction may cause incorrect results for edges
148		* which are close enough to a boundary to become connected.
149		*/
150		geom::Location locateEdgeBothEnds(uint8_t geomIndex, OverlayEdge* edge);
151
152		/**
153		* Labels edges around nodes based on the arrangement
154		* of incident area boundary edges.
155		* Also propagates the labelling to connected linear edges.
156		*/
157		void labelAreaNodeEdges(std::vector<OverlayEdge*>& nodes);
158
159
160
161		public:
162
163		OverlayLabeller(OverlayGraph* p_graph, InputGeometry* p_inputGeometry)
164	307k	: graph(p_graph)
165	307k	, inputGeometry(p_inputGeometry)
166	307k	, edges(p_graph->getEdges())
167	307k	{}
168
169		/**
170		* Computes the topological labelling for the edges in the graph->
171		*/
172		void computeLabelling();
173
174		/**
175		* Scans around a node CCW, propagating the side labels
176		* for a given area geometry to all edges (and their sym)
177		* with unknown locations for that geometry.
178		*/
179		void propagateAreaLocations(OverlayEdge* nodeEdge, uint8_t geomIndex);
180
181		void markResultAreaEdges(int overlayOpCode);
182
183		/**
184		* Marks an edge which forms part of the boundary of the result area.
185		* This is determined by the overlay operation being executed,
186		* and the location of the edge.
187		* The relevant location is either the right side of a boundary edge,
188		* or the line location of a non-boundary edge.
189		*/
190		static void markInResultArea(OverlayEdge* e, int overlayOpCode);
191
192		/**
193		* Unmarks result area edges where the sym edge
194		* is also marked as in the result.
195		* This has the effect of merging edge-adjacent result areas,
196		* as required by polygon validity rules.
197		*/
198		void unmarkDuplicateEdgesFromResultArea();
199
200
201		};
202
203
204		} // namespace geos.operation.overlayng
205		} // namespace geos.operation
206		} // namespace geos
207