Mercurial > hg > orthanc-stone

diff UnitTestsSources/ComputationalGeometryTests.cpp @ 1875:b896f20d24ca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added UnionOfRectangles algorithm
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 19:59:40 +0100
parents 08f2476e8f5e
children b1f510e601d2
line wrap: on
line diff
--- a/UnitTestsSources/ComputationalGeometryTests.cpp	Tue Jan 11 18:58:37 2022 +0100
+++ b/UnitTestsSources/ComputationalGeometryTests.cpp	Tue Jan 11 19:59:40 2022 +0100
@@ -25,6 +25,7 @@
 #include "../OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.h"
 #include "../OrthancStone/Sources/Toolbox/Internals/RectanglesIntegerProjection.h"
 #include "../OrthancStone/Sources/Toolbox/SegmentTree.h"
+#include "../OrthancStone/Sources/Toolbox/UnionOfRectangles.h"
 
 #include <Logging.h>
 #include <OrthancException.h>
@@ -479,3 +480,224 @@
   ASSERT_EQ(5u, v[4]);
   ASSERT_EQ(5u, v[5]);
 }
+
+
+TEST(UnionOfRectangles, Textbook)
+{
+  // This is Figure 8.12 from textbook
+
+  std::list<OrthancStone::Extent2D>  rectangles;
+  rectangles.push_back(OrthancStone::Extent2D(1, 3, 13, 5));
+  rectangles.push_back(OrthancStone::Extent2D(3, 1, 7, 12));
+  rectangles.push_back(OrthancStone::Extent2D(5, 7, 11, 10));
+  rectangles.push_back(OrthancStone::Extent2D(10, 2, 14, 8));
+  rectangles.push_back(OrthancStone::Extent2D(3, 3, 4, 3));  // empty rectangle
+
+  for (unsigned int fillHole = 0; fillHole < 2; fillHole++)
+  {
+    if (fillHole)
+    {
+      rectangles.push_back(OrthancStone::Extent2D(6.5, 4.5, 10.5, 7.5));
+    }
+    
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+
+    ASSERT_EQ(fillHole ? 1u : 2u, contours.size());
+    ASSERT_EQ(17u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(3, 12)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 12)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 10)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(11, 10)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(11, 8)));
+    ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(14, 8)));
+    ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(14, 2)));
+    ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D(10, 2)));
+    ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D(10, 3)));
+    ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D(7, 3)));
+    ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(7, 1)));
+    ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(3, 1)));
+    ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(3, 3)));
+    ASSERT_TRUE(contours.front()[13].IsEqual(OrthancStone::ScenePoint2D(1, 3)));
+    ASSERT_TRUE(contours.front()[14].IsEqual(OrthancStone::ScenePoint2D(1, 5)));
+    ASSERT_TRUE(contours.front()[15].IsEqual(OrthancStone::ScenePoint2D(3, 5)));
+    ASSERT_TRUE(contours.front()[16].IsEqual(OrthancStone::ScenePoint2D(3, 12)));
+
+    if (!fillHole)
+    {
+      ASSERT_EQ(5u, contours.back().size());
+      ASSERT_TRUE(contours.back()[0].IsEqual(OrthancStone::ScenePoint2D(10, 7)));
+      ASSERT_TRUE(contours.back()[1].IsEqual(OrthancStone::ScenePoint2D(7, 7)));
+      ASSERT_TRUE(contours.back()[2].IsEqual(OrthancStone::ScenePoint2D(7, 5)));
+      ASSERT_TRUE(contours.back()[3].IsEqual(OrthancStone::ScenePoint2D(10, 5)));
+      ASSERT_TRUE(contours.back()[4].IsEqual(OrthancStone::ScenePoint2D(10, 7)));
+    }
+  }
+}
+
+
+#if 0
+static void SaveSvg(const std::list< std::vector<OrthancStone::ScenePoint2D> >& contours)
+{
+  float ww = 15;
+  float hh = 13;
+
+  FILE* fp = fopen("test.svg", "w");
+  fprintf(fp, "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n");
+  fprintf(fp, "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\" \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n");
+  fprintf(fp, "<svg width=\"%f\" height=\"%f\" viewBox=\"0 0 %f %f\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n", 100.0f*ww, 100.0f*hh, ww, hh);
+
+  // http://thenewcode.com/1068/Making-Arrows-in-SVG
+  fprintf(fp, "<defs>\n");
+  fprintf(fp, "<marker id=\"arrowhead\" markerWidth=\"2\" markerHeight=\"3\" \n");
+  fprintf(fp, "refX=\"2\" refY=\"1.5\" orient=\"auto\">\n");
+  fprintf(fp, "<polygon points=\"0 0, 2 1.5, 0 3\" />\n");
+  fprintf(fp, "</marker>\n");
+  fprintf(fp, "</defs>\n");
+
+  fprintf(fp, "<rect fill=\"#fff\" stroke=\"#000\" x=\"0\" y=\"0\" width=\"%f\" height=\"%f\"/>\n", ww, hh);
+
+  for (std::list< std::vector<OrthancStone::ScenePoint2D> >::const_iterator
+         it = contours.begin(); it != contours.end(); ++it)
+  {
+    for (size_t i = 0; i + 1 < it->size(); i++)
+    {
+      float x1 = (*it)[i].GetX();
+      float x2 = (*it)[i + 1].GetX();
+      float y1 = (*it)[i].GetY();
+      float y2 = (*it)[i + 1].GetY();
+      
+      fprintf(fp, "<line x1=\"%f\" y1=\"%f\" x2=\"%f\" y2=\"%f\" stroke=\"blue\" stroke-width=\"0.05\" marker-end=\"url(#arrowhead)\"/>\n", x1, y1, x2, y2);
+    }
+  }
+  fprintf(fp, "</svg>\n");
+  
+  fclose(fp);
+}
+#endif
+
+
+TEST(UnionOfRectangles, Complex)
+{
+  {
+    std::list<OrthancStone::Extent2D>  rectangles;
+    rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
+    rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
+    rectangles.push_back(OrthancStone::Extent2D(4, 2, 7, 4));
+    rectangles.push_back(OrthancStone::Extent2D(7, 4, 10, 6));
+  
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+
+    ASSERT_EQ(1u, contours.size());
+    ASSERT_EQ(17u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(10, 6)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(10, 4)));
+    ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
+    ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(7, 2)));
+    ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D(4, 2)));
+    ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
+    ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
+    ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
+    ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D(4, 6)));
+    ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
+    ASSERT_TRUE(contours.front()[13].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
+    ASSERT_TRUE(contours.front()[14].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
+    ASSERT_TRUE(contours.front()[15].IsEqual(OrthancStone::ScenePoint2D(4, 6)));
+    ASSERT_TRUE(contours.front()[16].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+  }
+  
+  {
+    std::list<OrthancStone::Extent2D>  rectangles;
+    rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
+    rectangles.push_back(OrthancStone::Extent2D(4, 4, 7, 6));
+  
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+
+    ASSERT_EQ(1u, contours.size());
+    ASSERT_EQ(5u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(1, 6)));
+  }
+  
+  {
+    std::list<OrthancStone::Extent2D>  rectangles;
+    rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
+    rectangles.push_back(OrthancStone::Extent2D(1, 6, 4, 8));
+  
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+
+    ASSERT_EQ(1u, contours.size());
+    ASSERT_EQ(5u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(1, 8)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(1, 8)));
+  }
+  
+  {
+    std::list<OrthancStone::Extent2D>  rectangles;
+    rectangles.push_back(OrthancStone::Extent2D(1, 1, 2, 2));
+    rectangles.push_back(OrthancStone::Extent2D(4, 4, 7, 6));
+    rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
+
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+    
+    ASSERT_EQ(2u, contours.size());
+    
+    ASSERT_EQ(5u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 4)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+    
+    ASSERT_EQ(5u, contours.back().size());
+    ASSERT_TRUE(contours.back()[0].IsEqual(OrthancStone::ScenePoint2D(1, 2)));
+    ASSERT_TRUE(contours.back()[1].IsEqual(OrthancStone::ScenePoint2D(2, 2)));
+    ASSERT_TRUE(contours.back()[2].IsEqual(OrthancStone::ScenePoint2D(2, 1)));
+    ASSERT_TRUE(contours.back()[3].IsEqual(OrthancStone::ScenePoint2D(1, 1)));
+    ASSERT_TRUE(contours.back()[4].IsEqual(OrthancStone::ScenePoint2D(1, 2)));
+  }
+
+#if 0
+  {
+    std::list<OrthancStone::Extent2D>  rectangles;
+    rectangles.push_back(OrthancStone::Extent2D(1, 4, 4, 6));
+    rectangles.push_back(OrthancStone::Extent2D(6, 4, 9, 6));
+    rectangles.push_back(OrthancStone::Extent2D(4, 6, 7, 8));
+    rectangles.push_back(OrthancStone::Extent2D(4, 2, 7, 6));
+
+    std::list< std::vector<OrthancStone::ScenePoint2D> > contours;
+    OrthancStone::UnionOfRectangles::Apply(contours, rectangles);
+
+    SaveSvg(contours);
+    
+    ASSERT_EQ(1u, contours.size());
+    ASSERT_EQ(13u, contours.front().size());
+    ASSERT_TRUE(contours.front()[0].IsEqual(OrthancStone::ScenePoint2D(4, 8)));
+    ASSERT_TRUE(contours.front()[1].IsEqual(OrthancStone::ScenePoint2D(7, 8)));
+    ASSERT_TRUE(contours.front()[2].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
+    ASSERT_TRUE(contours.front()[3].IsEqual(OrthancStone::ScenePoint2D(9, 6)));
+    ASSERT_TRUE(contours.front()[4].IsEqual(OrthancStone::ScenePoint2D(7, 6)));
+    ASSERT_TRUE(contours.front()[5].IsEqual(OrthancStone::ScenePoint2D(4, 4)));
+    ASSERT_TRUE(contours.front()[6].IsEqual(OrthancStone::ScenePoint2D(1, 4)));
+    ASSERT_TRUE(contours.front()[7].IsEqual(OrthancStone::ScenePoint2D()));
+    ASSERT_TRUE(contours.front()[8].IsEqual(OrthancStone::ScenePoint2D()));
+    ASSERT_TRUE(contours.front()[9].IsEqual(OrthancStone::ScenePoint2D()));
+    ASSERT_TRUE(contours.front()[10].IsEqual(OrthancStone::ScenePoint2D()));
+    ASSERT_TRUE(contours.front()[11].IsEqual(OrthancStone::ScenePoint2D()));
+    ASSERT_TRUE(contours.front()[12].IsEqual(OrthancStone::ScenePoint2D()));
+  }
+#endif
+}