bentleyottmann Namespace Reference

Classes
struct	Cross
struct	Crossing
struct	Event
class	EventQueue
class	EventQueueInterface
class	EventQueueTestingPeer
struct	Int96
struct	Lower
struct	OrderBySlope
struct	Point
struct	Segment
class	SweepLine
class	SweepLineInterface
struct	SweepLineTestingPeer
struct	Upper
struct	Visitor

Typedefs
using	EventType = std::variant< Lower, Cross, Upper >
using	DeletionSegmentSet = std::set< Segment >
using	InsertionSegmentSet = std::set< Segment, OrderBySlope >

Functions
std::optional< std::vector< Crossing > >	bentley_ottmann_1 (SkSpan< const Segment > segments)
std::optional< std::vector< Crossing > >	brute_force_crossings (SkSpan< const Segment > segments)
bool	operator== (const Int96 &a, const Int96 &b)
bool	operator< (const Int96 &a, const Int96 &b)
Int96	operator+ (const Int96 &a, const Int96 &b)
Int96	multiply (int64_t a, int32_t b)
Int96	multiply (int32_t a, int64_t b)
bool	operator== (const Segment &s0, const Segment &s1)
bool	operator< (const Segment &s0, const Segment &s1)
bool	no_intersection_by_bounding_box (const Segment &s0, const Segment &s1)
std::optional< Point >	intersect (const Segment &s0, const Segment &s1)
bool	less_than_at (const Segment &s0, const Segment &s1, int32_t y)
bool	point_less_than_segment_in_x (Point p, const Segment &segment)
bool	rounded_point_less_than_segment_in_x_lower (const Segment &s, Point p)
bool	rounded_point_less_than_segment_in_x_upper (const Segment &s, Point p)
int	compare_slopes (const Segment &s0, const Segment &s1)
template<class... Ts>
	Visitor (Ts...) -> Visitor< Ts... >
bool	operator< (const Point &p0, const Point &p1)
bool	operator> (const Point &p0, const Point &p1)
bool	operator>= (const Point &p0, const Point &p1)
bool	operator<= (const Point &p0, const Point &p1)
bool	operator== (const Point &p0, const Point &p1)
bool	operator!= (const Point &p0, const Point &p1)

Typedef Documentation

DeletionSegmentSet

using bentleyottmann::DeletionSegmentSet = typedef std::set<Segment>

Definition at line 31 of file EventQueueInterface.h.

EventType

using bentleyottmann::EventType = typedef std::variant<Lower, Cross, Upper>

Definition at line 47 of file EventQueue.h.

InsertionSegmentSet

using bentleyottmann::InsertionSegmentSet = typedef std::set<Segment, OrderBySlope>

Definition at line 38 of file EventQueueInterface.h.

Function Documentation

bentley_ottmann_1()

std::optional< std::vector< Crossing > > bentleyottmann::bentley_ottmann_1

(

SkSpan< const Segment >

segments

)

Definition at line 16 of file BentleyOttmann1.cpp.

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

brute_force_crossings()

std::optional< std::vector< Crossing > > bentleyottmann::brute_force_crossings

(

SkSpan< const Segment >

segments

)

Definition at line 12 of file BruteForceCrossings.cpp.

                                                                                       {
    std::vector<Crossing> answer;
    if (segments.size() >= 2) {
        for (auto i0 = segments.begin(); i0 != segments.end() - 1; ++i0) {
            for (auto i1 = i0 + 1; i1 != segments.end(); ++i1) {
                if (auto possiblePoint = intersect(*i0, *i1)) {
                    answer.push_back({*i0, *i1, possiblePoint.value()});
                }
            }
        }
    }
    return answer;
}

compare_slopes()

int bentleyottmann::compare_slopes	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 329 of file Segment.cpp.

                                                         {
    Point s0Delta = s0.lower() - s0.upper(),
          s1Delta = s1.lower() - s1.upper();
 
    // Handle the horizontal cases to avoid dealing with infinities.
    if (s0Delta.y == 0 || s1Delta.y == 0) {
        if (s0Delta.y != 0) {
            return -1;
        } else if (s1Delta.y != 0) {
            return 1;
        } else {
            return 0;
        }
    }
 
    // Compare s0Delta.x / s0Delta.y ? s1Delta.x / s1Delta.y. I used the alternate slope form for
    // two reasons.
    // * no change of sign - since the delta ys are always positive, then I don't need to worry
    //                       about the change in sign with the cross-multiply.
    // * proper slope ordering - the slope monotonically increases from the smallest along the
    //                           negative x-axis increasing counterclockwise to the largest along
    //                           the positive x-axis.
    int64_t lhs = SkToS64(s0Delta.x) * SkToS64(s1Delta.y),
            rhs = SkToS64(s1Delta.x) * SkToS64(s0Delta.y);
 
    if (lhs < rhs) {
        return -1;
    } else if (lhs > rhs) {
        return 1;
    } else {
        return 0;
    }
}

intersect()

std::optional< Point > bentleyottmann::intersect	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 97 of file Segment.cpp.

                                                                   {
 
    // Check if the bounds intersect.
    if (no_intersection_by_bounding_box(s0, s1)) {
        return std::nullopt;
    }
 
    // Create the end Points for s0 and s1
    const Point P0 = s0.upper(),
                P1 = s0.lower(),
                P2 = s1.upper(),
                P3 = s1.lower();
 
    if (P0 == P2 || P1 == P3 || P1 == P2 || P3 == P0) {
        // Lines don't intersect if they share an end point.
        return std::nullopt;
    }
 
    // Create the Q, R, and T.
    const Point Q = P1 - P0,
                R = P2 - P0,
                T = P3 - P2;
 
    // 64-bit cross product.
    auto cross = [](const Point& v0, const Point& v1) {
        int64_t x0 = SkToS64(v0.x),
                y0 = SkToS64(v0.y),
                x1 = SkToS64(v1.x),
                y1 = SkToS64(v1.y);
        return x0 * y1 - y0 * x1;
    };
 
    // Calculate the cross products needed for calculating s and t.
    const int64_t QxR = cross(Q, R),
                  TxR = cross(T, R),
                  TxQ = cross(T, Q);
 
    if (TxQ == 0) {
        // Both t and s are either < 0 or > 1 because the denominator is 0.
        return std::nullopt;
    }
 
    // t = (Q x R) / (T x Q). s = (T x R) / (T x Q). Check that t & s are on [0, 1]
    if ((QxR ^ TxQ) < 0 || (TxR ^ TxQ) < 0) {
        // The division is negative and t or s < 0.
        return std::nullopt;
    }
 
    if (TxQ > 0) {
        if (QxR > TxQ || TxR > TxQ) {
            // t or s is greater than 1.
            return std::nullopt;
        }
    } else {
        if (QxR < TxQ || TxR < TxQ) {
            // t or s is greater than 1.
            return std::nullopt;
        }
    }
 
    // Calculate the intersection using doubles.
    // TODO: This is just a placeholder approximation for calculating x and y should use big math
    // above.
    const double t = static_cast<double>(QxR) / static_cast<double>(TxQ);
    SkASSERT(0 <= t && t <= 1);
    const int32_t x = std::round(t * (P3.x - P2.x) + P2.x),
                  y = std::round(t * (P3.y - P2.y) + P2.y);
 
    return Point{x, y};
}

less_than_at()

bool bentleyottmann::less_than_at	(	const Segment &	s0,
		const Segment &	s1,
		int32_t	y
	)

Definition at line 178 of file Segment.cpp.

                                                                   {
    auto [l0, t0, r0, b0] = s0.bounds();
    auto [l1, t1, r1, b1] = s1.bounds();
    SkASSERT(t0 <= y && y <= b0);
    SkASSERT(t1 <= y && y <= b1);
 
    // Return true if the bounding box of s0 is fully to the left of s1.
    if (r0 < l1) {
        return true;
    }
 
    // Return false if the bounding box of s0 is fully to the right of s1.
    if (r1 < l0) {
        return false;
    }
 
    // Check the x intercepts along the horizontal line at y.
    // Make s0 be (x0, y0) -> (x1, y1) and s1 be (x2, y2) -> (x3, y3).
    auto [x0, y0] = s0.upper();
    auto [x1, y1] = s0.lower();
    auto [x2, y2] = s1.upper();
    auto [x3, y3] = s1.lower();
 
    int64_t s0YDiff = y - y0,
            s1YDiff = y - y2,
            s0YDelta = y1 - y0,
            s1YDelta = y3 - y2,
            x0Offset = x0 * s0YDelta + s0YDiff * (x1 - x0),
            x2Offset = x2 * s1YDelta + s1YDiff * (x3 - x2);
 
    Int96 s0Factor = multiply(x0Offset, y3 - y2),
          s1Factor = multiply(x2Offset, y1 - y0);
 
    return s0Factor < s1Factor;
}

multiply() [1/2]

Int96 bentleyottmann::multiply	(	int32_t	a,
		int64_t	b
	)

Definition at line 65 of file Int96.cpp.

                                     {
    return multiply(b, a);
}

multiply() [2/2]

Int96 bentleyottmann::multiply	(	int64_t	a,
		int32_t	b
	)

Definition at line 41 of file Int96.cpp.

                                     {
    // Multiply the low 32-bits generating a 64-bit lower part.
    uint64_t loA = a & 0xFFFFFFFF;
    uint64_t loB = (uint32_t)b;
    uint64_t newLo = loA * loB;
 
    // Multiply the upper bits 32-bits of a and b resulting in the hi 64-bits of the Int96.
    int64_t newHi = (a >> 32) * (int64_t)b;
 
    // Calculate the overflow into the upper 32-bits.
    // Remember that newLo is unsigned so will be zero filled by the shift.
    int64_t lowOverflow = newLo >> 32;
 
    // Add overflow from the low multiply into hi.
    newHi += lowOverflow;
 
    // Compensate for the negative b in the calculation of newLo by subtracting out 2^32 * a.
    if (b < 0) {
        newHi -= loA;
    }
 
    return {newHi, (uint32_t)newLo};
}

no_intersection_by_bounding_box()

bool bentleyottmann::no_intersection_by_bounding_box	(	const Segment &	s0,
		const Segment &	s1
	)

Definition at line 39 of file Segment.cpp.

                                                                           {
    auto [left0, top0, right0, bottom0] = s0.bounds();
    auto [left1, top1, right1, bottom1] = s1.bounds();
    // If the sides of the box touch, then there is no new intersection.
    return right0 <= left1 || right1 <= left0 || bottom0 <= top1 || bottom1 <= top0;
}

operator!=()

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

Definition at line 32 of file Point.cpp.

                                                  {
    return !(p0 == p1);
}

operator+()

Int96 bentleyottmann::operator+	(	const Int96 &	a,
		const Int96 &	b
	)

Definition at line 27 of file Int96.cpp.

                                                 {
    uint32_t lo = a.lo + b.lo;
    int64_t carry = lo < a.lo;
    int64_t hi = a.hi + b.hi + carry;
    return {hi, lo};
}

operator<() [1/3]

bool bentleyottmann::operator<	(	const Int96 &	a,
		const Int96 &	b
	)

Definition at line 23 of file Int96.cpp.

                                                {
    return std::tie(a.hi, a.lo) < std::tie(b.hi, b.lo);
}

operator<() [2/3]

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

Definition at line 12 of file Point.cpp.

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

operator<() [3/3]

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

Definition at line 35 of file Segment.cpp.

                                                     {
    return std::make_tuple(s0.upper(), s0.lower()) < std::make_tuple(s1.upper(), s1.lower());
}

operator<=()

bool bentleyottmann::operator<=	(	const Point &	p0,
		const Point &	p1
	)

Definition at line 24 of file Point.cpp.

                                                  {
    return !(p0 > p1);
}

operator==() [1/3]

bool bentleyottmann::operator==	(	const Int96 &	a,
		const Int96 &	b
	)

Definition at line 19 of file Int96.cpp.

                                                 {
    return std::tie(a.hi, a.lo) == std::tie(b.hi, b.lo);
}

operator==() [2/3]

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

Definition at line 28 of file Point.cpp.

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

operator==() [3/3]

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

Definition at line 31 of file Segment.cpp.

                                                      {
    return s0.upper() == s1.upper() && s0.lower() == s1.lower();
}

operator>()

bool bentleyottmann::operator>	(	const Point &	p0,
		const Point &	p1
	)

Definition at line 16 of file Point.cpp.

                                                 {
    return p1 < p0;
}

operator>=()

bool bentleyottmann::operator>=	(	const Point &	p0,
		const Point &	p1
	)

Definition at line 20 of file Point.cpp.

                                                  {
    return !(p0 < p1);
}

point_less_than_segment_in_x()

bool bentleyottmann::point_less_than_segment_in_x	(	Point	p,
		const Segment &	segment
	)

Definition at line 214 of file Segment.cpp.

                                                                   {
    auto [l, t, r, b] = segment.bounds();
 
    // Ensure that the segment intersects the horizontal sweep line
    SkASSERT(t <= p.y && p.y <= b);
 
    // Fast answers using bounding boxes.
    if (p.x < l) {
        return true;
    } else if (p.x >= r) {
        return false;
    }
 
    auto [x0, y0] = segment.upper();
    auto [x1, y1] = segment.lower();
    auto [x2, y2] = p;
 
    // For a point and a segment the comparison is:
    //    x2 < x0 + (y2 - y0)(x1 - x0) / (y1 - y0)
    // becomes
    //    (x2 - x0)(y1 - y0) < (x1 - x0)(y2 - y0)
    // We don't need to worry about the signs changing in the cross multiply because (y1 - y0) is
    // always positive. Manipulating a little further derives predicate 2 from "Robust Plane
    // Sweep for Intersecting Segments" page 9.
    //    0 < (x1 - x0)(y2 - y0) - (x2 - x0)(y1 - y0)
    // becomes
    //        | x1-x0   x2-x0 |
    //   0 <  | y1-y0   y2-y0 |
    return SkToS64(x2 - x0) * SkToS64(y1 - y0) < SkToS64(y2 - y0) * SkToS64(x1 - x0);
}

rounded_point_less_than_segment_in_x_lower()

bool bentleyottmann::rounded_point_less_than_segment_in_x_lower	(	const Segment &	s,
		Point	p
	)

Definition at line 248 of file Segment.cpp.

                                                                           {
    const auto [l, t, r, b] = s.bounds();
    const auto [x, y] = p;
 
    // Ensure that the segment intersects the horizontal sweep line
    SkASSERT(t <= y && y <= b);
 
    // In the comparisons below, x is really x - ½
    if (r < x) {
        // s is entirely < p.
        return true;
    } else if (x <= l) {
        // s is entirely > p. This also handles vertical lines, so we don't have to handle them
        // below.
        return false;
    }
 
    const auto [x0, y0] = s.upper();
    const auto [x1, y1] = s.lower();
 
    // Horizontal - from the guards above we know that p is on s.
    if (y0 == y1) {
        return false;
    }
 
    // s is not horizontal or vertical.
    SkASSERT(x0 != x1 && y0 != y1);
 
    // Given the segment upper = (x0, y0) and lower = (x1, y1)
    // x0 + (x1 - x0)(y - y0) / (y1 - y0) < x - ½
    // (x1 - x0)(y - y0) / (y1 - y0) < x - x0 - ½
    // Because (y1 - y0) is always positive we can multiply through the inequality without
    // worrying about sign changes.
    // (x1 - x0)(y - y0) < (x - x0 - ½)(y1 - y0)
    // (x1 - x0)(y - y0) < ½(2x - 2x0 - 1)(y1 - y0)
    // 2(x1 - x0)(y - y0) < (2(x - x0) - 1)(y1 - y0)
    return 2 * SkToS64(x1 - x0) * SkToS64(y - y0) < (2 * SkToS64(x - x0) - 1) * SkToS64(y1 - y0);
}

rounded_point_less_than_segment_in_x_upper()

bool bentleyottmann::rounded_point_less_than_segment_in_x_upper	(	const Segment &	s,
		Point	p
	)

Definition at line 290 of file Segment.cpp.

                                                                           {
    const auto [l, t, r, b] = s.bounds();
    const auto [x, y] = p;
 
    // Ensure that the segment intersects the horizontal sweep line
    SkASSERT(t <= y && y <= b);
 
    // In the comparisons below, x is really x + ½
    if (r <= x) {
        // s is entirely < p.
        return true;
    } else if (x < l) {
        // s is entirely > p. This also handles vertical lines, so we don't have to handle them
        // below.
        return false;
    }
 
    const auto [x0, y0] = s.upper();
    const auto [x1, y1] = s.lower();
 
    // Horizontal - from the guards above we know that p is on s.
    if (y0 == y1) {
        return false;
    }
 
    // s is not horizontal or vertical.
    SkASSERT(x0 != x1 && y0 != y1);
 
    // Given the segment upper = (x0, y0) and lower = (x1, y1)
    // x0 + (x1 - x0)(y - y0) / (y1 - y0) < x + ½
    // (x1 - x0)(y - y0) / (y1 - y0) < x - x0 + ½
    // Because (y1 - y0) is always positive we can multiply through the inequality without
    // worrying about sign changes.
    // (x1 - x0)(y - y0) < (x - x0 + ½)(y1 - y0)
    // (x1 - x0)(y - y0) < ½(2x - 2x0 + 1)(y1 - y0)
    // 2(x1 - x0)(y - y0) < (2(x - x0) + 1)(y1 - y0)
    return 2 * SkToS64(x1 - x0) * SkToS64(y - y0) < (2 * SkToS64(x - x0) + 1) * SkToS64(y1 - y0);
}

Visitor()

template<class... Ts>

bentleyottmann::Visitor

(

Ts...

)

-> Visitor< Ts... >