# HG changeset patch
# User Sebastien Jodogne <s.jodogne@gmail.com>
# Date 1642514644 -3600
# Node ID 5dae41084ab7e91f2de539f707f47f4ad9ec164a
# Parent  bee6da5155dc947b7998d7d27dfdb8f6437a3507
fix filling polygons

diff -r bee6da5155dc -r 5dae41084ab7 OrthancFramework/Sources/Images/ImageProcessing.cpp
--- a/OrthancFramework/Sources/Images/ImageProcessing.cpp	Tue Jan 18 13:04:47 2022 +0100
+++ b/OrthancFramework/Sources/Images/ImageProcessing.cpp	Tue Jan 18 15:04:04 2022 +0100
@@ -1983,8 +1983,8 @@
   
 
   // For an index, return y-coordinate of next nonhorizontal line
-  static size_t GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points,
-                                size_t k)
+  static int GetPolygonNextY(const std::vector<ImageProcessing::ImagePoint>& points,
+                             size_t k)
   {
     // cf. "yNext()" in textbook
     size_t j = k;
@@ -2005,8 +2005,8 @@
   }
 
 
-  static size_t GetPolygonPreviousY(const std::vector<ImageProcessing::ImagePoint>& points,
-                                    size_t k)
+  static int GetPolygonPreviousY(const std::vector<ImageProcessing::ImagePoint>& points,
+                                 size_t k)
   {
     size_t j = k;
 
@@ -2046,6 +2046,32 @@
       return;
     }
 
+    bool onlyHorizontalSegments = true;
+    for (size_t i = 1; i < points.size(); i++)
+    {
+      if (points[0].GetY() != points[i].GetY())
+      {
+        onlyHorizontalSegments = false;
+        break;
+      }
+    }
+
+    if (onlyHorizontalSegments)
+    {
+      // Degenerate case: There are only horizontal lines. If this is
+      // the case, "GetPolygonPreviousY()" will be an infinite loop
+      int x1 = points[0].GetX();
+      int x2 = points[0].GetX();
+      for (size_t i = 1; i < points.size(); i++)
+      {
+        assert(points[i].GetY() == points[0].GetY());
+        x1 = std::min(x1, points[i].GetX());
+        x2 = std::max(x2, points[i].GetX());
+      }
+      filler.Fill(points[0].GetY(), x1, x2);
+      return;
+    }
+
     EdgeTable globalEdgeTable;
 
     // cf. "buildEdgeList()" in textbook
@@ -2081,20 +2107,7 @@
       v1 = v2;
     }
     
-    if (globalEdgeTable.empty())
-    {
-      // Degenerate case: There were only horizontal lines
-      int x1 = points[0].GetX();
-      int x2 = points[0].GetX();
-      for (size_t i = 1; i < points.size(); i++)
-      {
-        assert(points[i].GetY() == points[0].GetY());
-        x1 = std::min(x1, points[i].GetX());
-        x2 = std::max(x2, points[i].GetX());
-      }
-      filler.Fill(points[0].GetY(), x1, x2);
-      return;
-    }
+    assert(!globalEdgeTable.empty());
 
     std::vector<PolygonEdge> activeEdges;
 
@@ -2147,11 +2160,23 @@
         std::sort(activeEdges.begin(), activeEdges.end());
 
         // cf. "fillScan()" in textbook
-        for (size_t k = 0; k + 1 < activeEdges.size(); k += 2)
+        for (size_t k = 0; k + 1 < activeEdges.size(); )
         {
           int a = activeEdges[k].GetExitX();
           int b = activeEdges[k + 1].GetEnterX();
-          filler.Fill(y, std::min(a, b), std::max(a, b));
+
+          // Fix wrt. the textbook: merge overlapping segments
+          k += 2;
+          while (k + 1 < activeEdges.size() &&
+                 activeEdges[k].GetExitX() == b)
+          {
+            assert(a <= b);
+            b = activeEdges[k + 1].GetEnterX();
+            k += 2;
+          }
+
+          assert(a <= b);
+          filler.Fill(y, a, b);
         }
 
         // cf. "updateActiveList()" in textbook
diff -r bee6da5155dc -r 5dae41084ab7 OrthancFramework/UnitTestsSources/ImageProcessingTests.cpp
--- a/OrthancFramework/UnitTestsSources/ImageProcessingTests.cpp	Tue Jan 18 13:04:47 2022 +0100
+++ b/OrthancFramework/UnitTestsSources/ImageProcessingTests.cpp	Tue Jan 18 15:04:04 2022 +0100
@@ -196,8 +196,6 @@
 }
 
 
-#include "../Sources/Images/PngWriter.h"
-
 TYPED_TEST(TestIntegerImageTraits, FillPolygon)
 {
   ImageAccessor& image = this->GetImage();
@@ -212,9 +210,6 @@
 
   ImageProcessing::FillPolygon(image, points, 255);
 
-  Orthanc::PngWriter writer;
-  Orthanc::IImageWriter::WriteToFile(writer, "tutu.png", image);
-  
   // outside polygon
   ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 0, 0));
   ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 0, 6));
@@ -311,9 +306,9 @@
 }
 
 static void SetSignedGrayscale16Pixel(ImageAccessor& image,
-                                unsigned int x,
-                                unsigned int y,
-                                int16_t value)
+                                      unsigned int x,
+                                      unsigned int y,
+                                      int16_t value)
 {
   ImageTraits<PixelFormat_SignedGrayscale16>::SetPixel(image, value, x, y);
 }
@@ -1096,3 +1091,136 @@
     }
   }
 }
+
+
+namespace
+{
+  class PolygonSegments : public ImageProcessing::IPolygonFiller
+  {
+  private:
+    std::vector<int> y_, x1_, x2_;
+
+  public:  
+    virtual void Fill(int y,
+                      int x1,
+                      int x2) ORTHANC_OVERRIDE
+    {
+      assert(x1 <= x2);
+      y_.push_back(y);
+      x1_.push_back(x1);
+      x2_.push_back(x2);
+    }
+
+    size_t GetSize() const
+    {
+      return y_.size();
+    }
+
+    int GetY(size_t i) const
+    {
+      return y_[i];
+    }
+
+    int GetX1(size_t i) const
+    {
+      return x1_[i];
+    }
+
+    int GetX2(size_t i) const
+    {
+      return x2_[i];
+    }
+  };
+}
+
+
+TEST(ImageProcessing, FillPolygon)
+{
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(0u, segments.GetSize());
+  }
+
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(288, 208));
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(0u, segments.GetSize());
+  }
+
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(10, 100));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(50, 100));
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(1u, segments.GetSize());
+    ASSERT_EQ(100, segments.GetY(0));
+    ASSERT_EQ(10, segments.GetX1(0));
+    ASSERT_EQ(50, segments.GetX2(0));
+  }
+
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(10, 100));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(10, 101));
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(2u, segments.GetSize());
+    ASSERT_EQ(100, segments.GetY(0));
+    ASSERT_EQ(10, segments.GetX1(0));
+    ASSERT_EQ(10, segments.GetX2(0));
+    ASSERT_EQ(101, segments.GetY(1));
+    ASSERT_EQ(10, segments.GetX1(1));
+    ASSERT_EQ(10, segments.GetX2(1));
+  }
+
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(10, 100));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(11, 101));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(13, 103));
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(4u, segments.GetSize());
+    ASSERT_EQ(100, segments.GetY(0));
+    ASSERT_EQ(10, segments.GetX1(0));
+    ASSERT_EQ(10, segments.GetX2(0));
+    ASSERT_EQ(101, segments.GetY(1));
+    ASSERT_EQ(11, segments.GetX1(1));
+    ASSERT_EQ(11, segments.GetX2(1));
+    ASSERT_EQ(102, segments.GetY(2));
+    ASSERT_EQ(12, segments.GetX1(2));
+    ASSERT_EQ(12, segments.GetX2(2));
+    ASSERT_EQ(103, segments.GetY(3));
+    ASSERT_EQ(13, segments.GetX1(3));
+    ASSERT_EQ(13, segments.GetX2(3));
+  }
+
+  {
+    std::vector<Orthanc::ImageProcessing::ImagePoint> polygon;
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(5, 5));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(7, 7));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(9, 5));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(9, 8));
+    polygon.push_back(Orthanc::ImageProcessing::ImagePoint(5, 8));
+
+    PolygonSegments segments;
+    Orthanc::ImageProcessing::FillPolygon(segments, polygon);
+    ASSERT_EQ(6u, segments.GetSize());
+    ASSERT_EQ(5, segments.GetY(0));  ASSERT_EQ(5, segments.GetX1(0));  ASSERT_EQ(5, segments.GetX2(0));
+    ASSERT_EQ(5, segments.GetY(1));  ASSERT_EQ(9, segments.GetX1(1));  ASSERT_EQ(9, segments.GetX2(1));
+    ASSERT_EQ(6, segments.GetY(2));  ASSERT_EQ(5, segments.GetX1(2));  ASSERT_EQ(6, segments.GetX2(2));
+    ASSERT_EQ(6, segments.GetY(3));  ASSERT_EQ(8, segments.GetX1(3));  ASSERT_EQ(9, segments.GetX2(3));
+    ASSERT_EQ(7, segments.GetY(4));  ASSERT_EQ(5, segments.GetX1(4));  ASSERT_EQ(9, segments.GetX2(4));
+    ASSERT_EQ(8, segments.GetY(5));  ASSERT_EQ(5, segments.GetX1(5));  ASSERT_EQ(9, segments.GetX2(5));
+  }
+}