1 // Copyright 2023 Google LLC
2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
3
4 #include "modules/bentleyottmann/include/SweepLine.h"
5
6 #include "include/private/base/SkAssert.h"
7 #include "modules/bentleyottmann/include/EventQueueInterface.h"
8 #include "modules/bentleyottmann/include/Point.h"
9 #include <algorithm>
10 #include <iterator>
11 #include <limits>
12 #include <optional>
13 #include <set>
14
15
16 namespace bentleyottmann {
17
SweepLine()18 SweepLine::SweepLine() {
19 static constexpr Segment LeftSentinel = {{-std::numeric_limits<int32_t>::max(),
20 -std::numeric_limits<int32_t>::max()},
21 {-std::numeric_limits<int32_t>::max(),
22 std::numeric_limits<int32_t>::max()}};
23 static constexpr Segment RightSentinel = {{std::numeric_limits<int32_t>::max(),
24 -std::numeric_limits<int32_t>::max()},
25 {std::numeric_limits<int32_t>::max(),
26 std::numeric_limits<int32_t>::max()}};
27
28 fSweepLine.reserve(8);
29 fSweepLine.push_back(LeftSentinel);
30 fSweepLine.push_back(RightSentinel);
31 }
32
verify(int32_t y) const33 void SweepLine::verify(int32_t y) const {
34 for(auto cursor = fSweepLine.begin(); (cursor + 1) != fSweepLine.end(); ++cursor) {
35 [[maybe_unused]] const Segment& left = *cursor;
36 [[maybe_unused]] const Segment& right = *(cursor + 1);
37 SkASSERT(less_than_at(left, right, y));
38 }
39 }
40
handleDeletions(Point eventPoint,const DeletionSegmentSet & removing)41 void SweepLine::handleDeletions(Point eventPoint, const DeletionSegmentSet& removing) {
42 std::vector<Segment>::iterator newEnd;
43 if (removing.empty()) {
44 // Remove ending segments
45 auto toRemove = [eventPoint](Segment s) {
46 return s.lower() == eventPoint;
47 };
48 newEnd = std::remove_if(fSweepLine.begin(), fSweepLine.end(), toRemove);
49 } else {
50 // Remove all ending and crossing segments.
51 auto toRemove = [eventPoint, &removing](Segment s) {
52 return s.lower() == eventPoint || removing.find(s) != removing.end();
53 };
54 newEnd = std::remove_if(fSweepLine.begin(), fSweepLine.end(), toRemove);
55 }
56 fSweepLine.erase(newEnd, fSweepLine.end());
57 }
58
handleInsertionsAndCheckForNewCrossings(Point eventPoint,const InsertionSegmentSet & inserting,EventQueueInterface * queue)59 void SweepLine::handleInsertionsAndCheckForNewCrossings(
60 Point eventPoint, const InsertionSegmentSet& inserting, EventQueueInterface* queue) {
61 // The SlopeSegmentSet makes sure that these segments are in the right order for insertion.
62 auto comp = [](const Segment& s, Point p) {
63 return !point_less_than_segment_in_x(p, s);
64 };
65
66 const auto rightOfInsertion = std::lower_bound(
67 fSweepLine.begin(), fSweepLine.end(), eventPoint, comp);
68 SkASSERT(rightOfInsertion != fSweepLine.begin());
69 const auto leftOfInsertion = rightOfInsertion - 1;
70
71 if (inserting.empty()) {
72 // There were deletions, but no insertions, so check if the two segments at the insertion
73 // point cross.
74 if (auto crossingPoint = intersect(*leftOfInsertion, *rightOfInsertion)) {
75 queue->addCrossing(crossingPoint.value(), *leftOfInsertion, *rightOfInsertion);
76 }
77 } else {
78 // Check if the left most inserted segment crosses the segment immediately to the left of
79 // the insertion cursor.
80 if (auto crossingPoint = intersect(*leftOfInsertion, *inserting.begin())) {
81 queue->addCrossing(crossingPoint.value(), *leftOfInsertion, *inserting.begin());
82 }
83
84 // Check if the right most inserted segment crosses the segment immediately to the right of
85 // the insertion cursor.
86 if (auto crossingPoint = intersect(*inserting.rbegin(), *rightOfInsertion)) {
87 queue->addCrossing(crossingPoint.value(), *inserting.rbegin(), *rightOfInsertion);
88 }
89
90 // Insert the set in the sweep line.
91 fSweepLine.insert(rightOfInsertion, inserting.begin(), inserting.end());
92 }
93 }
94 } // namespace bentleyottmann
95