| 1 |
|
| #include "tesselate.h" |
| 2 |
|
| #include "mapbox/earcut.hpp" |
| 3 |
|
| #include <memory> |
| 4 |
|
| #include <assert.h> |
| 5 |
|
| |
| 6 |
|
| using coord_t = geos::geom::Coordinate; |
| 7 |
|
| |
| 8 |
|
| namespace mapbox { |
| 9 |
|
| namespace util { |
| 10 |
|
| |
| 11 |
|
| template <> |
| 12 |
|
| struct nth<0, coord_t> { |
| 13 |
24 |
| inline static auto get(const coord_t &t) { |
| 14 |
24 |
| return t.x; |
| 15 |
|
| }; |
| 16 |
|
| }; |
| 17 |
|
| template <> |
| 18 |
|
| struct nth<1, coord_t> { |
| 19 |
24 |
| inline static auto get(const coord_t &t) { |
| 20 |
24 |
| return t.y; |
| 21 |
|
| }; |
| 22 |
|
| }; |
| 23 |
|
| |
| 24 |
|
| } // namespace util |
| 25 |
|
| } // namespace mapbox |
| 26 |
|
| |
| 27 |
|
| namespace panda { namespace Geos { |
| 28 |
|
| |
| 29 |
1 |
| geos::geom::GeometryCollection* tesselate(geos::geom::Polygon& input) { |
| 30 |
|
| using seq_holder_t = std::unique_ptr<geos::geom::CoordinateSequence>; |
| 31 |
|
| using result_t = std::vector<geos::geom::Geometry*>; |
| 32 |
|
| using poly_sequence_t = std::vector<coord_t>; |
| 33 |
|
| |
| 34 |
1 |
▶ | auto shell = input.getExteriorRing(); |
Branch: 1 branch
| Branch | True | False | Total |
| auto shell = input.getExteriorRing(); |
1 |
0 |
1 |
|
| 35 |
1 |
▶ | auto shell_coords = seq_holder_t{shell->getCoordinates()}; |
Branch: 1 branch
| Branch | True | False | Total |
| auto shell_coords = seq_holder_t{shell->getCoordinates()}; |
1 |
0 |
1 |
|
| 36 |
1 |
| std::vector<poly_sequence_t> polygon; |
| 37 |
1 |
| poly_sequence_t linearized; |
| 38 |
|
| |
| 39 |
|
| /* outer ring/shell */ |
| 40 |
1 |
▶ | assert(shell_coords->size() > 1); |
Branch: 2 branches
| Branch | True | False | Total |
| assert(shell_coords->size() > 1); |
1 |
0 |
1 |
| assert(shell_coords->size() > 1); |
0 |
1 |
1 |
|
| 41 |
1 |
| poly_sequence_t shell_seq; |
| 42 |
5 |
▶ | for (size_t i = 0; i < shell_coords->size() - 1; ++i) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (size_t i = 0; i < shell_coords->size() - 1; ++i) { |
5 |
0 |
5 |
| for (size_t i = 0; i < shell_coords->size() - 1; ++i) { |
4 |
1 |
5 |
|
| 43 |
4 |
▶ | auto& coord = shell_coords->getAt(i); |
Branch: 1 branch
| Branch | True | False | Total |
| auto& coord = shell_coords->getAt(i); |
4 |
0 |
4 |
|
| 44 |
4 |
▶ | shell_seq.push_back(coord); |
Branch: 1 branch
| Branch | True | False | Total |
| shell_seq.push_back(coord); |
4 |
0 |
4 |
|
| 45 |
4 |
▶ | linearized.push_back(coord); |
Branch: 1 branch
| Branch | True | False | Total |
| linearized.push_back(coord); |
4 |
0 |
4 |
|
| 46 |
|
| } |
| 47 |
1 |
▶ | polygon.push_back(shell_seq); |
Branch: 1 branch
| Branch | True | False | Total |
| polygon.push_back(shell_seq); |
1 |
0 |
1 |
|
| 48 |
|
| |
| 49 |
|
| /* inner rings/holes */ |
| 50 |
1 |
▶ | auto holes_num = input.getNumInteriorRing(); |
Branch: 1 branch
| Branch | True | False | Total |
| auto holes_num = input.getNumInteriorRing(); |
1 |
0 |
1 |
|
| 51 |
2 |
▶ | for (size_t i = 0; i < holes_num; ++i) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (size_t i = 0; i < holes_num; ++i) { |
1 |
1 |
2 |
|
| 52 |
1 |
▶ | auto* hole = input.getInteriorRingN(i); |
Branch: 1 branch
| Branch | True | False | Total |
| auto* hole = input.getInteriorRingN(i); |
1 |
0 |
1 |
|
| 53 |
1 |
▶ | auto hole_coords = seq_holder_t{hole->getCoordinates()}; |
Branch: 1 branch
| Branch | True | False | Total |
| auto hole_coords = seq_holder_t{hole->getCoordinates()}; |
1 |
0 |
1 |
|
| 54 |
1 |
▶ | assert(hole_coords->size() > 1); |
Branch: 2 branches
| Branch | True | False | Total |
| assert(hole_coords->size() > 1); |
1 |
0 |
1 |
| assert(hole_coords->size() > 1); |
0 |
1 |
1 |
|
| 55 |
1 |
| poly_sequence_t seq; |
| 56 |
5 |
▶ | for (size_t j = 0; j < hole_coords->size() - 1; ++j) { |
Branch: 2 branches
| Branch | True | False | Total |
| for (size_t j = 0; j < hole_coords->size() - 1; ++j) { |
5 |
0 |
5 |
| for (size_t j = 0; j < hole_coords->size() - 1; ++j) { |
4 |
1 |
5 |
|
| 57 |
4 |
▶ | auto& coord = hole_coords->getAt(j); |
Branch: 1 branch
| Branch | True | False | Total |
| auto& coord = hole_coords->getAt(j); |
4 |
0 |
4 |
|
| 58 |
4 |
▶ | seq.push_back(coord); |
Branch: 1 branch
| Branch | True | False | Total |
| seq.push_back(coord); |
4 |
0 |
4 |
|
| 59 |
4 |
▶ | linearized.push_back(coord); |
Branch: 1 branch
| Branch | True | False | Total |
| linearized.push_back(coord); |
4 |
0 |
4 |
|
| 60 |
|
| } |
| 61 |
1 |
▶ | polygon.push_back(seq); |
Branch: 1 branch
| Branch | True | False | Total |
| polygon.push_back(seq); |
1 |
0 |
1 |
|
| 62 |
1 |
| } |
| 63 |
|
| |
| 64 |
|
| /* run tesselation */ |
| 65 |
|
| using N = uint32_t; |
| 66 |
1 |
▶ | std::vector<N> indices = mapbox::earcut<N>(polygon); |
Branch: 1 branch
| Branch | True | False | Total |
| std::vector<N> indices = mapbox::earcut<N>(polygon); |
1 |
0 |
1 |
|
| 67 |
1 |
| auto vertices = indices.size(); |
| 68 |
1 |
▶ | if (!vertices) throw "no tesselation (invalid polygon?)"; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!vertices) throw "no tesselation (invalid polygon?)"; |
0 |
1 |
1 |
|
| 69 |
1 |
▶ | assert(vertices % 3 == 0); |
Branch: 1 branch
| Branch | True | False | Total |
| assert(vertices % 3 == 0); |
0 |
1 |
1 |
|
| 70 |
|
| |
| 71 |
|
| /* construct triangles as polygones */ |
| 72 |
1 |
| auto factory = input.getFactory(); |
| 73 |
1 |
▶ | auto seq_factory = factory->getCoordinateSequenceFactory(); |
Branch: 1 branch
| Branch | True | False | Total |
| auto seq_factory = factory->getCoordinateSequenceFactory(); |
1 |
0 |
1 |
|
| 74 |
1 |
▶ | auto triangles = new result_t(); |
Branch: 1 branch
| Branch | True | False | Total |
| auto triangles = new result_t(); |
1 |
0 |
1 |
|
| 75 |
9 |
▶ | for(size_t i = 0; i < indices.size(); i += 3) { |
Branch: 1 branch
| Branch | True | False | Total |
| for(size_t i = 0; i < indices.size(); i += 3) { |
8 |
1 |
9 |
|
| 76 |
8 |
| auto& c_A = linearized[indices[i + 0]]; |
| 77 |
8 |
| auto& c_B = linearized[indices[i + 1]]; |
| 78 |
8 |
| auto& c_C = linearized[indices[i + 2]]; |
| 79 |
8 |
▶ | auto seq = seq_holder_t{seq_factory->create(4, 2)}; |
Branch: 1 branch
| Branch | True | False | Total |
| auto seq = seq_holder_t{seq_factory->create(4, 2)}; |
8 |
0 |
8 |
|
| 80 |
8 |
▶ | seq->setAt(c_A, 0); |
Branch: 1 branch
| Branch | True | False | Total |
| seq->setAt(c_A, 0); |
8 |
0 |
8 |
|
| 81 |
8 |
▶ | seq->setAt(c_B, 1); |
Branch: 1 branch
| Branch | True | False | Total |
| seq->setAt(c_B, 1); |
8 |
0 |
8 |
|
| 82 |
8 |
▶ | seq->setAt(c_C, 2); |
Branch: 1 branch
| Branch | True | False | Total |
| seq->setAt(c_C, 2); |
8 |
0 |
8 |
|
| 83 |
8 |
▶ | seq->setAt(c_A, 3); /* close the poly */ |
Branch: 1 branch
| Branch | True | False | Total |
| seq->setAt(c_A, 3); /* close the poly */ |
8 |
0 |
8 |
|
| 84 |
|
| |
| 85 |
8 |
▶ | auto shell = factory->createLinearRing(seq.release()); |
Branch: 1 branch
| Branch | True | False | Total |
| auto shell = factory->createLinearRing(seq.release()); |
8 |
0 |
8 |
|
| 86 |
8 |
▶ | auto holes = new std::vector<geos::geom::Geometry*>(); |
Branch: 1 branch
| Branch | True | False | Total |
| auto holes = new std::vector<geos::geom::Geometry*>(); |
8 |
0 |
8 |
|
| 87 |
8 |
▶ | auto poly = factory->createPolygon(shell, holes); |
Branch: 1 branch
| Branch | True | False | Total |
| auto poly = factory->createPolygon(shell, holes); |
8 |
0 |
8 |
|
| 88 |
8 |
▶ | triangles->push_back(poly); |
Branch: 2 branches
| Branch | True | False | Total |
| triangles->push_back(poly); |
8 |
0 |
8 |
| triangles->push_back(poly); |
8 |
0 |
8 |
|
| 89 |
8 |
| } |
| 90 |
|
| |
| 91 |
2 |
▶ | return factory->createGeometryCollection(triangles); |
Branch: 1 branch
| Branch | True | False | Total |
| return factory->createGeometryCollection(triangles); |
1 |
0 |
1 |
|
| 92 |
1 |
| } |
| 93 |
|
| |
| 94 |
|
| |
| 95 |
|
| }} |