bentleyottmann::EventQueue Class Reference

#include <EventQueue.h>

Inheritance diagram for bentleyottmann::EventQueue:

Public Types
using	Queue = std::set< Event >

Public Member Functions
	EventQueue (Queue &&queue)
	EventQueue ()=default
void	addCrossing (Point crossingPoint, const Segment &s0, const Segment &s1) override
bool	hasMoreEvents () const
void	handleNextEventPoint (SweepLineInterface *handler)
std::vector< Crossing >	crossings ()
Public Member Functions inherited from bentleyottmann::EventQueueInterface
	EventQueueInterface ()=default
	EventQueueInterface (const EventQueueInterface &)=default
	EventQueueInterface (EventQueueInterface &&)=default
EventQueueInterface &	operator= (const EventQueueInterface &)=default
EventQueueInterface &	operator= (EventQueueInterface &&)=default
virtual	~EventQueueInterface ()=default
virtual void	addCrossing (Point crossingPoint, const Segment &s0, const Segment &s1)=0

Static Public Member Functions
static std::optional< EventQueue >	Make (SkSpan< const Segment > segments)

Friends
class	EventQueueTestingPeer

Detailed Description

Definition at line 58 of file EventQueue.h.

Member Typedef Documentation

Queue

using bentleyottmann::EventQueue::Queue = std::set<Event>

Definition at line 63 of file EventQueue.h.

Constructor & Destructor Documentation

EventQueue() [1/2]

bentleyottmann::EventQueue::EventQueue

(

EventQueue::Queue &&

queue

)

Definition at line 40 of file EventQueue.cpp.

: fQueue{std::move(queue)} { }

EventQueue() [2/2]

bentleyottmann::EventQueue::EventQueue ( )

default

Member Function Documentation

addCrossing()

void bentleyottmann::EventQueue::addCrossing ( Point  crossingPoint, const Segment &  s0, const Segment &  s1  )

overridevirtual

Implements bentleyottmann::EventQueueInterface.

Definition at line 49 of file EventQueue.cpp.

                                                                                      {
    this->add({crossingPoint, Cross{s0, s1}});
    fCrossings.push_back({s0, s1, crossingPoint});
}

crossings()

std::vector< Crossing > bentleyottmann::EventQueue::crossings

(

)

Definition at line 125 of file EventQueue.cpp.

                                          {
    return std::vector<Crossing>{fCrossings.begin(), fCrossings.end()};
}

handleNextEventPoint()

void bentleyottmann::EventQueue::handleNextEventPoint

(

SweepLineInterface *

handler

)

Definition at line 63 of file EventQueue.cpp.

                                                                 {
    SkASSERT(!fQueue.empty());
 
    // Clear temp segment buffers.
    fDeletionSet.clear();
    fInsertionSet.clear();
 
    // An events that are Lower points.
    bool hasLower = false;
 
    // Set up the visitors for the different event types.
    auto handleLower = [&hasLower](const Lower& l) {
        hasLower = true;
    };
 
    // Crossing Segments must be deleted and re-inserted in the sweep line.
    auto handleCross = [this](const Cross& c) {
        fDeletionSet.insert({c.s0, c.s1});
        fInsertionSet.insert({c.s0, c.s1});
    };
 
    // Upper events are added to the sweep line, and a lower event is added to the event queue.
    auto handleUpper = [this](const Upper& u) {
        fInsertionSet.insert(u.s);
        // Add the delete event for the inserted segment. Make sure we are not adding more events
        // on this eventPoint.
        SkASSERT(u.s.lower() != u.s.upper());
        this->add(Event{u.s.lower(), Lower{}});
    };
 
    Visitor visitor{handleLower, handleCross, handleUpper};
 
    const Point eventPoint = fQueue.begin()->where;
 
    // We must make forward progress.
    SkASSERT(fLastEventPoint < eventPoint);
    fLastEventPoint = eventPoint;
 
    // Accumulate changes for all events with the same event point.
    auto cursor = fQueue.begin();
    const auto queueEnd = fQueue.end();
    for (; cursor != queueEnd && cursor->where == eventPoint;
         ++cursor) {
        const Event& event = *cursor;
        std::visit(visitor, event.type);
    }
 
    // Remove all accumulated events with the same event point.
    fQueue.erase(fQueue.begin(), cursor);
 
    if (hasLower || !fDeletionSet.empty()) {
        // There are segments to delete.
        handler->handleDeletions(eventPoint, fDeletionSet);
    }
 
    if (hasLower || !fDeletionSet.empty() || !fInsertionSet.empty()) {
        // If there are insertions then insert them. If there are no insertions, but there were
        // deletions we need to check for new crossings.
        handler->handleInsertionsAndCheckForNewCrossings(eventPoint, fInsertionSet, this);
    }
}

hasMoreEvents()

bool bentleyottmann::EventQueue::hasMoreEvents

(

)

const

Definition at line 54 of file EventQueue.cpp.

                                     {
    return !fQueue.empty();
}

Make()

std::optional< EventQueue > bentleyottmann::EventQueue::Make ( SkSpan< const Segment >  segments )

static

Definition at line 14 of file EventQueue.cpp.

                                                                       {
    Queue queue;
 
    int32_t left   = Point::Largest().x,
            top    = Point::Largest().y,
            right  = Point::Smallest().x,
            bottom = Point::Smallest().y;
 
    for(const Segment& s : segments) {
        auto [l, t, r, b] = s.bounds();
        left   = std::min(l, left);
        top    = std::min(t, top);
        right  = std::max(r, right);
        bottom = std::max(b, bottom);
 
        queue.insert(Event{s.upper(), Upper{s}});
    }
 
    // If min max difference is too large, fail.
    if (Point::DifferenceTooBig(Point{left, top}, Point{right, bottom})) {
        return std::nullopt;
    }
 
    return EventQueue{std::move(queue)};
}

Friends And Related Function Documentation

EventQueueTestingPeer

friend class EventQueueTestingPeer

friend

Definition at line 77 of file EventQueue.h.

---

The documentation for this class was generated from the following files:

• third_party/skia/modules/bentleyottmann/include/EventQueue.h
• third_party/skia/modules/bentleyottmann/src/EventQueue.cpp