1 #pragma once
2 
3 #include <mapbox/geometry/box.hpp>
4 #include <mapbox/geometry/multi_polygon.hpp>
5 #include <mapbox/geometry/polygon.hpp>
6 #include <mapbox/geometry/wagyu/wagyu.hpp>
7 
8 namespace mapbox {
9 namespace geometry {
10 namespace wagyu {
11 namespace quick_clip {
12 
13 template <typename T>
intersect(mapbox::geometry::point<T> a,mapbox::geometry::point<T> b,size_t edge,mapbox::geometry::box<T> const & box)14 mapbox::geometry::point<T> intersect(mapbox::geometry::point<T> a,
15                                      mapbox::geometry::point<T> b,
16                                      size_t edge,
17                                      mapbox::geometry::box<T> const& box) {
18     switch (edge) {
19     case 0:
20         return mapbox::geometry::point<T>(
21             mapbox::geometry::wagyu::wround<T>(static_cast<double>(a.x) + static_cast<double>(b.x - a.x) *
22                                                                               static_cast<double>(box.min.y - a.y) /
23                                                                               static_cast<double>(b.y - a.y)),
24             box.min.y);
25 
26     case 1:
27         return mapbox::geometry::point<T>(
28             box.max.x,
29             mapbox::geometry::wagyu::wround<T>(static_cast<double>(a.y) + static_cast<double>(b.y - a.y) *
30                                                                               static_cast<double>(box.max.x - a.x) /
31                                                                               static_cast<double>(b.x - a.x)));
32 
33     case 2:
34         return mapbox::geometry::point<T>(
35             mapbox::geometry::wagyu::wround<T>(static_cast<double>(a.x) + static_cast<double>(b.x - a.x) *
36                                                                               static_cast<double>(box.max.y - a.y) /
37                                                                               static_cast<double>(b.y - a.y)),
38             box.max.y);
39 
40     default: // case 3
41         return mapbox::geometry::point<T>(
42             box.min.x,
43             mapbox::geometry::wagyu::wround<T>(static_cast<double>(a.y) + static_cast<double>(b.y - a.y) *
44                                                                               static_cast<double>(box.min.x - a.x) /
45                                                                               static_cast<double>(b.x - a.x)));
46     }
47 }
48 
49 template <typename T>
inside(mapbox::geometry::point<T> p,size_t edge,mapbox::geometry::box<T> const & b)50 bool inside(mapbox::geometry::point<T> p, size_t edge, mapbox::geometry::box<T> const& b) {
51     switch (edge) {
52     case 0:
53         return p.y > b.min.y;
54 
55     case 1:
56         return p.x < b.max.x;
57 
58     case 2:
59         return p.y < b.max.y;
60 
61     default: // case 3
62         return p.x > b.min.x;
63     }
64 }
65 
66 template <typename T>
quick_lr_clip(mapbox::geometry::linear_ring<T> const & ring,mapbox::geometry::box<T> const & b)67 mapbox::geometry::linear_ring<T> quick_lr_clip(mapbox::geometry::linear_ring<T> const& ring,
68                                                mapbox::geometry::box<T> const& b) {
69     mapbox::geometry::linear_ring<T> out = ring;
70 
71     for (size_t edge = 0; edge < 4; edge++) {
72         if (out.size() > 0) {
73             mapbox::geometry::linear_ring<T> in = out;
74             mapbox::geometry::point<T> S = in[in.size() - 1];
75             out.resize(0);
76 
77             for (size_t e = 0; e < in.size(); e++) {
78                 mapbox::geometry::point<T> E = in[e];
79 
80                 if (inside(E, edge, b)) {
81                     if (!inside(S, edge, b)) {
82                         out.push_back(intersect(S, E, edge, b));
83                     }
84                     out.push_back(E);
85                 } else if (inside(S, edge, b)) {
86                     out.push_back(intersect(S, E, edge, b));
87                 }
88 
89                 S = E;
90             }
91         }
92     }
93 
94     if (out.size() < 3) {
95         out.clear();
96         return out;
97     }
98     // Close the ring if the first/last point was outside
99     if (out[0] != out[out.size() - 1]) {
100         out.push_back(out[0]);
101     }
102     return out;
103 }
104 } // namespace quick_clip
105 
106 template <typename T>
107 mapbox::geometry::multi_polygon<T>
clip(mapbox::geometry::polygon<T> const & poly,mapbox::geometry::box<T> const & b,fill_type subject_fill_type)108 clip(mapbox::geometry::polygon<T> const& poly, mapbox::geometry::box<T> const& b, fill_type subject_fill_type) {
109     mapbox::geometry::multi_polygon<T> result;
110     wagyu<T> clipper;
111     for (auto const& lr : poly) {
112         auto new_lr = quick_clip::quick_lr_clip(lr, b);
113         if (!new_lr.empty()) {
114             clipper.add_ring(new_lr, polygon_type_subject);
115         }
116     }
117     clipper.execute(clip_type_union, result, subject_fill_type, fill_type_even_odd);
118     return result;
119 }
120 
121 template <typename T>
122 mapbox::geometry::multi_polygon<T>
clip(mapbox::geometry::multi_polygon<T> const & mp,mapbox::geometry::box<T> const & b,fill_type subject_fill_type)123 clip(mapbox::geometry::multi_polygon<T> const& mp, mapbox::geometry::box<T> const& b, fill_type subject_fill_type) {
124     mapbox::geometry::multi_polygon<T> result;
125     wagyu<T> clipper;
126     for (auto const& poly : mp) {
127         for (auto const& lr : poly) {
128             auto new_lr = quick_clip::quick_lr_clip(lr, b);
129             if (!new_lr.empty()) {
130                 clipper.add_ring(new_lr, polygon_type_subject);
131             }
132         }
133     }
134     clipper.execute(clip_type_union, result, subject_fill_type, fill_type_even_odd);
135     return result;
136 }
137 } // namespace wagyu
138 } // namespace geometry
139 } // namespace mapbox
140