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 #ifndef EventQueueInterface_DEFINED 5 #define EventQueueInterface_DEFINED 6 7 #include "modules/bentleyottmann/include/Point.h" 8 #include "modules/bentleyottmann/include/Segment.h" 9 10 #include <set> 11 12 // The EventQueueInterface and the SweepLineInterface allow the EventQueue and the SweepLine 13 // to be tested independently of each other. This allows very specific scenarios to be setup and 14 // tested in isolation. 15 16 namespace bentleyottmann { 17 // -- EventQueueInterface -------------------------------------------------------------------------- 18 // An EventQueueInterface implementation must be able to add crossing events into the event queue. 19 class EventQueueInterface { 20 public: 21 EventQueueInterface() = default; 22 EventQueueInterface(const EventQueueInterface&) = default; 23 EventQueueInterface(EventQueueInterface&&) = default; 24 EventQueueInterface& operator=(const EventQueueInterface&) = default; 25 EventQueueInterface& operator=(EventQueueInterface&&) = default; 26 virtual ~EventQueueInterface() = default; 27 28 virtual void addCrossing(Point crossingPoint, const Segment& s0, const Segment& s1) = 0; 29 }; 30 31 using DeletionSegmentSet = std::set<Segment>; 32 struct OrderBySlope { 33 bool operator()(const Segment& s0, const Segment& s1) const; 34 }; 35 // The set of insertion segments is ordered by slope. Since all the lines pass through the same 36 // point, then the slope of each line must be ordered from smallest to largest to keep the 37 // segment order correct in the sweep line. 38 using InsertionSegmentSet = std::set<Segment, OrderBySlope>; 39 40 // The EventQueue uses an object of SweepLineInterface to find new crossings when manipulating 41 // the sweep line. 42 class SweepLineInterface { 43 public: 44 virtual ~SweepLineInterface() = default; 45 46 // These are the segments to remove from the sweep line. 47 virtual void handleDeletions(Point eventPoint, const DeletionSegmentSet& removing) = 0; 48 49 // Insert inserting into the sweep line. Check the inserting segments against the existing 50 // sweep line segments and report any crossings using the addCrossing from the 51 // EventQueueInterface. 52 virtual void handleInsertionsAndCheckForNewCrossings( 53 Point eventPoint, const InsertionSegmentSet& inserting, EventQueueInterface* queue) = 0; 54 }; 55 } // namespace bentleyottmann 56 #endif // EventQueueInterface_DEFINED 57