1 #include <mbgl/tile/geometry_tile_data.hpp>
2 #include <mbgl/tile/tile_id.hpp>
3 
4 #include <mapbox/geometry/wagyu/wagyu.hpp>
5 
6 namespace mbgl {
7 
signedArea(const GeometryCoordinates & ring)8 static double signedArea(const GeometryCoordinates& ring) {
9     double sum = 0;
10 
11     for (std::size_t i = 0, len = ring.size(), j = len - 1; i < len; j = i++) {
12         const GeometryCoordinate& p1 = ring[i];
13         const GeometryCoordinate& p2 = ring[j];
14         sum += (p2.x - p1.x) * (p1.y + p2.y);
15     }
16 
17     return sum;
18 }
19 
toWagyuPath(const GeometryCoordinates & ring)20 static LinearRing<int32_t> toWagyuPath(const GeometryCoordinates& ring) {
21     LinearRing<int32_t> result;
22     result.reserve(ring.size());
23     for (const auto& p : ring) {
24         result.emplace_back(p.x, p.y);
25     }
26     return result;
27 }
28 
toGeometryCollection(MultiPolygon<int16_t> && multipolygon)29 static GeometryCollection toGeometryCollection(MultiPolygon<int16_t>&& multipolygon) {
30     GeometryCollection result;
31     for (auto& polygon : multipolygon) {
32         for (auto& ring : polygon) {
33             result.emplace_back(std::move(ring));
34         }
35     }
36     return result;
37 }
38 
fixupPolygons(const GeometryCollection & rings)39 GeometryCollection fixupPolygons(const GeometryCollection& rings) {
40     using namespace mapbox::geometry::wagyu;
41 
42     wagyu<int32_t> clipper;
43 
44     for (const auto& ring : rings) {
45         clipper.add_ring(toWagyuPath(ring));
46     }
47 
48     MultiPolygon<int16_t> multipolygon;
49     clipper.execute(clip_type_union, multipolygon, fill_type_even_odd, fill_type_even_odd);
50 
51     return toGeometryCollection(std::move(multipolygon));
52 }
53 
classifyRings(const GeometryCollection & rings)54 std::vector<GeometryCollection> classifyRings(const GeometryCollection& rings) {
55     std::vector<GeometryCollection> polygons;
56 
57     std::size_t len = rings.size();
58 
59     if (len <= 1) {
60         polygons.push_back(rings);
61         return polygons;
62     }
63 
64     GeometryCollection polygon;
65     int8_t ccw = 0;
66 
67     for (std::size_t i = 0; i < len; i++) {
68         double area = signedArea(rings[i]);
69 
70         if (area == 0)
71             continue;
72 
73         if (ccw == 0)
74             ccw = (area < 0 ? -1 : 1);
75 
76         if (ccw == (area < 0 ? -1 : 1) && !polygon.empty()) {
77             polygons.push_back(polygon);
78             polygon.clear();
79         }
80 
81         polygon.push_back(rings[i]);
82     }
83 
84     if (!polygon.empty())
85         polygons.push_back(polygon);
86 
87     return polygons;
88 }
89 
limitHoles(GeometryCollection & polygon,uint32_t maxHoles)90 void limitHoles(GeometryCollection& polygon, uint32_t maxHoles) {
91     if (polygon.size() > 1 + maxHoles) {
92         std::nth_element(polygon.begin() + 1,
93                          polygon.begin() + 1 + maxHoles,
94                          polygon.end(),
95                          [] (const auto& a, const auto& b) {
96                              return std::fabs(signedArea(a)) > std::fabs(signedArea(b));
97                          });
98         polygon.resize(1 + maxHoles);
99     }
100 }
101 
convertGeometry(const GeometryTileFeature & geometryTileFeature,const CanonicalTileID & tileID)102 static Feature::geometry_type convertGeometry(const GeometryTileFeature& geometryTileFeature, const CanonicalTileID& tileID) {
103     const double size = util::EXTENT * std::pow(2, tileID.z);
104     const double x0 = util::EXTENT * tileID.x;
105     const double y0 = util::EXTENT * tileID.y;
106 
107     auto tileCoordinatesToLatLng = [&] (const Point<int16_t>& p) {
108         double y2 = 180 - (p.y + y0) * 360 / size;
109         return Point<double>(
110             (p.x + x0) * 360 / size - 180,
111             360.0 / M_PI * std::atan(std::exp(y2 * M_PI / 180)) - 90.0
112         );
113     };
114 
115     GeometryCollection geometries = geometryTileFeature.getGeometries();
116 
117     switch (geometryTileFeature.getType()) {
118         case FeatureType::Unknown: {
119             assert(false);
120             return Point<double>(NAN, NAN);
121         }
122 
123         case FeatureType::Point: {
124             MultiPoint<double> multiPoint;
125             for (const auto& p : geometries.at(0)) {
126                 multiPoint.push_back(tileCoordinatesToLatLng(p));
127             }
128             if (multiPoint.size() == 1) {
129                 return multiPoint[0];
130             } else {
131                 return multiPoint;
132             }
133         }
134 
135         case FeatureType::LineString: {
136             MultiLineString<double> multiLineString;
137             for (const auto& g : geometries) {
138                 LineString<double> lineString;
139                 for (const auto& p : g) {
140                     lineString.push_back(tileCoordinatesToLatLng(p));
141                 }
142                 multiLineString.push_back(std::move(lineString));
143             }
144             if (multiLineString.size() == 1) {
145                 return multiLineString[0];
146             } else {
147                 return multiLineString;
148             }
149         }
150 
151         case FeatureType::Polygon: {
152             MultiPolygon<double> multiPolygon;
153             for (const auto& pg : classifyRings(geometries)) {
154                 Polygon<double> polygon;
155                 for (const auto& r : pg) {
156                     LinearRing<double> linearRing;
157                     for (const auto& p : r) {
158                         linearRing.push_back(tileCoordinatesToLatLng(p));
159                     }
160                     polygon.push_back(std::move(linearRing));
161                 }
162                 multiPolygon.push_back(std::move(polygon));
163             }
164             if (multiPolygon.size() == 1) {
165                 return multiPolygon[0];
166             } else {
167                 return multiPolygon;
168             }
169         }
170     }
171 
172     // Unreachable, but placate GCC.
173     return Point<double>();
174 }
175 
convertFeature(const GeometryTileFeature & geometryTileFeature,const CanonicalTileID & tileID)176 Feature convertFeature(const GeometryTileFeature& geometryTileFeature, const CanonicalTileID& tileID) {
177     Feature feature { convertGeometry(geometryTileFeature, tileID) };
178     feature.properties = geometryTileFeature.getProperties();
179     feature.id = geometryTileFeature.getID();
180     return feature;
181 }
182 
183 } // namespace mbgl
184