Coverage Report

Created: 2026-10-31 06:47

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/src/geos/src/geomgraph/index/SimpleMCSweepLineIntersector.cpp
Line
Count
Source
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
#include <algorithm>
17
#include <vector>
18
19
#include <geos/geomgraph/index/SimpleMCSweepLineIntersector.h>
20
#include <geos/geomgraph/index/MonotoneChainEdge.h>
21
#include <geos/geomgraph/index/MonotoneChain.h>
22
#include <geos/geomgraph/index/SweepLineEvent.h>
23
#include <geos/geomgraph/Edge.h>
24
#include <geos/util/Interrupt.h>
25
#include <geos/util.h>
26
27
namespace geos {
28
namespace geomgraph { // geos.geomgraph
29
namespace index { // geos.geomgraph.index
30
31
void
32
SimpleMCSweepLineIntersector::computeIntersections(std::vector<Edge*>* edges,
33
        SegmentIntersector* si, bool testAllSegments)
34
0
{
35
0
    if(testAllSegments) {
36
0
        add(edges, nullptr);
37
0
    }
38
0
    else {
39
0
        add(edges);
40
0
    }
41
0
    computeIntersections(si);
42
0
}
43
44
void
45
SimpleMCSweepLineIntersector::computeIntersections(std::vector<Edge*>* edges0,
46
        std::vector<Edge*>* edges1, SegmentIntersector* si)
47
0
{
48
0
    add(edges0, edges0);
49
0
    add(edges1, edges1);
50
0
    computeIntersections(si);
51
0
}
52
53
void
54
SimpleMCSweepLineIntersector::add(std::vector<Edge*>* edges)
55
0
{
56
0
    for(std::size_t i = 0; i < edges->size(); ++i) {
57
0
        Edge* edge = (*edges)[i];
58
        // edge is its own group
59
0
        add(edge, edge);
60
0
    }
61
0
}
62
63
void
64
SimpleMCSweepLineIntersector::add(std::vector<Edge*>* edges, void* edgeSet)
65
0
{
66
0
    for(std::size_t i = 0; i < edges->size(); ++i) {
67
0
        Edge* edge = (*edges)[i];
68
0
        add(edge, edgeSet);
69
0
    }
70
0
}
71
72
void
73
SimpleMCSweepLineIntersector::add(Edge* edge, void* edgeSet)
74
0
{
75
0
    MonotoneChainEdge* mce = edge->getMonotoneChainEdge();
76
0
    auto& startIndex = mce->getStartIndexes();
77
0
    std::size_t n = startIndex.size() - 1;
78
79
0
    for(std::size_t i = 0; i < n; ++i) {
80
0
        GEOS_CHECK_FOR_INTERRUPTS();
81
0
        chains.emplace_back(mce, i);
82
0
        MonotoneChain* mc = &chains.back();
83
84
0
        eventStore.emplace_back(edgeSet, mce->getMinX(i), nullptr, mc);
85
0
        SweepLineEvent* insertEvent = &eventStore.back();
86
87
0
        eventStore.emplace_back(edgeSet, mce->getMaxX(i), insertEvent, mc);
88
0
    }
89
0
}
90
91
/**
92
 * Because Delete Events have a link to their corresponding Insert event,
93
 * it is possible to compute exactly the range of events which must be
94
 * compared to a given Insert event object.
95
 */
96
void
97
SimpleMCSweepLineIntersector::prepareEvents()
98
0
{
99
0
    events.clear();
100
0
    events.reserve(eventStore.size());
101
0
    for (auto& e : eventStore) {
102
0
        events.push_back(&e);
103
0
    }
104
105
0
    sort(events.begin(), events.end(), SweepLineEventLessThen());
106
0
    for(std::size_t i = 0; i < events.size(); ++i) {
107
0
        GEOS_CHECK_FOR_INTERRUPTS();
108
0
        auto& ev = events[i];
109
0
        if(ev->isDelete()) {
110
0
            ev->getInsertEvent()->setDeleteEventIndex(i);
111
0
        }
112
0
    }
113
0
}
114
115
void
116
SimpleMCSweepLineIntersector::computeIntersections(SegmentIntersector* si)
117
0
{
118
0
    nOverlaps = 0;
119
0
    prepareEvents();
120
0
    for(std::size_t i = 0; i < events.size(); ++i) {
121
0
        GEOS_CHECK_FOR_INTERRUPTS();
122
0
        auto& ev = events[i];
123
0
        if(ev->isInsert()) {
124
0
            processOverlaps(i, ev->getDeleteEventIndex(), ev, si);
125
0
        }
126
0
        if(si->getIsDone()) {
127
0
            break;
128
0
        }
129
0
    }
130
0
}
131
132
void
133
SimpleMCSweepLineIntersector::processOverlaps(std::size_t start, std::size_t end,
134
        SweepLineEvent* ev0, SegmentIntersector* si)
135
0
{
136
0
    MonotoneChain* mc0 = detail::down_cast<MonotoneChain*>(ev0->getObject());
137
138
    /*
139
     * Since we might need to test for self-intersections,
140
     * include current insert event object in list of event objects to test.
141
     * Last index can be skipped, because it must be a Delete event.
142
     */
143
0
    for(auto i = start; i < end; ++i) {
144
0
        auto& ev1 = events[i];
145
0
        if(ev1->isInsert()) {
146
0
            MonotoneChain* mc1 = detail::down_cast<MonotoneChain*>(ev1->getObject());
147
148
0
            if (mc1 == mc0) {
149
                // Don't try to compute intersections between a MonotoneChain
150
                // and itself. SegmentIntersector::addIntersections will just
151
                // ignore them anyway.
152
0
                continue;
153
0
            }
154
155
            // don't compare edges in same group
156
            // null group indicates that edges should be compared
157
0
            if(ev0->edgeSet == nullptr || (ev0->edgeSet != ev1->edgeSet)) {
158
0
                mc0->computeIntersections(mc1, si);
159
0
                nOverlaps++;
160
0
            }
161
0
        }
162
0
    }
163
0
}
164
165
} // namespace geos.geomgraph.index
166
} // namespace geos.geomgraph
167
} // namespace geos