xref: /aosp_15_r20/external/skia/modules/bentleyottmann/src/BentleyOttmann1.cpp (revision c8dee2aa9b3f27cf6c858bd81872bdeb2c07ed17)

// Copyright 2023 Google LLC
// Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.

#include "modules/bentleyottmann/include/BentleyOttmann1.h"

#include "modules/bentleyottmann/include/EventQueue.h"
#include "modules/bentleyottmann/include/Segment.h"
#include "modules/bentleyottmann/include/SweepLine.h"

#include <optional>
#include <utility>
#include <vector>

namespace bentleyottmann {

std::optional<std::vector<Crossing>> bentley_ottmann_1(SkSpan<const Segment> segments) {
    if (auto possibleEQ = EventQueue::Make(segments)) {
        EventQueue eventQueue = std::move(possibleEQ.value());
        SweepLine sweepLine;
        while(eventQueue.hasMoreEvents()) {
            eventQueue.handleNextEventPoint(&sweepLine);
        }
        return eventQueue.crossings();
    }
    return std::nullopt;
}
}  // namespace bentleyottmann