1 /**********************************************************************
2 *
3 * GEOS - Geometry Engine Open Source
4 * http://geos.osgeo.org
5 *
6 * Copyright (C) 2001-2002 Vivid Solutions Inc.
7 * Copyright (C) 2005 Refractions Research Inc.
8 *
9 * This is free software; you can redistribute and/or modify it under
10 * the terms of the GNU Lesser General Public Licence as published
11 * by the Free Software Foundation.
12 * See the COPYING file for more information.
13 *
14 **********************************************************************
15 *
16 * Last port: operation/relate/EdgeEndBuilder.java rev. 1.12 (JTS-1.10)
17 *
18 **********************************************************************/
19
20 #include <geos/operation/relate/EdgeEndBuilder.h>
21 #include <geos/geom/Coordinate.h>
22 #include <geos/geomgraph/Edge.h>
23 #include <geos/geomgraph/EdgeEnd.h>
24 #include <geos/geomgraph/EdgeIntersectionList.h>
25 #include <geos/geomgraph/Label.h>
26
27 #include <vector>
28
29 using namespace geos::geomgraph;
30 using namespace geos::geom;
31
32 namespace geos {
33 namespace operation { // geos.operation
34 namespace relate { // geos.operation.relate
35
36 std::vector<EdgeEnd*>
computeEdgeEnds(std::vector<Edge * > * edges)37 EdgeEndBuilder::computeEdgeEnds(std::vector<Edge*>* edges)
38 {
39 std::vector<EdgeEnd*> l;
40 for(Edge* e : *edges) {
41 computeEdgeEnds(e, &l);
42 }
43 return l;
44 }
45
46 /**
47 * Creates stub edges for all the intersections in this
48 * Edge (if any) and inserts them into the graph.
49 */
50 void
computeEdgeEnds(Edge * edge,std::vector<EdgeEnd * > * l)51 EdgeEndBuilder::computeEdgeEnds(Edge* edge, std::vector<EdgeEnd*>* l)
52 {
53 EdgeIntersectionList& eiList = edge->getEdgeIntersectionList();
54 //Debug.print(eiList);
55 // ensure that the list has entries for the first and last point of the edge
56 eiList.addEndpoints();
57
58 EdgeIntersectionList::const_iterator it = eiList.begin();
59 // no intersections, so there is nothing to do
60 if(it == eiList.end()) {
61 return;
62 }
63
64 const EdgeIntersection* eiPrev = nullptr;
65 const EdgeIntersection* eiCurr = nullptr;
66
67 const EdgeIntersection* eiNext = &*it;
68 ++it;
69 do {
70 eiPrev = eiCurr;
71 eiCurr = eiNext;
72 eiNext = nullptr;
73 if(it != eiList.end()) {
74 eiNext = &*it;
75 ++it;
76 }
77 if(eiCurr != nullptr) {
78 createEdgeEndForPrev(edge, l, eiCurr, eiPrev);
79 createEdgeEndForNext(edge, l, eiCurr, eiNext);
80 }
81 }
82 while(eiCurr != nullptr);
83 }
84
85 /**
86 * Create a EdgeStub for the edge before the intersection eiCurr.
87 * The previous intersection is provided
88 * in case it is the endpoint for the stub edge.
89 * Otherwise, the previous point from the parent edge will be the endpoint.
90 *
91 * eiCurr will always be an EdgeIntersection, but eiPrev may be null.
92 */
93 void
createEdgeEndForPrev(Edge * edge,std::vector<EdgeEnd * > * l,const EdgeIntersection * eiCurr,const EdgeIntersection * eiPrev)94 EdgeEndBuilder::createEdgeEndForPrev(Edge* edge, std::vector<EdgeEnd*>* l,
95 const EdgeIntersection* eiCurr, const EdgeIntersection* eiPrev)
96 {
97 auto iPrev = eiCurr->segmentIndex;
98 if(eiCurr->dist == 0.0) {
99 // if at the start of the edge there is no previous edge
100 if(iPrev == 0) {
101 return;
102 }
103 iPrev--;
104 }
105 Coordinate pPrev(edge->getCoordinate(iPrev));
106 // if prev intersection is past the previous vertex, use it instead
107 if(eiPrev != nullptr && eiPrev->segmentIndex >= iPrev) {
108 pPrev = eiPrev->coord;
109 }
110 Label label(edge->getLabel());
111 // since edgeStub is oriented opposite to it's parent edge, have to flip sides for edge label
112 label.flip();
113 EdgeEnd* e = new EdgeEnd(edge, eiCurr->coord, pPrev, label);
114 //e.print(System.out); System.out.println();
115 l->push_back(e);
116 }
117
118 /**
119 * Create a StubEdge for the edge after the intersection eiCurr.
120 * The next intersection is provided
121 * in case it is the endpoint for the stub edge.
122 * Otherwise, the next point from the parent edge will be the endpoint.
123 *
124 * eiCurr will always be an EdgeIntersection, but eiNext may be null.
125 */
126 void
createEdgeEndForNext(Edge * edge,std::vector<EdgeEnd * > * l,const EdgeIntersection * eiCurr,const EdgeIntersection * eiNext)127 EdgeEndBuilder::createEdgeEndForNext(Edge* edge, std::vector<EdgeEnd*>* l,
128 const EdgeIntersection* eiCurr, const EdgeIntersection* eiNext)
129 {
130 size_t iNext = eiCurr->segmentIndex + 1;
131 // if there is no next edge there is nothing to do
132 if(iNext >= edge->getNumPoints() && eiNext == nullptr) {
133 return;
134 }
135 Coordinate pNext(edge->getCoordinate(iNext));
136 // if the next intersection is in the same segment as the current, use it as the endpoint
137 if(eiNext != nullptr && eiNext->segmentIndex == eiCurr->segmentIndex) {
138 pNext = eiNext->coord;
139 }
140 EdgeEnd* e = new EdgeEnd(edge, eiCurr->coord, pNext, edge->getLabel());
141 //Debug.println(e);
142 l->push_back(e);
143 }
144
145 } // namespace geos.operation.relate
146 } // namespace geos.operation
147 } // namespace geos
148
149