1 // Copyright 2023 Google LLC 2 // Use of this source code is governed by a BSD-style license that can be found in the LICENSE file. 3 4 #ifndef Segment_DEFINED 5 #define Segment_DEFINED 6 7 #include "modules/bentleyottmann/include/Point.h" 8 9 #include <cstdint> 10 #include <optional> 11 #include <tuple> 12 13 namespace bentleyottmann { 14 15 struct Segment { 16 Point p0; 17 Point p1; 18 19 // Y is larger going down the y-axis. 20 // Get the higher point. It will be left most for horizontal segment. 21 Point upper() const; 22 23 // Get the lower point. It will be the right most for horizontal segment. 24 Point lower() const; 25 26 std::tuple<int32_t, int32_t, int32_t, int32_t> bounds() const; 27 }; 28 29 bool operator==(const Segment& s0, const Segment& s1); 30 bool operator<(const Segment& s0, const Segment& s1); 31 32 struct Crossing { 33 const Segment s0; 34 const Segment s1; 35 const Point crossing; 36 }; 37 38 bool no_intersection_by_bounding_box(const Segment& s0, const Segment& s1); 39 40 // Finds the intersection of s0 and s1. Returns nullopt if there is no intersection. 41 // Note this intersection assumes that line segments do not include their end points. 42 std::optional<Point> intersect(const Segment& s0, const Segment& s1); 43 44 // Compare two segments at the sweep line given by y. 45 // It is an error to pass segments that don't intersect the horizontal line at y. 46 bool less_than_at(const Segment& s0, const Segment& s1, int32_t y); 47 48 // Given a horizontal line defined by p.y, is p.x < the x value where the horizontal line passes 49 // segment. 50 bool point_less_than_segment_in_x(Point p, const Segment& segment); 51 52 // The following two routines are used to find the rounded comparison between a Point p and a 53 // segment s. s(y) is the x value of the segment at y. The rounding definition is: 54 // x < ⌊s(y) + ½⌋ 55 // Expanding the floor operation results in 56 // (x - ½) ≤ s(y) < (x + ½) 57 // The two functions are the two halves of the above inequality. 58 // The rounding lower bound is: (x - ½) ≤ s(y). The ordering of the parameters facilitates using 59 // std::lower_bound. 60 bool rounded_point_less_than_segment_in_x_lower(const Segment& s, Point p); 61 // The rounding upper bound is: s(y) < (x + ½) 62 bool rounded_point_less_than_segment_in_x_upper(const Segment& s, Point p); 63 64 // Compare the slopes of two segments. If a slope is horizontal, then its slope is greater than 65 // all other slopes or equal of the other segment is also horizontal. The slope for 66 // non-horizontal segments monotonically increases from the smallest along the negative x-axis 67 // increasing counterclockwise to the largest along the positive x-axis. 68 // Returns: 69 // * -1 - slope(s0) < slope(s1) 70 // * 0 - slope(s0) == slope(s1) 71 // * 1 - slope(s0) > slope(s1) 72 int compare_slopes(const Segment& s0, const Segment& s1); 73 74 } // namespace bentleyottmann 75 #endif // Segment_DEFINED 76