Mercurial > hg > orthanc-stone

annotate OrthancStone/Sources/Toolbox/Internals/OrientedIntegerLine2D.cpp @ 2140:04211f6fd304 default tip

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