Myers.cpp

Go to the documentation of this file.

// 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/Myers.h"
 
#include "include/core/SkSpan.h"
#include "include/private/base/SkAssert.h"
#include "include/private/base/SkTo.h"
#include "modules/bentleyottmann/include/Int96.h"
 
#include <algorithm>
#include <climits>
#include <cstdint>
#include <iterator>
#include <tuple>
#include <utility>
#include <vector>
 
namespace myers {
 
// -- Point ----------------------------------------------------------------------------------------
Point operator-(const Point& p0, const Point& p1) {
    return {p0.x - p1.x, p0.y - p1.y};
}
 
std::tuple<int64_t, int64_t> point_to_s64(Point p) {
    return std::make_tuple(SkToS64(p.x), SkToS64(p.y));
}
 
// -- Segment --------------------------------------------------------------------------------------
const Point& Segment::upper() const {
    return fUpper;
}
 
const Point& Segment::lower() const {
    return fLower;
}
 
std::tuple<int32_t, int32_t, int32_t, int32_t> Segment::bounds() const {
    auto [left, right] = std::minmax(fUpper.x, fLower.x);
    return std::make_tuple(left, fUpper.y, right, fLower.y);
}
 
bool Segment::isHorizontal() const {
    return fUpper.y == fLower.y;
}
 
bool Segment::isVertical() const {
    return fUpper.x == fLower.x;
}
 
// Return:
//    | d0x   d1x |
//    | d0y   d1y |
int64_t cross(Point d0, Point d1) {
    const auto [d0x, d0y] = point_to_s64(d0);
    const auto [d1x, d1y] = point_to_s64(d1);
    return d0x * d1y - d1x * d0y;
}
 
// compare_slopes returns a comparison of the slope of s0 to the slope of s1 where
//    slope(s) = dx / dy
// instead of the regular dy / dx, and neither s0 nor s1 are horizontal.
//
// The slope for non-horizontal segments monotonically increases from the smallest along the
// negative x-axis increasing counterclockwise to the largest along the positive x-axis.
int64_t compare_slopes(const Segment& s0, const Segment& s1) {
    // Handle cases involving horizontal segments.
    if (s0.isHorizontal() || s1.isHorizontal()) {
        if (s0.isHorizontal() && s1.isHorizontal()) {
            // slope(s0) == slope(s1)
            return 0;
        }
        if (s0.isHorizontal()) {
            // slope(s0) > slope(s1)
            return 1;
        } else {
            // slope(s0) < slope(s1)
            return -1;
        }
    }
 
    const auto [u0, l0] = s0;
    const auto [u1, l1] = s1;
 
    const Point d0 = l0 - u0;
    const Point d1 = l1 - u1;
 
    // Since horizontal lines are handled separately and because of the ordering of points for
    // a segment, then d0y and d1y should always be positive.
    SkASSERT(d0.y > 0 && d1.y > 0);
 
    //     * slope(s0) = d0.x / d0.y
    //     * slope(s1) = d1.x / d1.y
    // If we want to find d0.x / d0.y < d1.x / d1.y, then
    //    d0x * d1y < d1x * d0y
    //    d0x * d1y - d1x * d0y < 0.
    //
    // We know that d0.y and d1.y are both positive, therefore, we can do a cross multiply without
    // worrying about changing the relation.
    // We can define ==, and > in a similar way:
    //    * <  - cross_of_slopes(s0, s1) < 0
    //    * == - cross_of_slopes(s0, s1) == 0
    //    * >  - cross_of_slopes(s0, s1) > 0
    return cross(d0, d1);
}
 
// Returns true of slope(s0) < slope(s1). See compare_slopes above for more information.
bool slope_s0_less_than_slope_s1(const Segment& s0, const Segment& s1) {
    return compare_slopes(s0, s1) < 0;
}
 
// compare_point_to_segment the relation between a point p and a segment s in the following way:
//     * p < s if the cross product is negative.
//     * p == s if the cross product is zero.
//     * p > s if the cross product is positive.
int64_t compare_point_to_segment(Point p, const Segment& s) {
    const auto [u, l] = s;
 
    // The segment must span p vertically.
    SkASSERT(u.y <= p.y && p.y <= l.y);
 
    // Check horizontal extents.
    {
        const auto [left, right] = std::minmax(u.x, l.x);
        if (p.x < left) {
            return -1;
        }
 
        if (right < p.x) {
            return 1;
        }
    }
 
    // If s is horizontal, then p is on the interval [u.x, l.x].
    if (s.isHorizontal()) {
        return 0;
    }
 
    // The point p < s when:
    //     p.x < u.x + (l.x - u.x)(p.y - u.y) / (l.y - u.y),
    //     p.x - u.x < (l.x - u.x)(p.y - u.y) / (l.y - u.y),
    //     (p.x - u.x)(l.y - u.y) < (l.x - u.x)(p.y - u.y),
    //     (p.x - u.x)(l.y - u.y) - (l.x - u.x)(p.y - u.y) < 0,
    //     (p - u) x (l - u) < 0,
    //     dUtoP x dS < 0.
    // The other relations can be implemented in a similar way.
    const Point dUToP = p - u;
    const Point dS = l - u;
 
    SkASSERT(dS.y > 0);
    return cross(dUToP, dS);
}
 
// segment_less_than_upper_to_insert is used with std::lower_bound to find the place to insert the
// segment to_insert in a vector. The signature of this function is crafted to work with
// lower_bound.
bool segment_less_than_upper_to_insert(const Segment& segment, const Segment& to_insert) {
    const int64_t compare = compare_point_to_segment(to_insert.upper(), segment);
 
    // compare > 0 when segment < to_insert.upper().
    return (compare > 0) || ((compare == 0) && slope_s0_less_than_slope_s1(segment, to_insert));
}
 
// Return true if s0(y) < s1(y) else if s0(y) == s1(y) then slope(s0) < slope(s1)
bool s0_less_than_s1_at_y(const Segment& s0, const Segment& s1, int32_t y) {
    // Neither s0 nor s1 are horizontal because this is used during the sorting phase
    SkASSERT(!s0.isHorizontal() && !s1.isHorizontal());
 
    const auto [u0, l0] = s0;
    const auto [u1, l1] = s1;
 
    const auto [left0, right0] = std::minmax(u0.x, l0.x);
    const auto [left1, right1] = std::minmax(u1.x, l1.x);
 
    if (right0 < left1) {
        return true;
    } else if (right1 < left0) {
        return false;
    }
 
    const Point d0 = l0 - u0;
    const Point d1 = l1 - u1;
 
    // Since horizontal lines are handled separately and the ordering of points for the segment,
    // then there should always be positive Dy.
    SkASSERT(d0.y > 0 && d1.y > 0);
 
    namespace bo = bentleyottmann;
    using Int96 = bo::Int96;
 
    // Defining s0(y) and s1(y),
    //    s0(y) = u0.x + (y - u0.y) * d0.x / d0.y
    //    s1(y) = u1.x + (y - u1.y) * d1.x / d1.y
    // Find the following
    //    s0(y) < s1(y)
    // Substituting s0(y) and s1(y)
    //    u0.x + (y - u0.y) * d0.x / d0.y < u1.x + (y - u1.y) * d1.x / d1.y
    // Factoring out the denominator.
    //    (u0.x * d0.y + (y - u0.y) * d0.x) / d0.y < (u1.x * d1.y + (y - u1.y) * d1.x) / d1.y
    // Cross-multiplying the denominators. The sign will not switch because d0.y and d1.y are
    // always positive.
    //    d1.y * (u0.x * d0.y + (y - u0.y) * d0.x) < d0.y * (u1.x * d1.y + (y - u1.y) * d1.x)
    // If these are equal, then we use the slope to break the tie.
    //    d0.x / d0.y < d1.x / d1.y
    // Cross multiplying leaves.
    //    d0.x * d1.y < d1.x * d0.y
    const Int96 lhs = bo::multiply(d1.y, u0.x * SkToS64(d0.y) + (y - u0.y) * SkToS64(d0.x));
    const Int96 rhs = bo::multiply(d0.y, u1.x * SkToS64(d1.y) + (y - u1.y) * SkToS64(d1.x));
 
    return lhs < rhs || ((lhs == rhs) && slope_s0_less_than_slope_s1(s0, s1));
}
 
// -- Event ----------------------------------------------------------------------------------------
// Events are horizontal lines at a given y where segments are added, or they contain one or
// more horizontal lines, or segments end.
struct Event {
    const int32_t y;
 
    // The set of segments that begin at y.
    SkSpan<const Segment> begin;
 
    // The set of segments that are horizontal on y.
    SkSpan<const Segment> horizontal;
 
    // The set of segments that end on y.
    SkSpan<const Segment> end;
};
 
// -- EventQueue -----------------------------------------------------------------------------------
// The EventQueue produces Events. Events are never added to the queue after initial creation.
class EventQueue {
    class Iterator {
    public:
        using value_type = Event;
        using difference_type = ptrdiff_t;
        using pointer = value_type*;
        using reference = value_type;
        using iterator_category = std::input_iterator_tag;
        Iterator(const EventQueue& eventQueue, size_t index)
            : fEventQueue{eventQueue}
            , fIndex{index} { }
        Iterator(const Iterator& that) : Iterator{ that.fEventQueue, that.fIndex } { }
        Iterator& operator++() { ++fIndex; return *this; }
        Iterator operator++(int) { Iterator tmp(*this); operator++(); return tmp; }
        bool operator==(const Iterator& rhs) const { return fIndex == rhs.fIndex; }
        bool operator!=(const Iterator& rhs) const { return fIndex != rhs.fIndex; }
        value_type operator*() { return fEventQueue[fIndex]; }
        friend difference_type operator-(Iterator lhs, Iterator rhs) {
            return lhs.fIndex - rhs.fIndex;
        }
 
    private:
        const EventQueue& fEventQueue;
        size_t fIndex = 0;
    };
 
    // Events are stored using CompactEvent, Events are only passed back from nextEvent. start,
    // endOfBegin, etc. are all indexes into fSegmentStorage. The beginning segments for the event
    // are from start to endOfBegin, the horizontal segments are from endOfBegin to endOfStart, and
    // the end segments are from endOfHorizontal to endOfEnd.
    class CompactEvent {
    public:
        const int32_t y;
        const int32_t start;
        const int32_t endOfBegin;
        const int32_t endOfHorizontal;
        const int32_t endOfEnd;
    };
 
public:
    // Given a list of segments make an EventQueue, and populate its queue with events.
    static EventQueue Make(const SkSpan<const Segment> segments) {
        SkASSERT(!segments.empty());
        SkASSERT(segments.size() < INT32_MAX);
 
        enum EventType {
            kBegin = 0,
            kHorizontal = 1,
            kEnd = 2
        };
 
        // A vector of SetupTuple when ordered will produce the events, and all the different
        // sets of segments (beginning, etc.).
        struct SetupTuple {
            // The main ordering of events.
            int32_t yOrdering;
 
            // Group together like event types together.
            EventType type;
 
            // Break ties if yOrdering is the same.
            int32_t xTieBreaker;
 
            // We want to sort the segments, but they are not part of the key.
            Segment originalSegment;
 
            bool operator==(const SetupTuple& r) const {
                return
                    std::tie(this->yOrdering, this->type, this->xTieBreaker, this->originalSegment)
                        == std::tie(r.yOrdering, r.type, r.xTieBreaker, r.originalSegment);
            }
        };
 
        std::vector<SetupTuple> eventOrdering;
        for (const auto& s : segments) {
 
            // Exclude zero length segments.
            if (s.upper() == s.lower()) {
                continue;
            }
 
            if (s.isHorizontal()) {
                // Tag for the horizontal set.
                eventOrdering.push_back(SetupTuple{s.upper().y, kHorizontal, -s.upper().x, s});
            } else {
                // Tag for the beginning and ending sets.
                eventOrdering.push_back(SetupTuple{s.upper().y, kBegin, -s.upper().x, s});
                eventOrdering.push_back(SetupTuple{s.lower().y, kEnd, -s.lower().x, s});
            }
        }
 
        // Order the tuples by y, then by set type, then by x value.
        auto eventLess = [](const SetupTuple& l, const SetupTuple& r) {
            return std::tie(l.yOrdering, l.type, l.xTieBreaker) <
                   std::tie(r.yOrdering, r.type, r.xTieBreaker);
        };
 
        // Sort the events.
        std::sort(eventOrdering.begin(), eventOrdering.end(), eventLess);
 
        // Remove duplicate segments.
        auto eraseFrom = std::unique(eventOrdering.begin(), eventOrdering.end());
        eventOrdering.erase(eraseFrom, eventOrdering.end());
 
        std::vector<CompactEvent> events;
        std::vector<Segment> segmentStorage;
        segmentStorage.reserve(eventOrdering.size());
 
        int32_t currentY = eventOrdering.front().yOrdering;
        int32_t start = 0,
                endOfBegin = 0,
                endOfHorizontal = 0,
                endOfEnd = 0;
        for (const auto& [y, type, _, s] : eventOrdering) {
            // If this is a new y then create the compact event.
            if (currentY != y) {
                events.push_back(CompactEvent{currentY,
                                              start,
                                              endOfBegin,
                                              endOfHorizontal,
                                              endOfEnd});
                start = endOfBegin = endOfHorizontal = endOfEnd = segmentStorage.size();
                currentY = y;
            }
 
            segmentStorage.push_back(s);
 
            // Increment the various set indices.
            const size_t segmentCount = segmentStorage.size();
            switch (type) {
                case kBegin: endOfBegin = segmentCount;
                    [[fallthrough]];
                case kHorizontal: endOfHorizontal = segmentCount;
                    [[fallthrough]];
                case kEnd: endOfEnd = segmentCount;
            }
        }
 
        // Store the last event.
        events.push_back(CompactEvent{currentY,
                                      start,
                                      endOfBegin,
                                      endOfHorizontal,
                                      endOfEnd});
 
        return EventQueue{std::move(events), std::move(segmentStorage)};
    }
 
    Event operator[](size_t i) const {
        SkASSERT(i < fEvents.size());
        auto& [y, start, endOfBegin, endOfHorizontal, endOfEnd] = fEvents[i];
        SkSpan<const Segment> begin{&fSegmentStorage[start], endOfBegin - start};
        SkSpan<const Segment>
            horizontal{&fSegmentStorage[endOfBegin], endOfHorizontal - endOfBegin};
        SkSpan<const Segment> end{&fSegmentStorage[endOfHorizontal], endOfEnd - endOfHorizontal};
        return Event{y, begin, horizontal, end};
    }
 
    Iterator begin() const {
        return Iterator{*this, 0};
    }
 
    Iterator end() const {
        return Iterator{*this, fEvents.size()};
    }
 
    size_t size() const {
        return fEvents.size();
    }
 
    bool empty() const {
        return fEvents.empty();
    }
 
private:
    EventQueue(std::vector<CompactEvent>&& events, std::vector<Segment>&& segmentStorage)
            : fEvents{std::move(events)}
            , fSegmentStorage{std::move(segmentStorage)} {}
 
    const std::vector<CompactEvent> fEvents;
    const std::vector<Segment> fSegmentStorage;
};
 
// -- CrossingAccumulator --------------------------------------------------------------------------
// Collect all the crossings, and reject endpoint-to-endpoint crossings as those intersections
// are already represented in the data.
class CrossingAccumulator {
public:
    void recordCrossing(const Segment& s0, const Segment& s1) {
        // Endpoints with no possible interior overlap.
        if (s0.upper() == s1.lower() || s0.lower() == s1.upper()) {
            return;
        }
 
        // Segments don't overlap if they are not collinear.
        if ((s0.upper() == s1.upper() || s0.lower() == s1.lower()) && compare_slopes(s0, s1) != 0) {
            return;
        }
 
        fCrossings.emplace_back(s0, s1);
    }
 
    std::vector<Crossing> finishAndReleaseCrossings() {
        return std::move(fCrossings);
    }
 
private:
    std::vector<Crossing> fCrossings;
};
 
class SweepLine {
    static constexpr Segment kLeftStatusSentinel{{INT32_MIN, INT32_MIN}, {INT32_MIN, INT32_MAX}};
    static constexpr Segment kRightStatusSentinel{{INT32_MAX, INT32_MIN}, {INT32_MAX, INT32_MAX}};
 
public:
    SweepLine() {
        fStatus.push_back(kLeftStatusSentinel);
        fStatus.push_back(kRightStatusSentinel);
    }
 
    void handleEvent(Event e) {
        auto& [y, beginnings, horizontals, endings] = e;
 
        // Things could be out of order from last event.
        this->sortAndRecord(y);
 
        this->handleBeginnings(y, beginnings);
        this->handleHorizontals(y, horizontals);
        this->handleEndings(endings);
    }
 
    std::vector<Crossing> finishAndReleaseCrossings() {
        // Only the sentinels should be left.
        SkASSERT(this->statusEmpty());
        return fCrossings.finishAndReleaseCrossings();
    }
 
private:
    using StatusLine = std::vector<Segment>;
 
    bool statusEmpty() const {
        return fStatus.size() == 2;
    }
 
    // Sort the status line, if items are swapped, then there is a crossing to record.
    void sortAndRecord(int32_t y) {
        // If there are only the sentinels or just 1 segment, then nothing to sort.
        if (fStatus.size() <= 3) {
            return;
        }
 
        // Skip the first and last sentinels.
        for (size_t i = 2; i < fStatus.size() - 1; ++i) {
            const Segment t = fStatus[i];
            size_t j = i;
            for (; j > 1 && s0_less_than_s1_at_y(t, fStatus[j - 1], y); --j) {
                // While t < the thing before it move it down.
                fCrossings.recordCrossing(t, fStatus[j-1]);
                fStatus[j] = fStatus[j-1];
            }
            fStatus[j] = t;
        }
    }
 
    // When inserting a starting point (either a beginning or a horizontal) check the segments to
    // the left and the right checking nearby segments for crossings.
    template <typename CrossingCheck>
    void checkCrossingsLeftAndRight(
            const Segment& segment, StatusLine::iterator insertionPoint, CrossingCheck check) {
 
        // Match to the left using the left sentinel to break the loop.
        for (auto cursor = std::make_reverse_iterator(insertionPoint); check(*cursor); ++cursor) {
            fCrossings.recordCrossing(segment, *cursor);
        }
 
        // Match to the right using the right sentinel to break the loop.
        for (auto cursor = insertionPoint; check(*cursor); ++cursor) {
            fCrossings.recordCrossing(segment, *cursor);
        }
    }
 
    // Add segments that start on y excluding horizontals.
    void handleBeginnings(int32_t y, SkSpan<const Segment> inserting) {
        for (const Segment& s : inserting) {
            auto insertionPoint =
                    std::lower_bound(fStatus.begin(), fStatus.end(), s,
                                     segment_less_than_upper_to_insert);
 
            // Checking intersections left and right checks if the point s.upper() lies on
            // the nearby segment.
            auto checkIntersect = [&](const Segment& toCheck) {
                return compare_point_to_segment(s.upper(), toCheck) == 0;
            };
            this->checkCrossingsLeftAndRight(s, insertionPoint, checkIntersect);
 
            fStatus.insert(insertionPoint, s);
        }
    }
 
    // Horizontals on y are handled by checking for crossings by adding them, and then immediately
    // removing them.
    void handleHorizontals(int32_t y, SkSpan<const Segment> horizontals) {
        for (const Segment& s : horizontals) {
            auto insertionPoint =
                    std::lower_bound(fStatus.begin(), fStatus.end(), s,
                                     segment_less_than_upper_to_insert);
 
            // Check if the nearby segment crosses the horizontal line.
            auto checkIntersection = [&](const Segment& toCheck) {
                return compare_point_to_segment(s.upper(), toCheck) <= 0 &&
                       compare_point_to_segment(s.lower(), toCheck) >= 0;
            };
            this->checkCrossingsLeftAndRight(s, insertionPoint, checkIntersection);
 
            fStatus.insert(insertionPoint, s);
        }
 
        this->handleEndings(horizontals);
    }
 
    // Remove all the segments ending on y.
    void handleEndings(SkSpan<const Segment> removing) {
        for (const Segment& s : removing) {
            auto removedPoint = std::remove(fStatus.begin(), fStatus.end(), s);
            SkASSERT(removedPoint != fStatus.end());
            fStatus.erase(removedPoint, fStatus.end());
        }
    }
 
    StatusLine fStatus;
    CrossingAccumulator fCrossings;
};
 
std::vector<Crossing> myers_find_crossings(const SkSpan<const Segment> segments) {
    const EventQueue eventQueue = EventQueue::Make(segments);
    SweepLine sweepLine;
 
    for (const Event& event : eventQueue) {
        sweepLine.handleEvent(event);
    }
 
    return sweepLine.finishAndReleaseCrossings();
}
 
// This intersection algorithm is from "Robust Plane Sweep for Intersecting Segments" page 10.
bool s0_intersects_s1(const Segment& s0, const Segment& s1) {
    // Make sure that s0 upper is above s1 upper.
    if (s1.upper().y < s0.upper().y
        || ((s1.upper().y == s0.upper().y) && (s1.lower().y > s0.lower().y))) {
 
        // Swap to put in the right orientation.
        return s0_intersects_s1(s1, s0);
    }
 
    SkASSERT(s0.upper().y <= s1.upper().y);
 
    {  // If extents don't overlap then there is no intersection.
        auto [left0, top0, right0, bottom0] = s0.bounds();
        auto [left1, top1, right1, bottom1] = s1.bounds();
        if (right1 < left0 || right0 < left1 || bottom1 < top0 || bottom0 < top1) {
            return false;
        }
    }
 
    auto [u0, l0] = s0;
    auto [u1, l1] = s1;
 
    const Point D0 = l0 - u0,
                D1 = l1 - u1;
 
    // If the vector from u0 to l0 (named D0) and the vector from u0 to u1 have an angle of 0
    // between them, then u1 is on the segment u0 to l0 (named s0).
    const Point U0toU1 = (u1 - u0);
    const int64_t D0xU0toU1 = cross(D0, U0toU1);
    if (D0xU0toU1 == 0) {
        // u1 is on s0.
        return true;
    }
 
    if (l1.y <= l0.y) {
        // S1 is between the upper and lower points of S0.
        const Point U0toL1 = (l1 - u0);
        const int64_t D0xU0toL1 = cross(D0, U0toL1);
        if (D0xU0toL1 == 0) {
            // l1 is on s0.
            return true;
        }
 
        // If U1 and L1 are on opposite sides of D0 then the segments cross.
        return (D0xU0toU1 ^ D0xU0toL1) < 0;
    } else {
        // S1 extends past S0. It could be that S1 crosses the line of S0 (not the bound segment)
        // beyond the endpoints of S0. Make sure that it crosses on the segment and not beyond.
        const Point U1toL0 = (l0 - u1);
        const int64_t D1xU1toL0 = cross(D1, U1toL0);
        if (D1xU1toL0 == 0) {
            return true;
        }
 
        // For D1 to cross D0, then D1 must be on the same side of U1toL0 as D0. D0xU0toU1
        // describes the orientation of U0 compared to D0. The angle from D1 to U1toL0 must
        // have the same direction as the angle from U0toU1 to D0.
        return (D0xU0toU1 ^ D1xU1toL0) >= 0;
    }
}
 
std::vector<Crossing> brute_force_crossings(SkSpan<Segment> segments) {
 
    auto isNonZeroSegment = [](const Segment& segment) {
        return segment.upper() != segment.lower();
    };
    const auto zeroSegments = std::partition(segments.begin(), segments.end(), isNonZeroSegment);
 
    std::sort(segments.begin(), zeroSegments);
 
    const auto duplicateSegments = std::unique(segments.begin(), zeroSegments);
 
    SkSpan<const Segment> cleanSegments =
            SkSpan{segments.data(), std::distance(segments.begin(), duplicateSegments)};
 
    CrossingAccumulator crossings;
    if (cleanSegments.size() >= 2) {
        for (auto i = cleanSegments.begin(); i != std::prev(cleanSegments.end()); ++i) {
            for (auto j = std::next(i); j != cleanSegments.end(); ++j) {
                if (s0_intersects_s1(*i, *j)) {
                    crossings.recordCrossing(*i, *j);
                }
            }
        }
    }
    return crossings.finishAndReleaseCrossings();
}
}  // namespace myers