Coverage Report

Created: 2024-07-27 06:14

/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