/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 |