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 Myers_DEFINED 5 #define Myers_DEFINED 6 7 #include "include/core/SkSpan.h" 8 #include "include/private/base/SkAssert.h" 9 10 #include <algorithm> 11 #include <cstddef> 12 #include <cstdint> 13 #include <tuple> 14 #include <vector> 15 16 namespace myers { 17 18 // -- Point ---------------------------------------------------------------------------------------- 19 struct Point { 20 int32_t x = 0; 21 int32_t y = 0; 22 }; 23 24 // Return p0 and p1 in the correct order for a Segment. 25 constexpr bool operator<(const Point& p0, const Point& p1) { 26 return std::tie(p0.y, p0.x) < std::tie(p1.y, p1.x); 27 } 28 29 constexpr bool operator==(const Point& p0, const Point& p1) { 30 return std::tie(p0.x, p0.y) == std::tie(p1.x, p1.y); 31 } 32 33 constexpr bool operator!=(const Point& p0, const Point& p1) { 34 return std::tie(p0.x, p0.y) != std::tie(p1.x, p1.y); 35 } 36 37 // -- Segment -------------------------------------------------------------------------------------- 38 // A Segment is an undirected edge where the points have an order u.y < l.y else 39 // if (u.y == l.y) u.x < x.y. 40 class Segment { 41 public: Segment(Point p0,Point p1)42 constexpr Segment(Point p0, Point p1) 43 : Segment{std::minmax(p0, p1)} {} 44 45 const Point& upper() const; 46 const Point& lower() const; 47 std::tuple<int32_t, int32_t, int32_t, int32_t> bounds() const; 48 bool isHorizontal() const; 49 bool isVertical() const; 50 friend constexpr bool operator<(const Segment& s0, const Segment& s1); 51 friend constexpr bool operator==(const Segment& s0, const Segment& s1); 52 friend constexpr bool operator!=(const Segment& s0, const Segment& s1); 53 54 private: Segment(const std::tuple<Point,Point> & ps)55 constexpr Segment(const std::tuple<Point, Point>& ps) 56 : fUpper{std::get<0>(ps)} 57 , fLower{std::get<1>(ps)} { 58 SkASSERT(fUpper != fLower); 59 SkASSERT(fUpper < fLower); 60 } 61 62 Point fUpper; 63 Point fLower; 64 }; 65 66 constexpr bool operator<(const Segment& s0, const Segment& s1) { 67 return std::tie(s0.fUpper, s0.fLower) < std::tie(s1.fUpper, s1.fLower); 68 } 69 70 constexpr bool operator==(const Segment& s0, const Segment& s1) { 71 return std::tie(s0.fUpper, s0.fLower) == std::tie(s1.fUpper, s1.fLower); 72 } 73 74 constexpr bool operator!=(const Segment& s0, const Segment& s1) { 75 return std::tie(s0.fUpper, s0.fLower) != std::tie(s1.fUpper, s1.fLower); 76 } 77 78 // Support for Segment as a tuple. 79 template<size_t> const myers::Point& get(const myers::Segment&); 80 template<> inline const myers::Point& get<0>(const myers::Segment& s) { return s.upper(); } 81 template<> inline const myers::Point& get<1>(const myers::Segment& s) { return s.lower(); } 82 83 // -- Crossing ------------------------------------------------------------------------------------- 84 class Crossing { 85 public: Crossing(const Segment & s0,const Segment & s1)86 Crossing(const Segment& s0, const Segment& s1) : Crossing{std::minmax(s0, s1)} {} 87 friend bool operator<(const Crossing& c0, const Crossing& c1); 88 friend bool operator==(const Crossing& c0, const Crossing& c1); 89 90 private: Crossing(std::tuple<Segment,Segment> highLow)91 Crossing(std::tuple<Segment, Segment> highLow) 92 : fHigher{std::get<0>(highLow)} 93 , fLower{std::get<1>(highLow)} {} 94 95 Segment fHigher; 96 Segment fLower; 97 }; 98 99 inline bool operator<(const Crossing& c0, const Crossing& c1) { 100 return std::tie(c0.fHigher, c0.fLower) < std::tie(c1.fHigher, c1.fLower); 101 } 102 103 inline bool operator==(const Crossing& c0, const Crossing& c1) { 104 return std::tie(c0.fHigher, c0.fLower) == std::tie(c1.fHigher, c1.fLower); 105 } 106 107 std::vector<Crossing> myers_find_crossings(const SkSpan<const Segment> segments); 108 std::vector<Crossing> brute_force_crossings(SkSpan<Segment>); 109 } // namespace myers 110 111 // Support for Segment as a tuple. Must be in top-level namespace. 112 template<> struct std::tuple_size<myers::Segment> { 113 static constexpr int value = 2; 114 }; 115 116 template<size_t Index> struct std::tuple_element<Index, myers::Segment> { 117 using type = const myers::Point&; 118 }; 119 #endif // Myers_DEFINED 120