Mercurial > hg > orthanc-stone
annotate OrthancStone/Sources/Toolbox/UnionOfRectangles.cpp @ 1894:438071a29f77
xor polygon filler for holes in rt-struct
author | Sebastien Jodogne <s.jodogne@gmail.com> |
---|---|
date | Wed, 19 Jan 2022 14:25:59 +0100 |
parents | c9ccd13c6a3c |
children | e318b524ad3f |
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 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
5 * Copyright (C) 2017-2022 Osimis S.A., Belgium |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
6 * Copyright (C) 2021-2022 Sebastien Jodogne, ICTEAM UCLouvain, Belgium |
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 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
214 throw std::runtime_error("internal error"); |
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(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
227 |
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 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
243 if (it->first == it->second) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
244 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
245 throw std::runtime_error("parameter out of range"); |
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 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
251 edges.push_back(Internals::OrientedIntegerLine2D(x, it->first, x, it->second)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
252 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
253 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
254 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
255 edges.push_back(Internals::OrientedIntegerLine2D(x, it->second, x, it->first)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
256 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
257 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
258 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
259 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
260 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
261 class UnionOfRectangles::VerticalSide |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
262 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
263 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
264 size_t x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
265 bool isLeft_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
266 size_t y1_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
267 size_t y2_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
268 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
269 public: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
270 VerticalSide(size_t x, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
271 bool isLeft, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
272 size_t y1, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
273 size_t y2) : |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
274 x_(x), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
275 isLeft_(isLeft), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
276 y1_(y1), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
277 y2_(y2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
278 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
279 assert(y1 < y2); |
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 size_t GetX() const |
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 return x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
285 } |
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 bool IsLeft() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
288 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
289 return isLeft_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
290 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
291 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
292 size_t GetY1() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
293 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
294 return y1_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
295 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
296 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
297 size_t GetY2() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
298 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
299 return y2_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
300 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
301 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
302 bool operator< (const VerticalSide& other) const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
303 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
304 if (x_ < other.x_) |
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 return true; |
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 else if (x_ == other.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 return isLeft_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
311 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
312 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
313 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
314 return false; |
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 } |
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 bool Equals(const VerticalSide& other) const |
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 return (x_ == other.x_ && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
321 isLeft_ == other.isLeft_); |
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 }; |
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 class UnionOfRectangles::HorizontalJunction |
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 private: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
329 size_t x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
330 size_t y_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
331 size_t ybis_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
332 bool downward_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
333 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
334 public: |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
335 HorizontalJunction(size_t x, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
336 size_t y, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
337 size_t ybis, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
338 bool downward) : |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
339 x_(x), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
340 y_(y), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
341 ybis_(ybis), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
342 downward_(downward) |
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 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
345 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
346 size_t GetX() const |
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 return x_; |
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 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
351 size_t GetY() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
352 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
353 return y_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
354 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
355 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
356 size_t GetYBis() const |
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 return ybis_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
359 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
360 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
361 bool IsDownward() const |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
362 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
363 return downward_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
364 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
365 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
366 bool operator< (const HorizontalJunction& other) const |
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 if (y_ > other.y_) |
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 return true; |
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 else if (y_ == other.y_) |
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 return x_ < other.x_; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
375 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
376 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
377 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
378 return false; |
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 } |
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 |
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 void UnionOfRectangles::Apply(std::list< std::vector<ScenePoint2D> >& contours, |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
385 const std::list<Extent2D>& rectangles) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
386 { |
1876 | 387 contours.clear(); |
388 | |
1875
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 * STEP 1 |
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 Internals::RectanglesIntegerProjection horizontalProjection(rectangles, true); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
393 Internals::RectanglesIntegerProjection verticalProjection(rectangles, false); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
394 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
395 assert(horizontalProjection.GetProjectedRectanglesCount() == verticalProjection.GetProjectedRectanglesCount()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
396 |
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 * STEP 2 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
399 **/ |
1876 | 400 if (verticalProjection.GetEndpointsCount() == 0) |
401 { | |
402 return; | |
403 } | |
404 | |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
405 Factory factory; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
406 SegmentTree tree(0, verticalProjection.GetEndpointsCount() - 1, factory); |
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 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
409 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
410 * STEP 3 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
411 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
412 std::vector<VerticalSide> verticalSides; |
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 const size_t countRectangles = horizontalProjection.GetProjectedRectanglesCount(); |
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 verticalSides.reserve(2 * countRectangles); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
417 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
418 for (size_t i = 0; i < countRectangles; i++) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
419 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
420 size_t horizontalLow = horizontalProjection.GetProjectedRectangleLow(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
421 size_t horizontalHigh = horizontalProjection.GetProjectedRectangleHigh(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
422 size_t verticalLow = verticalProjection.GetProjectedRectangleLow(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
423 size_t verticalHigh = verticalProjection.GetProjectedRectangleHigh(i); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
424 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
425 verticalSides.push_back(VerticalSide(horizontalLow, true, verticalLow, verticalHigh)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
426 verticalSides.push_back(VerticalSide(horizontalHigh, false, verticalLow, verticalHigh)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
427 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
428 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
429 assert(verticalSides.size() == 2 * countRectangles); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
430 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
431 std::sort(verticalSides.begin(), verticalSides.end()); |
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 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
435 * STEP 4 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
436 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
437 std::list<Internals::OrientedIntegerLine2D> verticalEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
438 std::stack<size_t> stack; |
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 for (size_t i = 0; i < verticalSides.size(); i++) |
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 if (i > 0 && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
443 !verticalSides[i].Equals(verticalSides[i - 1])) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
444 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
445 // Output the stack |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
446 AddVerticalEdges(verticalEdges, stack, verticalSides[i - 1].GetX(), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
447 verticalSides[i - 1].IsLeft()); |
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 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
450 size_t y1 = verticalSides[i].GetY1(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
451 size_t y2 = verticalSides[i].GetY2(); |
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 if (verticalSides[i].IsLeft()) |
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 Visitor::IntersectComplement(stack, y1, y2, tree); |
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 Visitor visitor(Operation_Insert); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
458 tree.VisitSegment(y1, y2, visitor); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
459 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
460 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
461 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
462 Visitor visitor(Operation_Delete); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
463 tree.VisitSegment(y1, y2, visitor); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
464 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
465 Visitor::IntersectComplement(stack, y1, y2, tree); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
466 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
467 } |
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 if (!verticalSides.empty() && |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
470 !stack.empty()) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
471 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
472 AddVerticalEdges(verticalEdges, stack, verticalSides.back().GetX(), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
473 verticalSides.back().IsLeft()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
474 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
475 |
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 /** |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
478 * STEP 5: Horizontal edges |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
479 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
480 std::vector<HorizontalJunction> horizontalJunctions; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
481 horizontalJunctions.reserve(2 * verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
482 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
483 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 484 it = verticalEdges.begin(); it != verticalEdges.end(); ++it) |
1875
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 assert(it->GetX1() == it->GetX2()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
487 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
|
488 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
|
489 } |
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 assert(horizontalJunctions.size() == 2 * verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
492 std::sort(horizontalJunctions.begin(), horizontalJunctions.end()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
493 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
494 std::list<Internals::OrientedIntegerLine2D> horizontalEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
495 for (size_t i = 0; i < horizontalJunctions.size(); i += 2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
496 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
497 size_t x1 = horizontalJunctions[i].GetX(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
498 size_t x2 = horizontalJunctions[i + 1].GetX(); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
499 size_t y = horizontalJunctions[i].GetY(); |
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 if ((horizontalJunctions[i].IsDownward() && y > horizontalJunctions[i].GetYBis()) || |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
502 (!horizontalJunctions[i].IsDownward() && y < horizontalJunctions[i].GetYBis())) |
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 horizontalEdges.push_back(Internals::OrientedIntegerLine2D(x1, y, x2, y)); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
505 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
506 else |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
507 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
508 horizontalEdges.push_back(Internals::OrientedIntegerLine2D(x2, y, x1, y)); |
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 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
511 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
512 |
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 * POST-PROCESSING: Combine the separate sets of horizontal and |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
515 * vertical edges, into a set of 2D chains |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
516 **/ |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
517 std::vector<Internals::OrientedIntegerLine2D> allEdges; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
518 allEdges.reserve(horizontalEdges.size() + verticalEdges.size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
519 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
520 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 521 it = horizontalEdges.begin(); it != horizontalEdges.end(); ++it) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
522 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
523 allEdges.push_back(*it); |
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 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
526 for (std::list<Internals::OrientedIntegerLine2D>::const_iterator |
1878 | 527 it = verticalEdges.begin(); it != verticalEdges.end(); ++it) |
1875
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
528 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
529 allEdges.push_back(*it); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
530 } |
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 assert(allEdges.size() == horizontalEdges.size() + verticalEdges.size()); |
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 std::list<Internals::OrientedIntegerLine2D::Chain> chains; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
535 Internals::OrientedIntegerLine2D::ExtractChains(chains, allEdges); |
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 for (std::list<Internals::OrientedIntegerLine2D::Chain>::const_iterator |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
538 it = chains.begin(); it != chains.end(); ++it) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
539 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
540 assert(!it->empty()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
541 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
542 std::vector<ScenePoint2D> chain; |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
543 chain.reserve(it->size()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
544 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
545 for (Internals::OrientedIntegerLine2D::Chain::const_iterator |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
546 it2 = it->begin(); it2 != it->end(); ++it2) |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
547 { |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
548 chain.push_back(ScenePoint2D(horizontalProjection.GetEndpointCoordinate(it2->first), |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
549 verticalProjection.GetEndpointCoordinate(it2->second))); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
550 } |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
551 |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
552 assert(!chain.empty()); |
b896f20d24ca
added UnionOfRectangles algorithm
Sebastien Jodogne <s.jodogne@gmail.com>
parents:
diff
changeset
|
553 contours.push_back(chain); |
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 } |