tests/unit/triangulate/DelaunayTest.cpp

   1
   2 //
   3 // Test Suite for geos::triangulate::quadedge::QuadEdge
   4 //
   5 // tut
   6 #include <tut.hpp>
   7 // geos
   8 #include <geos/triangulate/quadedge/QuadEdge.h>
   9 #include <geos/triangulate/quadedge/QuadEdgeSubdivision.h>
  10 #include <geos/triangulate/IncrementalDelaunayTriangulator.h>
  11 #include <geos/triangulate/DelaunayTriangulationBuilder.h>
  12 //#include <geos/io/WKTWriter.h>
  13 #include <geos/io/WKTReader.h>
  14 #include <geos/geom/GeometryCollection.h>
  15 #include <geos/geom/GeometryFactory.h>
  16 #include <geos/geom/CoordinateArraySequence.h>
  17 //#include <stdio.h>
  18
  19 using namespace geos::triangulate;
  20 using namespace geos::triangulate::quadedge;
  21 using namespace geos::geom;
  22 using namespace geos::io;
  23
  24 namespace tut
  25 {
  26         //
  27         // Test Group
  28         //
  29
  30         // dummy data, not used
  31         struct test_incdelaunaytri_data
  32         {
  33                 test_incdelaunaytri_data()
  34                 {
  35                 }
  36         };
  37
  38         typedef test_group<test_incdelaunaytri_data> group;
  39         typedef group::object object;
  40
  41         group test_incdelaunaytri_group("geos::triangulate::Delaunay");
  42
  43         //helper function for funning triangulation
  44         void runDelaunay(const char *sitesWkt, bool computeTriangles, const char *expectedWkt, double tolerance=0.0)
  45         {
  46                 WKTReader reader;
  47                 std::auto_ptr<Geometry> results;
  48                 Geometry *sites = reader.read(sitesWkt);
  49                 Geometry *expected = reader.read(expectedWkt);
  50                 DelaunayTriangulationBuilder builder;
  51                 builder.setTolerance(tolerance);
  52                 GeometryFactory geomFact;
  53
  54                 builder.setSites(*sites);
  55                 if(computeTriangles)
  56                         results=builder.getTriangles(geomFact);
  57                 else
  58                         results=builder.getEdges(geomFact);
  59
  60                 results->normalize();
  61                 expected->normalize();
  62
  63                 ensure(results->toString(), results->equalsExact(expected, 1e-7));
  64                 ensure_equals(results->getCoordinateDimension(), expected->getCoordinateDimension());
  65
  66                 delete sites;
  67                 delete expected;
  68         }
  69
  70         //
  71         // Test Cases
  72         //
  73
  74         // 1 - Basic function test
  75         template<>
  76         template<>
  77         void object::test<1>()
  78         {
  79                 //Create a subdivision centered at (0,0)
  80                 QuadEdgeSubdivision sub(Envelope(-100, 100, -100, 100), .00001);
  81                 //make a triagulaor to work on sub
  82                 IncrementalDelaunayTriangulator triangulator(&sub);
  83
  84                 triangulator.insertSite(Vertex(0, 0));
  85
  86                 //extract the triangles from the subdivision
  87                 GeometryFactory geomFact;
  88                 std::auto_ptr<GeometryCollection> tris = sub.getTriangles(geomFact);
  89         }
  90
  91         // 2 - Test Triangle
  92         template<>
  93         template<>
  94         void object::test<2>()
  95         {
  96                 const char * wkt = "MULTIPOINT ((10 10), (10 20), (20 20))";
  97                 const char* expectedEdges = "MULTILINESTRING ((10 20, 20 20), (10 10, 10 20), (10 10, 20 20))";
  98                 const char * expectedTri = "GEOMETRYCOLLECTION (POLYGON ((10 20, 10 10, 20 20, 10 20)))";
  99
 100                 runDelaunay(wkt, true, expectedTri);
 101                 runDelaunay(wkt, false, expectedEdges);
 102         }
 103
 104         // 3 - Test Random
 105         template<>
 106         template<>
 107         void object::test<3>()
 108         {
 109                 const char* wkt = "MULTIPOINT ((50 40), (140 70), (80 100), (130 140), (30 150), (70 180), (190 110), (120 20))";
 110                 const char* expectedEdges = "MULTILINESTRING ((70 180, 190 110), (30 150, 70 180), (30 150, 50 40), (50 40, 120 20), (190 110, 120 20), (120 20, 140 70), (190 110, 140 70), (130 140, 140 70), (130 140, 190 110), (70 180, 130 140), (80 100, 130 140), (70 180, 80 100), (30 150, 80 100), (50 40, 80 100), (80 100, 120 20), (80 100, 140 70))";
 111                 const char* expectedTri = "GEOMETRYCOLLECTION (POLYGON ((30 150, 50 40, 80 100, 30 150)), POLYGON ((30 150, 80 100, 70 180, 30 150)), POLYGON ((70 180, 80 100, 130 140, 70 180)), POLYGON ((70 180, 130 140, 190 110, 70 180)), POLYGON ((190 110, 130 140, 140 70, 190 110)), POLYGON ((190 110, 140 70, 120 20, 190 110)), POLYGON ((120 20, 140 70, 80 100, 120 20)), POLYGON ((120 20, 80 100, 50 40, 120 20)), POLYGON ((80 100, 140 70, 130 140, 80 100)))";
 112
 113                 runDelaunay(wkt, false, expectedEdges);
 114                 runDelaunay(wkt, true, expectedTri);
 115         }
 116
 117         // 4 - Test grid
 118         template<>
 119         template<>
 120         void object::test<4>()
 121         {
 122                 const char * wkt = "MULTIPOINT ((10 10), (10 20), (20 20), (20 10), (20 0), (10 0), (0 0), (0 10), (0 20))";
 123                 const char* expectedEdges = "MULTILINESTRING ((10 20, 20 20), (0 20, 10 20), (0 10, 0 20), (0 0, 0 10), (0 0, 10 0), (10 0, 20 0), (20 0, 20 10), (20 10, 20 20), (10 20, 20 10), (10 10, 20 10), (10 10, 10 20), (10 10, 0 20), (10 10, 0 10), (10 0, 10 10), (0 10, 10 0), (10 10, 20 0))";
 124                 const char * expectedTri = "GEOMETRYCOLLECTION (POLYGON ((0 20, 0 10, 10 10, 0 20)), POLYGON ((0 20, 10 10, 10 20, 0 20)), POLYGON ((10 20, 10 10, 20 10, 10 20)), POLYGON ((10 20, 20 10, 20 20, 10 20)), POLYGON ((10 0, 20 0, 10 10, 10 0)), POLYGON ((10 0, 10 10, 0 10, 10 0)), POLYGON ((10 0, 0 10, 0 0, 10 0)), POLYGON ((10 10, 20 0, 20 10, 10 10)))";
 125
 126                 runDelaunay(wkt, false, expectedEdges);
 127                 runDelaunay(wkt, true, expectedTri);
 128         }
 129
 130         // 5 - Test Circle
 131         template<>
 132         template<>
 133         void object::test<5>()
 134         {
 135                 const char * wkt = "POLYGON ((42 30, 41.96 29.61, 41.85 29.23, 41.66 28.89, 41.41 28.59, 41.11 28.34, 40.77 28.15, 40.39 28.04, 40 28, 39.61 28.04, 39.23 28.15, 38.89 28.34, 38.59 28.59, 38.34 28.89, 38.15 29.23, 38.04 29.61, 38 30, 38.04 30.39, 38.15 30.77, 38.34 31.11, 38.59 31.41, 38.89 31.66, 39.23 31.85, 39.61 31.96, 40 32, 40.39 31.96, 40.77 31.85, 41.11 31.66, 41.41 31.41, 41.66 31.11, 41.85 30.77, 41.96 30.39, 42 30))";
 136                 const char* expectedEdges = "MULTILINESTRING ((41.66 31.11, 41.85 30.77), (41.41 31.41, 41.66 31.11), (41.11 31.66, 41.41 31.41), (40.77 31.85, 41.11 31.66), (40.39 31.96, 40.77 31.85), (40 32, 40.39 31.96), (39.61 31.96, 40 32), (39.23 31.85, 39.61 31.96), (38.89 31.66, 39.23 31.85), (38.59 31.41, 38.89 31.66), (38.34 31.11, 38.59 31.41), (38.15 30.77, 38.34 31.11), (38.04 30.39, 38.15 30.77), (38 30, 38.04 30.39), (38 30, 38.04 29.61), (38.04 29.61, 38.15 29.23), (38.15 29.23, 38.34 28.89), (38.34 28.89, 38.59 28.59), (38.59 28.59, 38.89 28.34), (38.89 28.34, 39.23 28.15), (39.23 28.15, 39.61 28.04), (39.61 28.04, 40 28), (40 28, 40.39 28.04), (40.39 28.04, 40.77 28.15), (40.77 28.15, 41.11 28.34), (41.11 28.34, 41.41 28.59), (41.41 28.59, 41.66 28.89), (41.66 28.89, 41.85 29.23), (41.85 29.23, 41.96 29.61), (41.96 29.61, 42 30), (41.96 30.39, 42 30), (41.85 30.77, 41.96 30.39), (41.66 31.11, 41.96 30.39), (41.41 31.41, 41.96 30.39), (41.41 28.59, 41.96 30.39), (41.41 28.59, 41.41 31.41), (38.59 28.59, 41.41 28.59), (38.59 28.59, 41.41 31.41), (38.59 28.59, 38.59 31.41), (38.59 31.41, 41.41 31.41), (38.59 31.41, 39.61 31.96), (39.61 31.96, 41.41 31.41), (39.61 31.96, 40.39 31.96), (40.39 31.96, 41.41 31.41), (40.39 31.96, 41.11 31.66), (38.04 30.39, 38.59 28.59), (38.04 30.39, 38.59 31.41), (38.04 30.39, 38.34 31.11), (38.04 29.61, 38.59 28.59), (38.04 29.61, 38.04 30.39), (39.61 28.04, 41.41 28.59), (38.59 28.59, 39.61 28.04), (38.89 28.34, 39.61 28.04), (40.39 28.04, 41.41 28.59), (39.61 28.04, 40.39 28.04), (41.96 29.61, 41.96 30.39), (41.41 28.59, 41.96 29.61), (41.66 28.89, 41.96 29.61), (40.39 28.04, 41.11 28.34), (38.04 29.61, 38.34 28.89), (38.89 31.66, 39.61 31.96))";
 137
 138                 runDelaunay(wkt, false, expectedEdges);
 139         }
 140
 141         // 6 - Test Polygon With Chevron Holes
 142         template<>
 143         template<>
 144         void object::test<6>()
 145         {
 146                 const char * wkt = "POLYGON ((0 0, 0 200, 180 200, 180 0, 0 0), (20 180, 160 180, 160 20, 152.625 146.75, 20 180), (30 160, 150 30, 70 90, 30 160))";
 147                 const char* expectedEdges = "MULTILINESTRING ((0 200, 180 200), (0 0, 0 200), (0 0, 180 0), (180 200, 180 0), (152.625 146.75, 180 0), (152.625 146.75, 180 200), (152.625 146.75, 160 180), (160 180, 180 200), (0 200, 160 180), (20 180, 160 180), (0 200, 20 180), (20 180, 30 160), (30 160, 0 200), (0 0, 30 160), (30 160, 70 90), (0 0, 70 90), (70 90, 150 30), (150 30, 0 0), (150 30, 160 20), (0 0, 160 20), (160 20, 180 0), (152.625 146.75, 160 20), (150 30, 152.625 146.75), (70 90, 152.625 146.75), (30 160, 152.625 146.75), (30 160, 160 180))";
 148
 149                 runDelaunay(wkt, false, expectedEdges);
 150         }
 151
 152         // 7 - Test grid (2.5d)
 153         template<>
 154         template<>
 155         void object::test<7>()
 156         {
 157                 const char * wkt = "MULTIPOINT ((10 10 1), (10 20 2), (20 20 3), (20 10 1.5), (20 0 2.5), (10 0 3.5), (0 0 0), (0 10 .5), (0 20 .25))";
 158                 const char* expectedEdges = "MULTILINESTRING ((10 20 2, 20 20 3), (0 20 .25, 10 20 2), (0 10 .5, 0 20 .25), (0 0 0, 0 10 .5), (0 0 0, 10 0 3.5), (10 0 3.5, 20 0 2.5), (20 0 2.5, 20 10 1.5), (20 10 1.5, 20 20 3), (10 20 2, 20 10 1.5), (10 10 1, 20 10 1.6), (10 10 1, 10 20 2), (10 10 1, 0 20 .25), (10 10 1, 0 10 .5), (10 0 3.5, 10 10 1), (0 10 .5, 10 0 3.5), (10 10 1, 20 0 2.5))";
 159                 const char * expectedTri = "GEOMETRYCOLLECTION (POLYGON ((0 20 .25, 0 10 .5, 10 10 1, 0 20 .25)), POLYGON ((0 20 .25, 10 10 1, 10 20 2, 0 20 .25)), POLYGON ((10 20 2, 10 10 1, 20 10 1.5, 10 20 2)), POLYGON ((10 20 2, 20 10 1.5, 20 20 3, 10 20 2)), POLYGON ((10 0 3.5, 20 0 2.5, 10 10 1, 10 0 3.5)), POLYGON ((10 0 3.5, 10 10 1, 0 10 .5, 10 0 3.5)), POLYGON ((10 0 3.5, 0 10 .5, 0 0 0, 10 0 3.5)), POLYGON ((10 10 1, 20 0 2.5, 20 10 1.5, 10 10 1)))";
 160
 161                 runDelaunay(wkt, false, expectedEdges);
 162                 runDelaunay(wkt, true, expectedTri);
 163         }
 164
 165         // 8 - Tolerance robustness - http://trac.osgeo.org/geos/ticket/604
 166         template<>
 167         template<>
 168         void object::test<8>()
 169         {
 170                 const char * wkt = "MULTIPOINT(-118.3964065 56.0557,-118.396406 56.0475,-118.396407 56.04,-118.3968 56)";
 171                 const char* expectedEdges = "MULTILINESTRING ((-118.3964065 56.0557, -118.396406 56.0475), (-118.396407 56.04, -118.396406 56.0475), (-118.3968 56, -118.396407 56.04))";
 172
 173                 runDelaunay(wkt, false, expectedEdges, 0.001);
 174         }
 175         // 9 - Test for DelaunayTriangulationBuilder::envelope
 176         template<>
 177         template<>
 178         void object::test<9>()
 179         {
 180                 std::vector<Coordinate>* v = new std::vector<Coordinate>();
 181                 v->push_back( Coordinate (150,200) );
 182                 v->push_back( Coordinate (180,270) );
 183                 v->push_back( Coordinate (275,163) );
 184
 185                 geos::geom::CoordinateArraySequence *seq = new CoordinateArraySequence(v);
 186
 187                 Envelope env = DelaunayTriangulationBuilder::envelope(*seq);
 188
 189                 ensure_equals(env.getWidth() , 125);
 190                 ensure_equals(env.getHeight() , 107);
 191
 192         }
 193
 194 } // namespace tut
 195