/src/geos/src/index/chain/MonotoneChain.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /********************************************************************** |
2 | | * |
3 | | * GEOS - Geometry Engine Open Source |
4 | | * http://geos.osgeo.org |
5 | | * |
6 | | * Copyright (C) 2006 Refractions Research Inc. |
7 | | * Copyright (C) 2001-2002 Vivid Solutions 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: index/chain/MonotoneChain.java rev. 1.15 (JTS-1.10) |
17 | | * |
18 | | **********************************************************************/ |
19 | | |
20 | | #include <geos/index/chain/MonotoneChain.h> |
21 | | #include <geos/index/chain/MonotoneChainSelectAction.h> |
22 | | #include <geos/index/chain/MonotoneChainOverlapAction.h> |
23 | | #include <geos/geom/CoordinateSequence.h> |
24 | | #include <geos/geom/LineSegment.h> |
25 | | #include <geos/geom/Envelope.h> |
26 | | #include <geos/util.h> |
27 | | |
28 | | using namespace geos::geom; |
29 | | |
30 | | namespace geos { |
31 | | namespace index { // geos.index |
32 | | namespace chain { // geos.index.chain |
33 | | |
34 | | MonotoneChain::MonotoneChain(const geom::CoordinateSequence& newPts, |
35 | | std::size_t nstart, std::size_t nend, void* nContext) |
36 | | : pts(&newPts) |
37 | | , context(nContext) |
38 | | , start(nstart) |
39 | | , end(nend) |
40 | | , env() |
41 | 65.4M | {} |
42 | | |
43 | | const Envelope& |
44 | | MonotoneChain::getEnvelope() const |
45 | 0 | { |
46 | 0 | return getEnvelope(0.0); |
47 | 0 | } |
48 | | |
49 | | const Envelope& |
50 | | MonotoneChain::getEnvelope(double expansionDistance) const |
51 | 65.4M | { |
52 | 65.4M | if (env.isNull()) { |
53 | 65.4M | env.init(pts->getAt<CoordinateXY>(start), pts->getAt<CoordinateXY>(end)); |
54 | 65.4M | if (expansionDistance > 0.0) { |
55 | 9.03M | env.expandBy(expansionDistance); |
56 | 9.03M | } |
57 | 65.4M | } |
58 | 65.4M | return env; |
59 | 65.4M | } |
60 | | |
61 | | std::unique_ptr<CoordinateSequence> |
62 | | MonotoneChain::getCoordinates() const |
63 | 0 | { |
64 | 0 | return pts->clone(); |
65 | 0 | } |
66 | | |
67 | | void |
68 | | MonotoneChain::select(const Envelope& searchEnv, MonotoneChainSelectAction& mcs) const |
69 | 0 | { |
70 | 0 | computeSelect(searchEnv, start, end, mcs); |
71 | 0 | } |
72 | | |
73 | | void |
74 | | MonotoneChain::computeSelect(const Envelope& searchEnv, |
75 | | std::size_t start0, std::size_t end0, |
76 | | MonotoneChainSelectAction& mcs) const |
77 | 0 | { |
78 | 0 | const CoordinateXY& p0 = pts->getAt<CoordinateXY>(start0); |
79 | 0 | const CoordinateXY& p1 = pts->getAt<CoordinateXY>(end0); |
80 | | |
81 | | // terminating condition for the recursion |
82 | 0 | if(end0 - start0 == 1) { |
83 | 0 | mcs.select(*this, start0); |
84 | 0 | return; |
85 | 0 | } |
86 | | // nothing to do if the envelopes don't overlap |
87 | 0 | if(!searchEnv.intersects(p0, p1)) { |
88 | 0 | return; |
89 | 0 | } |
90 | | // the chains overlap,so split each in half and iterate (binary search) |
91 | 0 | std::size_t mid = (start0 + end0) / 2; |
92 | | |
93 | | // Assert: mid != start or end (since we checked above for end-start <= 1) |
94 | | // check terminating conditions before recursing |
95 | 0 | if(start0 < mid) { |
96 | 0 | computeSelect(searchEnv, start0, mid, mcs); |
97 | 0 | } |
98 | |
|
99 | 0 | if(mid < end0) { |
100 | 0 | computeSelect(searchEnv, mid, end0, mcs); |
101 | 0 | } |
102 | 0 | } |
103 | | |
104 | | /* public */ |
105 | | void |
106 | | MonotoneChain::computeOverlaps(const MonotoneChain* mc, |
107 | | MonotoneChainOverlapAction* mco) const |
108 | 0 | { |
109 | 0 | computeOverlaps(start, end, *mc, mc->start, mc->end, 0.0, *mco); |
110 | 0 | } |
111 | | |
112 | | /* public */ |
113 | | void |
114 | | MonotoneChain::computeOverlaps(const MonotoneChain* mc, double overlapTolerance, |
115 | | MonotoneChainOverlapAction* mco) const |
116 | 592M | { |
117 | 592M | computeOverlaps(start, end, *mc, mc->start, mc->end, overlapTolerance, *mco); |
118 | 592M | } |
119 | | |
120 | | /*private*/ |
121 | | void |
122 | | MonotoneChain::computeOverlaps(std::size_t start0, std::size_t end0, |
123 | | const MonotoneChain& mc, |
124 | | std::size_t start1, std::size_t end1, |
125 | | double overlapTolerance, |
126 | | MonotoneChainOverlapAction& mco) const |
127 | 671M | { |
128 | | // terminating condition for the recursion |
129 | 671M | if(end0 - start0 == 1 && end1 - start1 == 1) { |
130 | 499M | mco.overlap(*this, start0, mc, start1); |
131 | 499M | return; |
132 | 499M | } |
133 | | |
134 | | // nothing to do if the envelopes of these subchains don't overlap |
135 | 171M | if(!overlaps(start0, end0, mc, start1, end1, overlapTolerance)) { |
136 | 695k | return; |
137 | 695k | } |
138 | | |
139 | | // the chains overlap,so split each in half and iterate (binary search) |
140 | 170M | std::size_t mid0 = (start0 + end0) / 2; |
141 | 170M | std::size_t mid1 = (start1 + end1) / 2; |
142 | | |
143 | | // Assert: mid != start or end (since we checked above for |
144 | | // end-start <= 1) |
145 | | // check terminating conditions before recursing |
146 | 170M | if(start0 < mid0) { |
147 | 16.3M | if(start1 < mid1) { |
148 | 3.14M | computeOverlaps(start0, mid0, mc, start1, mid1, overlapTolerance, mco); |
149 | 3.14M | } |
150 | 16.3M | if(mid1 < end1) { |
151 | 16.3M | computeOverlaps(start0, mid0, mc, mid1, end1, overlapTolerance, mco); |
152 | 16.3M | } |
153 | 16.3M | } |
154 | | |
155 | 170M | if(mid0 < end0) { |
156 | 36.9M | if(start1 < mid1) { |
157 | 22.9M | computeOverlaps(mid0, end0, mc, start1, mid1, overlapTolerance, mco); |
158 | 22.9M | } |
159 | 36.9M | if(mid1 < end1) { |
160 | 36.1M | computeOverlaps(mid0, end0, mc, mid1, end1, overlapTolerance, mco); |
161 | 36.1M | } |
162 | 36.9M | } |
163 | 170M | } |
164 | | |
165 | | /*private*/ |
166 | | bool |
167 | | MonotoneChain::overlaps(const CoordinateXY& p1, const CoordinateXY& p2, |
168 | | const CoordinateXY& q1, const CoordinateXY& q2, |
169 | | double overlapTolerance) |
170 | 145M | { |
171 | 145M | double maxq = std::max(q1.x, q2.x); |
172 | 145M | double minp = std::min(p1.x, p2.x); |
173 | 145M | if (minp > (maxq + overlapTolerance)) |
174 | 8.71k | return false; |
175 | | |
176 | 145M | double minq = std::min(q1.x, q2.x); |
177 | 145M | double maxp = std::max(p1.x, p2.x); |
178 | 145M | if (maxp < (minq - overlapTolerance)) |
179 | 103k | return false; |
180 | | |
181 | 145M | maxq = std::max(q1.y, q2.y); |
182 | 145M | minp = std::min(p1.y, p2.y); |
183 | 145M | if (minp > (maxq + overlapTolerance)) |
184 | 11.6k | return false; |
185 | | |
186 | 145M | minq = std::min(q1.y, q2.y); |
187 | 145M | maxp = std::max(p1.y, p2.y); |
188 | 145M | if (maxp < (minq - overlapTolerance)) |
189 | 22.3k | return false; |
190 | | |
191 | 145M | return true; |
192 | 145M | } |
193 | | |
194 | | |
195 | | } // namespace geos.index.chain |
196 | | } // namespace geos.index |
197 | | } // namespace geos |