Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/UnionOfRectangles.cpp @ 2097:a9e23ef9ee09 dicom-sr
preparing to extract dicom-sr annotations
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Wed, 08 Nov 2023 16:31:49 +0100 |
parents | 07964689cb0b |
children | c23eef785569 |
rev | line source |
---|---|
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
1 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
2 * Stone of Orthanc |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
4 * Department, University Hospital of Liege, Belgium |
2077
07964689cb0b
upgrade to year 2023
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1906
diff
changeset
|
5 * Copyright (C) 2017-2023 Osimis S.A., Belgium |
07964689cb0b
upgrade to year 2023
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1906
diff
changeset
|
6 * Copyright (C) 2021-2023 Sebastien Jodogne, ICTEAM UCLouvain, Belgium |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
7 * |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
8 * This program is free software: you can redistribute it and/or |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
9 * modify it under the terms of the GNU Lesser General Public License |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
10 * as published by the Free Software Foundation, either version 3 of |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
11 * the License, or (at your option) any later version. |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
12 * |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
13 * This program is distributed in the hope that it will be useful, but |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
14 * WITHOUT ANY WARRANTY; without even the implied warranty of |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
16 * Lesser General Public License for more details. |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
17 * |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
18 * You should have received a copy of the GNU Lesser General Public |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
19 * License along with this program. If not, see |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
20 * <http://www.gnu.org/licenses/>. |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
21 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
22 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
23 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
24 #include "UnionOfRectangles.h" |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
25 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
26 #include "Internals/OrientedIntegerLine2D.h" |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
27 #include "Internals/RectanglesIntegerProjection.h" |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
28 #include "SegmentTree.h" |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
29 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
30 #include <OrthancException.h> |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
31 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
32 #include <stack> |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
33 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
34 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
35 namespace OrthancStone |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
36 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
37 class UnionOfRectangles::Payload : public Orthanc::IDynamicObject |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
38 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
39 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
40 int counter_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
41 Status status_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
42 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
43 public: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
44 Payload() : |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
45 counter_(0), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
46 status_(Status_Empty) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
47 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
48 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
49 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
50 int GetCounter() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
51 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
52 return counter_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
53 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
54 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
55 Status GetStatus() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
56 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
57 return status_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
58 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
59 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
60 void SetStatus(Status status) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
61 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
62 status_ = status; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
63 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
64 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
65 void Increment() |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
66 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
67 counter_ ++; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
68 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
69 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
70 void Decrement() |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
71 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
72 if (counter_ == 0) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
73 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
74 throw Orthanc::OrthancException(Orthanc::ErrorCode_InternalError); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
75 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
76 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
77 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
78 counter_ --; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
79 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
80 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
81 }; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
82 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
83 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
84 class UnionOfRectangles::Factory : public SegmentTree::IPayloadFactory |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
85 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
86 public: |
1876 | 87 virtual Orthanc::IDynamicObject* Create() ORTHANC_OVERRIDE |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
88 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
89 return new Payload; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
90 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
91 }; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
92 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
93 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
94 class UnionOfRectangles::Visitor : public SegmentTree::IVisitor |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
95 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
96 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
97 Operation operation_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
98 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
99 public: |
1878 | 100 explicit Visitor(Operation operation) : |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
101 operation_(operation) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
102 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
103 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
104 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
105 virtual void Visit(const SegmentTree& node, |
1876 | 106 bool fullyInside) ORTHANC_OVERRIDE |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
107 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
108 Payload& payload = node.GetTypedPayload<Payload>(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
109 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
110 if (fullyInside) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
111 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
112 switch (operation_) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
113 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
114 case Operation_Insert: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
115 payload.Increment(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
116 break; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
117 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
118 case Operation_Delete: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
119 payload.Decrement(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
120 break; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
121 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
122 default: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
123 throw Orthanc::OrthancException(Orthanc::ErrorCode_InternalError); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
124 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
125 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
126 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
127 if (payload.GetCounter() > 0) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
128 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
129 payload.SetStatus(Status_Full); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
130 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
131 else if (node.IsLeaf()) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
132 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
133 payload.SetStatus(Status_Empty); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
134 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
135 else if (node.GetLeftChild().GetTypedPayload<Payload>().GetStatus() == Status_Empty && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
136 node.GetRightChild().GetTypedPayload<Payload>().GetStatus() == Status_Empty) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
137 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
138 payload.SetStatus(Status_Empty); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
139 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
140 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
141 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
142 payload.SetStatus(Status_Partial); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
143 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
144 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
145 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
146 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
147 // This is the "CONTR()" function from the textbook |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
148 static void IntersectComplement(std::stack<size_t>& stack, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
149 size_t low, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
150 size_t high, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
151 const SegmentTree& node) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
152 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
153 if (low >= high) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
154 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
155 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
156 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
157 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
158 Status status = node.GetTypedPayload<Payload>().GetStatus(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
159 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
160 if (status != Status_Full) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
161 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
162 assert(status == Status_Partial || |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
163 status == Status_Empty); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
164 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
165 // Aliases to use the same variable names as in the textbook |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
166 const size_t& b = low; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
167 const size_t& e = high; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
168 const size_t& bv = node.GetLowBound(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
169 const size_t& ev = node.GetHighBound(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
170 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
171 if (b <= bv && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
172 ev <= e && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
173 status == Status_Empty) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
174 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
175 // [B[v], E[v]] is contributed |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
176 if (!stack.empty() && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
177 stack.top() == bv) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
178 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
179 stack.pop(); // Merge continuous segments |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
180 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
181 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
182 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
183 stack.push(bv); // Beginning of edge |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
184 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
185 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
186 stack.push(ev); // Current termination of edge |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
187 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
188 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
189 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
190 size_t middle = (bv + ev) / 2; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
191 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
192 if (b < middle) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
193 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
194 IntersectComplement(stack, b, e, node.GetLeftChild()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
195 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
196 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
197 if (middle < e) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
198 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
199 IntersectComplement(stack, b, e, node.GetRightChild()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
200 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
201 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
202 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
203 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
204 }; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
205 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
206 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
207 static void AddVerticalEdges(std::list<Internals::OrientedIntegerLine2D>& edges, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
208 std::stack<size_t>& stack, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
209 size_t x, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
210 bool isLeft) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
211 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
212 if (stack.size() % 2 != 0) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
213 { |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
214 throw Orthanc::OrthancException(Orthanc::ErrorCode_InternalError); |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
215 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
216 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
217 typedef std::pair<size_t, size_t> Interval; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
218 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
219 std::list<Interval> intervals; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
220 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
221 while (!stack.empty()) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
222 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
223 size_t high = stack.top(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
224 stack.pop(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
225 size_t low = stack.top(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
226 stack.pop(); |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
227 |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
228 if (!intervals.empty() && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
229 intervals.back().second == low) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
230 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
231 // Extend the previous interval |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
232 intervals.back().second = high; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
233 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
234 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
235 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
236 intervals.push_back(std::make_pair(low, high)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
237 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
238 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
239 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
240 for (std::list<Interval>::const_iterator |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
241 it = intervals.begin(); it != intervals.end(); ++it) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
242 { |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
243 if (it->first >= it->second) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
244 { |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
245 throw Orthanc::OrthancException(Orthanc::ErrorCode_ParameterOutOfRange); |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
246 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
247 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
248 // By convention, the left sides go downward, and the right go upward |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
249 if (isLeft) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
250 { |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
251 if (!edges.empty() && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
252 edges.back().GetX1() == x && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
253 edges.back().GetX2() == x && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
254 edges.back().GetY1() == it->second && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
255 edges.back().GetY2() == it->first) |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
256 { |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
257 // The two successive vertical segments cancel each other |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
258 edges.pop_back(); |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
259 } |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
260 else |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
261 { |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
262 edges.push_back(Internals::OrientedIntegerLine2D(x, it->first, x, it->second)); |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
263 } |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
264 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
265 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
266 { |
1906
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
267 if (!edges.empty() && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
268 edges.back().GetX1() == x && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
269 edges.back().GetX2() == x && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
270 edges.back().GetY1() == it->first && |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
271 edges.back().GetY2() == it->second) |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
272 { |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
273 // The two successive vertical segments cancel each other |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
274 edges.pop_back(); |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
275 } |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
276 else |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
277 { |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
278 edges.push_back(Internals::OrientedIntegerLine2D(x, it->second, x, it->first)); |
925aaf49150c
minor fix in UnionOfRectangles
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1905
diff
changeset
|
279 } |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
280 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
281 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
282 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
283 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
284 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
285 class UnionOfRectangles::VerticalSide |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
286 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
287 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
288 size_t x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
289 bool isLeft_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
290 size_t y1_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
291 size_t y2_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
292 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
293 public: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
294 VerticalSide(size_t x, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
295 bool isLeft, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
296 size_t y1, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
297 size_t y2) : |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
298 x_(x), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
299 isLeft_(isLeft), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
300 y1_(y1), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
301 y2_(y2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
302 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
303 assert(y1 < y2); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
304 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
305 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
306 size_t GetX() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
307 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
308 return x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
309 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
310 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
311 bool IsLeft() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
312 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
313 return isLeft_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
314 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
315 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
316 size_t GetY1() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
317 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
318 return y1_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
319 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
320 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
321 size_t GetY2() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
322 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
323 return y2_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
324 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
325 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
326 bool operator< (const VerticalSide& other) const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
327 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
328 if (x_ < other.x_) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
329 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
330 return true; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
331 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
332 else if (x_ == other.x_) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
333 { |
1905
e318b524ad3f
use UnionOfRectangles algorithm to render RT-STRUCT
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
1878
diff
changeset
|
334 return static_cast<int>(isLeft_) < static_cast<int>(other.isLeft_); |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
335 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
336 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
337 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
338 return false; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
339 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
340 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
341 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
342 bool Equals(const VerticalSide& other) const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
343 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
344 return (x_ == other.x_ && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
345 isLeft_ == other.isLeft_); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
346 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
347 }; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
348 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
349 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
350 class UnionOfRectangles::HorizontalJunction |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
351 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
352 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
353 size_t x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
354 size_t y_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
355 size_t ybis_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
356 bool downward_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
357 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
358 public: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
359 HorizontalJunction(size_t x, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
360 size_t y, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
361 size_t ybis, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
362 bool downward) : |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
363 x_(x), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
364 y_(y), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
365 ybis_(ybis), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
366 downward_(downward) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
367 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
368 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
369 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
370 size_t GetX() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
371 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
372 return x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
373 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
374 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
375 size_t GetY() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
376 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
377 return y_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
378 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
379 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
380 size_t GetYBis() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
381 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
382 return ybis_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
383 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
384 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
385 bool IsDownward() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
386 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
387 return downward_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
388 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
389 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
390 bool operator< (const HorizontalJunction& other) const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
391 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
392 if (y_ > other.y_) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
393 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
394 return true; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
395 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
396 else if (y_ == other.y_) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
397 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
398 return x_ < other.x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
399 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
400 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
401 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
402 return false; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
403 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
404 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
405 }; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
406 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
407 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
408 void UnionOfRectangles::Apply(std::list< std::vector<ScenePoint2D> >& contours, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
409 const std::list<Extent2D>& rectangles) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
410 { |
1876 | 411 contours.clear(); |
412 | |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
413 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
414 * STEP 1 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
415 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
416 Internals::RectanglesIntegerProjection horizontalProjection(rectangles, true); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
417 Internals::RectanglesIntegerProjection verticalProjection(rectangles, false); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
418 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
419 assert(horizontalProjection.GetProjectedRectanglesCount() == verticalProjection.GetProjectedRectanglesCount()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
420 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
421 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
422 * STEP 2 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
423 **/ |
1876 | 424 if (verticalProjection.GetEndpointsCount() == 0) |
425 { | |
426 return; | |
427 } | |
428 | |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
429 Factory factory; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
430 SegmentTree tree(0, verticalProjection.GetEndpointsCount() - 1, factory); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
431 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
432 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
433 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
434 * STEP 3 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
435 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
436 std::vector<VerticalSide> verticalSides; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
437 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
438 const size_t countRectangles = horizontalProjection.GetProjectedRectanglesCount(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
439 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
440 verticalSides.reserve(2 * countRectangles); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
441 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
442 for (size_t i = 0; i < countRectangles; i++) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
443 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
444 size_t horizontalLow = horizontalProjection.GetProjectedRectangleLow(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
445 size_t horizontalHigh = horizontalProjection.GetProjectedRectangleHigh(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
446 size_t verticalLow = verticalProjection.GetProjectedRectangleLow(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
447 size_t verticalHigh = verticalProjection.GetProjectedRectangleHigh(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
448 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
449 verticalSides.push_back(VerticalSide(horizontalLow, true, verticalLow, verticalHigh)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
450 verticalSides.push_back(VerticalSide(horizontalHigh, false, verticalLow, verticalHigh)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
451 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
452 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
453 assert(verticalSides.size() == 2 * countRectangles); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
454 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
455 std::sort(verticalSides.begin(), verticalSides.end()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
456 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
457 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
458 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
459 * STEP 4 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
460 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
461 std::list<Internals::OrientedIntegerLine2D> verticalEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
462 std::stack<size_t> stack; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
463 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
464 for (size_t i = 0; i < verticalSides.size(); i++) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
465 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
466 if (i > 0 && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
467 !verticalSides[i].Equals(verticalSides[i - 1])) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
468 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
469 // Output the stack |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
470 AddVerticalEdges(verticalEdges, stack, verticalSides[i - 1].GetX(), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
471 verticalSides[i - 1].IsLeft()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
472 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
473 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
474 size_t y1 = verticalSides[i].GetY1(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
475 size_t y2 = verticalSides[i].GetY2(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
476 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
477 if (verticalSides[i].IsLeft()) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
478 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
479 Visitor::IntersectComplement(stack, y1, y2, tree); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
480 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
481 Visitor visitor(Operation_Insert); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
482 tree.VisitSegment(y1, y2, visitor); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
483 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
484 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
485 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
486 Visitor visitor(Operation_Delete); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
487 tree.VisitSegment(y1, y2, visitor); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
488 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
489 Visitor::IntersectComplement(stack, y1, y2, tree); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
490 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
491 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
492 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
493 if (!verticalSides.empty() && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
494 !stack.empty()) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
495 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
496 AddVerticalEdges(verticalEdges, stack, verticalSides.back().GetX(), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
497 verticalSides.back().IsLeft()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
498 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
499 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
500 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
501 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
502 * STEP 5: Horizontal edges |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
503 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
504 std::vector<HorizontalJunction> horizontalJunctions; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
505 horizontalJunctions.reserve(2 * verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
506 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
507 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 508 it = verticalEdges.begin(); it != verticalEdges.end(); ++it) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
509 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
510 assert(it->GetX1() == it->GetX2()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
511 horizontalJunctions.push_back(HorizontalJunction(it->GetX1(), it->GetY1(), it->GetY2(), it->IsDownward())); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
512 horizontalJunctions.push_back(HorizontalJunction(it->GetX1(), it->GetY2(), it->GetY1(), it->IsDownward())); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
513 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
514 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
515 assert(horizontalJunctions.size() == 2 * verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
516 std::sort(horizontalJunctions.begin(), horizontalJunctions.end()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
517 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
518 std::list<Internals::OrientedIntegerLine2D> horizontalEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
519 for (size_t i = 0; i < horizontalJunctions.size(); i += 2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
520 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
521 size_t x1 = horizontalJunctions[i].GetX(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
522 size_t x2 = horizontalJunctions[i + 1].GetX(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
523 size_t y = horizontalJunctions[i].GetY(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
524 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
525 if ((horizontalJunctions[i].IsDownward() && y > horizontalJunctions[i].GetYBis()) || |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
526 (!horizontalJunctions[i].IsDownward() && y < horizontalJunctions[i].GetYBis())) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
527 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
528 horizontalEdges.push_back(Internals::OrientedIntegerLine2D(x1, y, x2, y)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
529 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
530 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
531 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
532 horizontalEdges.push_back(Internals::OrientedIntegerLine2D(x2, y, x1, y)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
533 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
534 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
535 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
536 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
537 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
538 * POST-PROCESSING: Combine the separate sets of horizontal and |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
539 * vertical edges, into a set of 2D chains |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
540 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
541 std::vector<Internals::OrientedIntegerLine2D> allEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
542 allEdges.reserve(horizontalEdges.size() + verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
543 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
544 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 545 it = horizontalEdges.begin(); it != horizontalEdges.end(); ++it) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
546 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
547 allEdges.push_back(*it); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
548 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
549 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
550 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 551 it = verticalEdges.begin(); it != verticalEdges.end(); ++it) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
552 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
553 allEdges.push_back(*it); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
554 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
555 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
556 assert(allEdges.size() == horizontalEdges.size() + verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
557 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
558 std::list<Internals::OrientedIntegerLine2D::Chain> chains; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
559 Internals::OrientedIntegerLine2D::ExtractChains(chains, allEdges); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
560 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
561 for (std::list<Internals::OrientedIntegerLine2D::Chain>::const_iterator |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
562 it = chains.begin(); it != chains.end(); ++it) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
563 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
564 assert(!it->empty()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
565 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
566 std::vector<ScenePoint2D> chain; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
567 chain.reserve(it->size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
568 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
569 for (Internals::OrientedIntegerLine2D::Chain::const_iterator |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
570 it2 = it->begin(); it2 != it->end(); ++it2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
571 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
572 chain.push_back(ScenePoint2D(horizontalProjection.GetEndpointCoordinate(it2->first), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
573 verticalProjection.GetEndpointCoordinate(it2->second))); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
574 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
575 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
576 assert(!chain.empty()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
577 contours.push_back(chain); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
578 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
579 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
580 } |