Moka libraries
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
sweeping-comparators.cc
Go to the documentation of this file.
1 /*
2  * lib-corefinement : Opérations de corafinement.
3  * Copyright (C) 2004, Moka Team, Université de Poitiers, Laboratoire SIC
4  * http://www.sic.sp2mi.univ-poitiers.fr/
5  * Copyright (C) 2009, Guillaume Damiand, CNRS, LIRIS,
6  * guillaume.damiand@liris.cnrs.fr, http://liris.cnrs.fr/
7  *
8  * This file is part of lib-corefinement
9  *
10  * This program is free software: you can redistribute it and/or modify
11  * it under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation, either version 3 of the License, or
13  * (at your option) any later version.
14  *
15  * This program is distributed in the hope that it will be useful,
16  * but WITHOUT ANY WARRANTY; without even the implied warranty of
17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  * GNU Lesser General Public License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this program. If not, see <http://www.gnu.org/licenses/>.
22  */
23 
24 //******************************************************************************
25 #include "inline-macro.hh"
26 #include "sweeping-comparators.hh"
27 #include "vertex.hh"
28 #include "dart-vertex.hh"
29 #include "geometry.hh"
30 #include "g-map-vertex.hh"
31 #include <cassert>
32 using namespace GMap3d;
33 //******************************************************************************
34 CDartCompare::CDartCompare(CGMapVertex * AMap,
35  int ADirectVertex, int AExtremity1,
36  const CVertex & AZVector)
37 {
38  assert(AMap!=NULL);
39  assert(0 <= ADirectVertex);
40  assert(0 <= AExtremity1);
41  assert(!AZVector.isNull());
42 
43  FMap = AMap;
44 
45  FDirectVertex = ADirectVertex;
46  FExtremity1 = AExtremity1;
47 
48  if (fabs(AZVector.getX()) > fabs(AZVector.getY()))
49  {
50  if (fabs(AZVector.getX()) > fabs(AZVector.getZ()))
51  {
52  FCoord1 = 1; // OY
53  FCoord2 = 2; // OZ
54  }
55  else
56  {
57  FCoord1 = 0; // OX
58  FCoord2 = 1; // OY
59  }
60  }
61  else
62  {
63  if (fabs(AZVector.getY()) > fabs(AZVector.getZ()))
64  {
65  FCoord1 = 0; // OX
66  FCoord2 = 2; // OZ
67  }
68  else
69  {
70  FCoord1 = 0; // OX
71  FCoord2 = 1; // OY
72  }
73  }
74 }
75 //******************************************************************************
76 CDartLexicoCompare::CDartLexicoCompare(CGMapVertex * AMap,
77  int ADirectVertex, int AExtremity1,
78  const CVertex & AZVector,
79  bool AExactComparison)
80  : CDartCompare(AMap, ADirectVertex, AExtremity1, AZVector)
81 {
82  FExactComparison = AExactComparison;
83 }
84 //******************************************************************************
85 CDartVertexerticalCompare::CDartVertexerticalCompare(CGMapVertex * AMap,
86  int ADirectVertex, int AExtremity1,
87  const CVertex & AZVector)
88  : CDartCompare(AMap, ADirectVertex, AExtremity1, AZVector)
89 {
90 }
91 //******************************************************************************
92 TCoordinate CDartVertexerticalCompare::FX = 0 ;
93 //******************************************************************************
94 CDartAngularCompare::CDartAngularCompare(CGMapVertex * AMap,
95  int ADirectVertex,
96  const CVertex & AZVector)
97  : CDartCompare(AMap, ADirectVertex, 0, AZVector)
98 {
99  FZVector = AZVector;
100 }
101 //******************************************************************************
102 CIntersection::CIntersection(const TCoordinate & ALambda, int AIdentity)
103 {
104  FLambda = ALambda;
105  FIdentity = AIdentity;
106 }
107 //******************************************************************************
108 CDartLinearCompare::CDartLinearCompare()
109 {
110 }
111 //******************************************************************************
112 #define GET_VERTEX(DART) (FMap-> \
113  getDirectInfoAsAttributeVertex(DART, FDirectVertex))
114 //******************************************************************************
115 void CDartCompare::project(const CVertex & AVertex,
116  TCoordinate & AX, TCoordinate & AY) const
117 {
118  AX = AVertex.getCoord(FCoord1);
119  AY = AVertex.getCoord(FCoord2);
120 }
121 //******************************************************************************
122 bool CDartLexicoCompare::operator()
123  (CDartVertex * ADart1, CDartVertex * ADart2) const
124 {
125  if (ADart1==ADart2)
126  return false;
127 
128  // Ces variables sont déclarées statiques pour éviter que le constructeur par
129  // défaut de TCoordinate (quand GMP est utilisé) soit appelé à chaque appel à
130  // la méthode:
131  static TCoordinate x1, y1, x2, y2;
132 
133  project(* GET_VERTEX(ADart1), x1, y1);
134  project(* GET_VERTEX(ADart2), x2, y2);
135 
136  // Comparaison lexicographique:
137  if (FExactComparison)
138  {
139  if (x1 != x2)
140  return x1 < x2;
141 
142  if (y1 != y2)
143  return y1 < y2;
144  }
145  else
146  {
147  if (!areEqual(x1, x2))
148  return x1 < x2;
149 
150  if (!areEqual(y1, y2))
151  return y1 < y2;
152  }
153 
154  // Cas où les extrémités sont confondues:
155  bool in1 = FMap->isMarked(ADart1, FExtremity1);
156  bool in2 = FMap->isMarked(ADart2, FExtremity1);
157 
158  // Si une extrémité est sortante et l'autre entrante,
159  // l'extrémité entrante alpha priorité sur l'extrémité sortante
160  // (pour éviter des problèmes sur les arêtes de longueur nulle):
161  if (in1 != in2)
162  return in1;
163 
164  // Les deux extrémités sont confondues et de même type.
165  // On compare les pointeurs!!
166  return ADart1 < ADart2;
167 }
168 //******************************************************************************
169 bool CDartVertexerticalCompare::operator()
170  (CDartVertex * ADart1, CDartVertex * ADart2) const
171 {
172  if (ADart1==ADart2)
173  return false;
174 
175  // Ces variables sont déclarées statiques pour éviter que le constructeur par
176  // défaut de TCoordinate soit appelé à chaque appel à la méthode:
177  static TCoordinate xA,yA, xB,yB, xC,yC, xD,yD;
178 
179  project(* GET_VERTEX( ADart1 ), xA, yA);
180  project(* GET_VERTEX(FMap->alpha0(ADart1)), xB, yB);
181  project(* GET_VERTEX( ADart2 ), xC, yC);
182  project(* GET_VERTEX(FMap->alpha0(ADart2)), xD, yD);
183 
184  // Delta X:
185  TCoordinate dxAB = xB - xA;
186  TCoordinate dxCD = xD - xC;
187 
188  // Delta Y:
189  TCoordinate dyAB = yB - yA;
190  TCoordinate dyCD = yD - yC;
191 
192  // t:
193  TCoordinate tAB = isZero(dxAB) ? 0.0 : (FX - xA) / dxAB;
194  TCoordinate tCD = isZero(dxCD) ? 0.0 : (FX - xC) / dxCD;
195 
196  TCoordinate yAB = yA + tAB * dyAB;
197  TCoordinate yCD = yC + tCD * dyCD;
198 
199  // Cas où les ordonnées sont distinctes:
200  if (!areEqual(yAB, yCD))
201  return yAB < yCD;
202 
203  // Cas où les ordonnées sont égales:
204  bool in1 = FMap->isMarked(ADart1, FExtremity1);
205  bool in2 = FMap->isMarked(ADart2, FExtremity1);
206 
207  // Si une extrémité est sortante et l'autre entrante,
208  // l'extrémité entrante alpha priorité sur l'extrémité sortante:
209  if (in1 != in2)
210  return in1;
211 
212  // Sinon on regarde l'inclinaison des segments.
213  assert(areEqual(tAB, 0.0) || areEqual(tAB, 1.0) ||
214  areEqual(tCD, 0.0) || areEqual(tCD, 1.0) );
215 
216  bool inverseAB = areEqual(tAB, 1.0);
217  bool inverseCD = areEqual(tCD, 1.0);
218 
219  bool verticalAB = isZero(dxAB);
220  bool verticalCD = isZero(dxCD);
221 
222  if (verticalAB || verticalCD)
223  {
224  if (!verticalAB)
225  return true;
226 
227  if (!verticalCD)
228  return false;
229 
230  return ADart1 < ADart2;
231  }
232 
233  TCoordinate tanAB = dyAB / dxAB;
234  TCoordinate tanCD = dyCD / dxCD;
235 
236  if (inverseAB) tanAB = - tanAB;
237  if (inverseCD) tanCD = - tanCD;
238 
239  if (areEqual(tanAB, tanCD))
240  return ADart1 < ADart2;
241 
242  return tanAB < tanCD;
243 }
244 //******************************************************************************
245 void CDartVertexerticalCompare::setCurrentPoint(const CVertex & AVertex)
246 {
247  // Cette variable est déclarée statique pour éviter que le constructeur par
248  // défaut de TCoordinate soit appelé à chaque appel à la méthode:
249  static TCoordinate y;
250  project(AVertex, FX, y);
251 }
252 //******************************************************************************
253 bool CDartAngularCompare::operator()
254  (CDartVertex * ADart1, CDartVertex * ADart2) const
255 {
256  if (ADart1==ADart2)
257  return false;
258 
259  const CVertex O =
260  (* GET_VERTEX(ADart1) + * GET_VERTEX(ADart2)) / 2;
261 
262  const CVertex & A = * GET_VERTEX(FMap->alpha0(ADart1));
263  const CVertex & B = * GET_VERTEX(FMap->alpha0(ADart2));
264 
265  TCoordinate angle = CGeometry::getAngle(A-O, B-O, FZVector);
266 
267  // if (isZero(angle))
268  // return ADart1 < ADart2;
269 
270  return angle < 0;
271 }
272 //******************************************************************************
273 #undef GET_VERTEX
274 //******************************************************************************
275 bool CDartLinearCompare::operator()(CIntersection * AIntersection1,
276  CIntersection * AIntersection2) const
277 {
278  assert(AIntersection1->FIdentity != AIntersection2->FIdentity);
279 
280  if (areEqual(AIntersection1->FLambda, AIntersection2->FLambda))
281  return AIntersection1->FIdentity < AIntersection2->FIdentity;
282 
283  return AIntersection1->FLambda < AIntersection2->FLambda;
284 }
285 //******************************************************************************