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/EventQueue.h"
5
6 #include "include/private/base/SkAssert.h"
7 #include <algorithm>
8 #include <cstdint>
9 #include <utility>
10
11 namespace bentleyottmann {
12
13 // -- EventQueue -----------------------------------------------------------------------------------
Make(SkSpan<const Segment> segments)14 std::optional<EventQueue> EventQueue::Make(SkSpan<const Segment> segments) {
15 Queue queue;
16
17 int32_t left = Point::Largest().x,
18 top = Point::Largest().y,
19 right = Point::Smallest().x,
20 bottom = Point::Smallest().y;
21
22 for(const Segment& s : segments) {
23 auto [l, t, r, b] = s.bounds();
24 left = std::min(l, left);
25 top = std::min(t, top);
26 right = std::max(r, right);
27 bottom = std::max(b, bottom);
28
29 queue.insert(Event{s.upper(), Upper{s}});
30 }
31
32 // If min max difference is too large, fail.
33 if (Point::DifferenceTooBig(Point{left, top}, Point{right, bottom})) {
34 return std::nullopt;
35 }
36
37 return EventQueue{std::move(queue)};
38 }
39
EventQueue(EventQueue::Queue && queue)40 EventQueue::EventQueue(EventQueue::Queue&& queue) : fQueue{std::move(queue)} { }
41
add(const Event & event)42 void EventQueue::add(const Event& event) {
43 // New events must be up stream from the current event.
44 SkASSERT(fLastEventPoint < event.where);
45
46 fQueue.insert(event);
47 }
48
addCrossing(Point crossingPoint,const Segment & s0,const Segment & s1)49 void EventQueue::addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) {
50 this->add({crossingPoint, Cross{s0, s1}});
51 fCrossings.push_back({s0, s1, crossingPoint});
52 }
53
hasMoreEvents() const54 bool EventQueue::hasMoreEvents() const {
55 return !fQueue.empty();
56 }
57
58 template<class... Ts>
59 struct Visitor : Ts... { using Ts::operator()...; };
60 template<class... Ts>
61 Visitor(Ts...) -> Visitor<Ts...>;
62
handleNextEventPoint(SweepLineInterface * handler)63 void EventQueue::handleNextEventPoint(SweepLineInterface* handler) {
64 SkASSERT(!fQueue.empty());
65
66 // Clear temp segment buffers.
67 fDeletionSet.clear();
68 fInsertionSet.clear();
69
70 // An events that are Lower points.
71 bool hasLower = false;
72
73 // Set up the visitors for the different event types.
74 auto handleLower = [&hasLower](const Lower& l) {
75 hasLower = true;
76 };
77
78 // Crossing Segments must be deleted and re-inserted in the sweep line.
79 auto handleCross = [this](const Cross& c) {
80 fDeletionSet.insert({c.s0, c.s1});
81 fInsertionSet.insert({c.s0, c.s1});
82 };
83
84 // Upper events are added to the sweep line, and a lower event is added to the event queue.
85 auto handleUpper = [this](const Upper& u) {
86 fInsertionSet.insert(u.s);
87 // Add the delete event for the inserted segment. Make sure we are not adding more events
88 // on this eventPoint.
89 SkASSERT(u.s.lower() != u.s.upper());
90 this->add(Event{u.s.lower(), Lower{}});
91 };
92
93 Visitor visitor{handleLower, handleCross, handleUpper};
94
95 const Point eventPoint = fQueue.begin()->where;
96
97 // We must make forward progress.
98 SkASSERT(fLastEventPoint < eventPoint);
99 fLastEventPoint = eventPoint;
100
101 // Accumulate changes for all events with the same event point.
102 auto cursor = fQueue.begin();
103 const auto queueEnd = fQueue.end();
104 for (; cursor != queueEnd && cursor->where == eventPoint;
105 ++cursor) {
106 const Event& event = *cursor;
107 std::visit(visitor, event.type);
108 }
109
110 // Remove all accumulated events with the same event point.
111 fQueue.erase(fQueue.begin(), cursor);
112
113 if (hasLower || !fDeletionSet.empty()) {
114 // There are segments to delete.
115 handler->handleDeletions(eventPoint, fDeletionSet);
116 }
117
118 if (hasLower || !fDeletionSet.empty() || !fInsertionSet.empty()) {
119 // If there are insertions then insert them. If there are no insertions, but there were
120 // deletions we need to check for new crossings.
121 handler->handleInsertionsAndCheckForNewCrossings(eventPoint, fInsertionSet, this);
122 }
123 }
124
crossings()125 std::vector<Crossing> EventQueue::crossings() {
126 return std::vector<Crossing>{fCrossings.begin(), fCrossings.end()};
127 }
128
operator ()(const bentleyottmann::Segment & s0,const bentleyottmann::Segment & s1) const129 bool OrderBySlope::operator()(const bentleyottmann::Segment& s0,
130 const bentleyottmann::Segment& s1) const {
131 return compare_slopes(s0, s1) < 0;
132 }
133 } // namespace bentleyottmann
134