myers Namespace Reference

Classes
class	Crossing
class	CrossingAccumulator
struct	Event
class	EventQueue
struct	Point
class	Segment
class	SweepLine

Functions
constexpr bool	operator< (const Point &p0, const Point &p1)
constexpr bool	operator== (const Point &p0, const Point &p1)
constexpr bool	operator!= (const Point &p0, const Point &p1)
constexpr bool	operator< (const Segment &s0, const Segment &s1)
constexpr bool	operator== (const Segment &s0, const Segment &s1)
constexpr bool	operator!= (const Segment &s0, const Segment &s1)
template<size_t >
const myers::Point &	get (const myers::Segment &)
template<>
const myers::Point &	get< 0 > (const myers::Segment &s)
template<>
const myers::Point &	get< 1 > (const myers::Segment &s)
bool	operator< (const Crossing &c0, const Crossing &c1)
bool	operator== (const Crossing &c0, const Crossing &c1)
std::vector< Crossing >	myers_find_crossings (const SkSpan< const Segment > segments)
std::vector< Crossing >	brute_force_crossings (SkSpan< Segment >)
Point	operator- (const Point &p0, const Point &p1)
std::tuple< int64_t, int64_t >	point_to_s64 (Point p)
int64_t	cross (Point d0, Point d1)
int64_t	compare_slopes (const Segment &s0, const Segment &s1)
bool	slope_s0_less_than_slope_s1 (const Segment &s0, const Segment &s1)
int64_t	compare_point_to_segment (Point p, const Segment &s)
bool	segment_less_than_upper_to_insert (const Segment &segment, const Segment &to_insert)
bool	s0_less_than_s1_at_y (const Segment &s0, const Segment &s1, int32_t y)
bool	s0_intersects_s1 (const Segment &s0, const Segment &s1)

Function Documentation

brute_force_crossings()

std::vector< Crossing > myers::brute_force_crossings

(

SkSpan< Segment >

segments

)

Definition at line 638 of file Myers.cpp.

                                                                    {
 
    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();
}

compare_point_to_segment()

int64_t myers::compare_point_to_segment	(	Point	p,
		const Segment &	s
	)

Definition at line 117 of file Myers.cpp.

                                                            {
    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);
}

compare_slopes()

int64_t myers::compare_slopes	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 67 of file Myers.cpp.

                                                             {
    // 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);
}

cross()

int64_t myers::cross	(	Point	d0,
		Point	d1
	)

Definition at line 55 of file Myers.cpp.

                                  {
    const auto [d0x, d0y] = point_to_s64(d0);
    const auto [d1x, d1y] = point_to_s64(d1);
    return d0x * d1y - d1x * d0y;
}

get()

template<size_t >

const myers::Point & myers::get

(

const myers::Segment &

)

get< 0 >()

template<>

const myers::Point & myers::get< 0 > ( const myers::Segment &  s )

inline

Definition at line 80 of file Myers.h.

{ return s.upper(); }

get< 1 >()

template<>

const myers::Point & myers::get< 1 > ( const myers::Segment &  s )

inline

Definition at line 81 of file Myers.h.

{ return s.lower(); }

myers_find_crossings()

std::vector< Crossing > myers::myers_find_crossings

(

const SkSpan< const Segment >

segments

)

Definition at line 565 of file Myers.cpp.

                                                                               {
    const EventQueue eventQueue = EventQueue::Make(segments);
    SweepLine sweepLine;
 
    for (const Event& event : eventQueue) {
        sweepLine.handleEvent(event);
    }
 
    return sweepLine.finishAndReleaseCrossings();
}

operator!=() [1/2]

constexpr bool myers::operator!= ( const Point &  p0, const Point &  p1  )

constexpr

Definition at line 33 of file Myers.h.

                                                            {
    return std::tie(p0.x, p0.y) != std::tie(p1.x, p1.y);
}

operator!=() [2/2]

constexpr bool myers::operator!= ( const Segment &  s0, const Segment &  s1  )

constexpr

Definition at line 74 of file Myers.h.

                                                                {
    return std::tie(s0.fUpper, s0.fLower) != std::tie(s1.fUpper, s1.fLower);
}

operator-()

Point myers::operator-	(	const Point &	p0,
		const Point &	p1
	)

Definition at line 22 of file Myers.cpp.

                                                  {
    return {p0.x - p1.x, p0.y - p1.y};
}

operator<() [1/3]

bool myers::operator< ( const Crossing &  c0, const Crossing &  c1  )

inline

Definition at line 99 of file Myers.h.

                                                              {
    return std::tie(c0.fHigher, c0.fLower) < std::tie(c1.fHigher, c1.fLower);
}

operator<() [2/3]

constexpr bool myers::operator< ( const Point &  p0, const Point &  p1  )

constexpr

Definition at line 25 of file Myers.h.

                                                           {
    return std::tie(p0.y, p0.x) < std::tie(p1.y, p1.x);
}

operator<() [3/3]

constexpr bool myers::operator< ( const Segment &  s0, const Segment &  s1  )

constexpr

Definition at line 66 of file Myers.h.

                                                               {
    return std::tie(s0.fUpper, s0.fLower) < std::tie(s1.fUpper, s1.fLower);
}

operator==() [1/3]

bool myers::operator== ( const Crossing &  c0, const Crossing &  c1  )

inline

Definition at line 103 of file Myers.h.

                                                               {
    return std::tie(c0.fHigher, c0.fLower) == std::tie(c1.fHigher, c1.fLower);
}

operator==() [2/3]

constexpr bool myers::operator== ( const Point &  p0, const Point &  p1  )

constexpr

Definition at line 29 of file Myers.h.

                                                            {
    return std::tie(p0.x, p0.y) == std::tie(p1.x, p1.y);
}

operator==() [3/3]

constexpr bool myers::operator== ( const Segment &  s0, const Segment &  s1  )

constexpr

Definition at line 70 of file Myers.h.

                                                                {
    return std::tie(s0.fUpper, s0.fLower) == std::tie(s1.fUpper, s1.fLower);
}

point_to_s64()

std::tuple< int64_t, int64_t > myers::point_to_s64

(

Point

p

)

Definition at line 26 of file Myers.cpp.

                                                 {
    return std::make_tuple(SkToS64(p.x), SkToS64(p.y));
}

s0_intersects_s1()

bool myers::s0_intersects_s1	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 577 of file Myers.cpp.

                                                            {
    // 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;
    }
}

s0_less_than_s1_at_y()

bool myers::s0_less_than_s1_at_y	(	const Segment &	s0,
		const Segment &	s1,
		int32_t	y
	)

Definition at line 166 of file Myers.cpp.

                                                                           {
    // 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));
}

segment_less_than_upper_to_insert()

bool myers::segment_less_than_upper_to_insert	(	const Segment &	segment,
		const Segment &	to_insert
	)

Definition at line 158 of file Myers.cpp.

                                                                                         {
    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));
}

slope_s0_less_than_slope_s1()

bool myers::slope_s0_less_than_slope_s1	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 109 of file Myers.cpp.

                                                                       {
    return compare_slopes(s0, s1) < 0;
}