# HG changeset patch
# User Alain Mazy <alain@mazy.be>
# Date 1550511820 -3600
# Node ID 6f652c7bfc85b042b27d96b77cdf99fabf8098fc
# Parent  5d1f998b0b18402d43ce734c4c176de1c2c5a1f8
ImageProcessing::FillPolygon

diff -r 5d1f998b0b18 -r 6f652c7bfc85 Core/Images/ImageProcessing.cpp
--- a/Core/Images/ImageProcessing.cpp	Mon Feb 18 12:18:15 2019 +0100
+++ b/Core/Images/ImageProcessing.cpp	Mon Feb 18 18:43:40 2019 +0100
@@ -43,6 +43,7 @@
 #include <string.h>
 #include <limits>
 #include <stdint.h>
+#include <algorithm>
 
 namespace Orthanc
 {
@@ -1364,4 +1365,144 @@
       throw Orthanc::OrthancException(Orthanc::ErrorCode_NotImplemented);
     }
   }
+
+  void ComputePolygonExtent(int32_t& left, int32_t& right, int32_t& top, int32_t& bottom, const std::vector<ImageProcessing::ImagePoint>& points)
+  {
+    left = std::numeric_limits<int32_t>::max();
+    right = std::numeric_limits<int32_t>::min();
+    top = std::numeric_limits<int32_t>::max();
+    bottom = std::numeric_limits<int32_t>::min();
+
+    for (size_t i = 0; i < points.size(); i++)
+    {
+      const ImageProcessing::ImagePoint& p = points[i];
+      left = std::min(p.GetX(), left);
+      right = std::max(p.GetX(), right);
+      bottom = std::max(p.GetY(), bottom);
+      top = std::min(p.GetY(), top);
+    }
+  }
+
+  template <PixelFormat TargetFormat>
+  void FillPolygon_(ImageAccessor& image,
+              const std::vector<ImageProcessing::ImagePoint>& points,
+              int64_t value_)
+  {
+    typedef typename PixelTraits<TargetFormat>::PixelType  TargetType;
+
+    TargetType value = PixelTraits<TargetFormat>::IntegerToPixel(value_);
+    int32_t left;
+    int32_t right;
+    int32_t top;
+    int32_t bottom;
+
+    ComputePolygonExtent(left, right, top, bottom, points);
+
+    // from http://alienryderflex.com/polygon_fill/
+
+    // convert all "corner"  points to double only once
+    std::vector<double> cpx;
+    std::vector<double> cpy;
+    size_t cpSize = points.size();
+    for (size_t i = 0; i < points.size(); i++)
+    {
+      cpx.push_back((double)points[i].GetX());
+      cpy.push_back((double)points[i].GetY());
+    }
+
+    std::vector<int32_t> nodeX;
+    nodeX.resize(cpSize);
+    int  nodes, pixelX, pixelY, i, j, swap ;
+
+    //  Loop through the rows of the image.
+    for (pixelY = top; pixelY < bottom; pixelY++)
+    {
+      double y = (double)pixelY;
+      //  Build a list of nodes.
+      nodes = 0;
+      j = static_cast<int>(cpSize) - 1;
+
+      for (i = 0; i < cpSize; i++)
+      {
+        if ((cpy[i] < y && cpy[j] >=  y) || (cpy[j] < y && cpy[i] >= y))
+        {
+          nodeX[nodes++] = (int32_t)(cpx[i] + (y - cpy[i])/(cpy[j] - cpy[i]) * (cpx[j] - cpx[i]));
+        }
+        j=i;
+      }
+
+      //  Sort the nodes, via a simple “Bubble” sort.
+      i=0;
+      while (i < nodes-1)
+      {
+        if (nodeX[i] > nodeX[i+1])
+        {
+          swap = nodeX[i];
+          nodeX[i] = nodeX[i+1];
+          nodeX[i+1] = swap;
+          if (i > 0)
+          {
+            i--;
+          }
+        }
+        else
+        {
+          i++;
+        }
+      }
+
+      TargetType* row = reinterpret_cast<TargetType*>(image.GetRow(pixelY));
+      //  Fill the pixels between node pairs.
+      for (i=0; i<nodes; i+=2)
+      {
+        if (nodeX[i] >= right)
+          break;
+
+        if (nodeX[i+1] >= left)
+        {
+          if (nodeX[i]< left)
+          {
+            nodeX[i] = left;
+          }
+
+          if (nodeX[i+1] > right)
+          {
+            nodeX[i+1] = right;
+          }
+
+          for (pixelX = nodeX[i]; pixelX <= nodeX[i+1]; pixelX++)
+          {
+            *(row + pixelX) = value;
+          }
+        }
+      }
+    }
+  }
+
+  void ImageProcessing::FillPolygon(ImageAccessor& image,
+                                    const std::vector<ImagePoint>& points,
+                                    int64_t value)
+  {
+    switch (image.GetFormat())
+    {
+    case Orthanc::PixelFormat_Grayscale8:
+    {
+      FillPolygon_<Orthanc::PixelFormat_Grayscale8>(image, points, value);
+      break;
+    }
+    case Orthanc::PixelFormat_Grayscale16:
+    {
+      FillPolygon_<Orthanc::PixelFormat_Grayscale16>(image, points, value);
+      break;
+    }
+    case Orthanc::PixelFormat_SignedGrayscale16:
+    {
+      FillPolygon_<Orthanc::PixelFormat_SignedGrayscale16>(image, points, value);
+      break;
+    }
+    default:
+      throw Orthanc::OrthancException(Orthanc::ErrorCode_NotImplemented);
+    }
+  }
+
 }
diff -r 5d1f998b0b18 -r 6f652c7bfc85 Core/Images/ImageProcessing.h
--- a/Core/Images/ImageProcessing.h	Mon Feb 18 12:18:15 2019 +0100
+++ b/Core/Images/ImageProcessing.h	Mon Feb 18 18:43:40 2019 +0100
@@ -34,6 +34,7 @@
 #pragma once
 
 #include "ImageAccessor.h"
+#include <vector>
 
 #include <stdint.h>
 
@@ -41,6 +42,22 @@
 {
   namespace ImageProcessing
   {
+    class ImagePoint
+    {
+      int32_t x_;
+      int32_t y_;
+      
+     public:
+      ImagePoint(int32_t x, int32_t y)
+        : x_(x),
+          y_(y)
+      {
+      }
+
+      int32_t GetX() const {return x_;}
+      int32_t GetY() const {return y_;}
+    };
+
     void Copy(ImageAccessor& target,
               const ImageAccessor& source);
 
@@ -101,5 +118,9 @@
                          uint8_t green,
                          uint8_t blue,
                          uint8_t alpha);
+
+    void FillPolygon(ImageAccessor& image,
+                     const std::vector<ImagePoint>& points,
+                     int64_t value);
   }
 }
diff -r 5d1f998b0b18 -r 6f652c7bfc85 UnitTestsSources/ImageProcessingTests.cpp
--- a/UnitTestsSources/ImageProcessingTests.cpp	Mon Feb 18 12:18:15 2019 +0100
+++ b/UnitTestsSources/ImageProcessingTests.cpp	Mon Feb 18 18:43:40 2019 +0100
@@ -180,7 +180,7 @@
   
   memset(image.GetBuffer(), 128, image.GetHeight() * image.GetWidth());
 
-  unsigned int c = 0;
+  float c = 0.0f;
   for (unsigned int y = 0; y < image.GetHeight(); y++)
   {
     for (unsigned int x = 0; x < image.GetWidth(); x++, c++)
@@ -189,7 +189,6 @@
     }
   }
 
-  c = 0;
   for (unsigned int y = 0; y < image.GetHeight(); y++)
   {
     for (unsigned int x = 0; x < image.GetWidth(); x++, c++)
@@ -198,3 +197,28 @@
     }
   }
 }
+
+TYPED_TEST(TestIntegerImageTraits, FillPolygon)
+{
+  ImageAccessor& image = this->GetImage();
+
+  ImageProcessing::Set(image, 128);
+
+  // draw a triangle
+  std::vector<ImageProcessing::ImagePoint> points;
+  points.push_back(ImageProcessing::ImagePoint(1,1));
+  points.push_back(ImageProcessing::ImagePoint(1,5));
+  points.push_back(ImageProcessing::ImagePoint(5,5));
+
+  Orthanc::ImageProcessing::FillPolygon(image, points, 255);
+
+  // outside polygon
+  ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 0, 0));
+  ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 0, 6));
+  ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 6, 6));
+  ASSERT_FLOAT_EQ(128, TestFixture::ImageTraits::GetFloatPixel(image, 6, 0));
+
+  // inside polygon (note: we don't test too close from the edges since the current algo is taking some margin from the edges and might be improved in that sense)
+  ASSERT_FLOAT_EQ(255, TestFixture::ImageTraits::GetFloatPixel(image, 1, 2));
+  ASSERT_FLOAT_EQ(255, TestFixture::ImageTraits::GetFloatPixel(image, 2, 4));
+}