--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.cpp	Tue Jan 11 18:58:37 2022 +0100
@@ -0,0 +1,99 @@
+/**
+ * Stone of Orthanc
+ * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
+ * Department, University Hospital of Liege, Belgium
+ * Copyright (C) 2017-2022 Osimis S.A., Belgium
+ * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
+ *
+ * This program is free software: you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public License
+ * as published by the Free Software Foundation, either version 3 of
+ * the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this program. If not, see
+ * <http://www.gnu.org/licenses/>.
+ **/
+
+
+#include "OrientedIntegerLine2D.h"
+
+#include <cassert>
+#include <map>
+
+
+namespace OrthancStone
+{
+  namespace Internals
+  {
+    OrientedIntegerLine2D::OrientedIntegerLine2D(size_t x1,
+                                                 size_t y1,
+                                                 size_t x2,
+                                                 size_t y2) :
+      x1_(x1),
+      y1_(y1),
+      x2_(x2),
+      y2_(y2)
+    {
+    }
+
+    void OrientedIntegerLine2D::ExtractChains(std::list<Chain>& chains,
+                                              const std::vector<OrientedIntegerLine2D>& edges)
+    {
+      chains.clear();
+      
+      typedef std::map< std::pair<size_t, size_t>, std::list<size_t> > Index;
+      Index index;
+
+      for (size_t i = 0; i < edges.size(); i++)
+      {
+        index[std::make_pair(edges[i].GetX1(), edges[i].GetY1())].push_back(i);
+      }
+
+      std::vector<bool> visited(edges.size(), false);
+
+      for (size_t i = 0; i < edges.size(); i++)
+      {
+        if (!visited[i])
+        {
+          Chain chain;
+          
+          size_t current = i;
+          
+          chain.push_back(std::make_pair(edges[current].GetX1(), edges[current].GetY1()));
+          
+          for (;;)
+          {
+            visited[current] = true;
+
+            std::pair<size_t, size_t> start(edges[current].GetX1(), edges[current].GetY1());
+            std::pair<size_t, size_t> end(edges[current].GetX2(), edges[current].GetY2());
+            
+            assert(index.find(start) != index.end());
+            index[start].pop_back();
+            
+            chain.push_back(end);
+            Index::iterator next = index.find(end);
+
+            if (next == index.end() /* non-closed chain */ ||
+                next->second.empty())
+            {
+              break;
+            }
+            else
+            {
+              current = next->second.back();
+            }
+          }
+          
+          chains.push_back(chain);
+        }
+      }
+    }
+  }
+}