Mercurial > hg > orthanc-stone

comparison OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.cpp @ 1874:08f2476e8f5e

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added classes OrientedIntegerLine2D and RectanglesIntegerProjection
author Sebastien Jodogne <s.jodogne@gmail.com>
date Tue, 11 Jan 2022 18:58:37 +0100
parents
children 07964689cb0b
comparison
equal deleted inserted replaced
1873:e0966648ebd0 1874:08f2476e8f5e
1 /**
2 * Stone of Orthanc
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
4 * Department, University Hospital of Liege, Belgium
5 * Copyright (C) 2017-2022 Osimis S.A., Belgium
6 * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium
7 *
8 * This program is free software: you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public License
10 * as published by the Free Software Foundation, either version 3 of
11 * the License, or (at your option) any later version.
12 *
13 * This program is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this program. If not, see
20 * <http://www.gnu.org/licenses/>.
21 **/
22
23
24 #include "OrientedIntegerLine2D.h"
25
26 #include <cassert>
27 #include <map>
28
29
30 namespace OrthancStone
31 {
32 namespace Internals
33 {
34 OrientedIntegerLine2D::OrientedIntegerLine2D(size_t x1,
35 size_t y1,
36 size_t x2,
37 size_t y2) :
38 x1_(x1),
39 y1_(y1),
40 x2_(x2),
41 y2_(y2)
42 {
43 }
44
45 void OrientedIntegerLine2D::ExtractChains(std::list<Chain>& chains,
46 const std::vector<OrientedIntegerLine2D>& edges)
47 {
48 chains.clear();
49
50 typedef std::map< std::pair<size_t, size_t>, std::list<size_t> > Index;
51 Index index;
52
53 for (size_t i = 0; i < edges.size(); i++)
54 {
55 index[std::make_pair(edges[i].GetX1(), edges[i].GetY1())].push_back(i);
56 }
57
58 std::vector<bool> visited(edges.size(), false);
59
60 for (size_t i = 0; i < edges.size(); i++)
61 {
62 if (!visited[i])
63 {
64 Chain chain;
65
66 size_t current = i;
67
68 chain.push_back(std::make_pair(edges[current].GetX1(), edges[current].GetY1()));
69
70 for (;;)
71 {
72 visited[current] = true;
73
74 std::pair<size_t, size_t> start(edges[current].GetX1(), edges[current].GetY1());
75 std::pair<size_t, size_t> end(edges[current].GetX2(), edges[current].GetY2());
76
77 assert(index.find(start) != index.end());
78 index[start].pop_back();
79
80 chain.push_back(end);
81 Index::iterator next = index.find(end);
82
83 if (next == index.end() /* non-closed chain */ ||
84 next->second.empty())
85 {
86 break;
87 }
88 else
89 {
90 current = next->second.back();
91 }
92 }
93
94 chains.push_back(chain);
95 }
96 }
97 }
98 }
99 }