00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "inline-macro.hh"
00026 #include "sweeping-comparators.hh"
00027 #include "vertex.hh"
00028 #include "dart-vertex.hh"
00029 #include "geometry.hh"
00030 #include "g-map-vertex.hh"
00031 #include <cassert>
00032 using namespace GMap3d;
00033
00034 CDartCompare::CDartCompare(CGMapVertex * AMap,
00035 int ADirectVertex, int AExtremity1,
00036 const CVertex & AZVector)
00037 {
00038 assert(AMap!=NULL);
00039 assert(0 <= ADirectVertex);
00040 assert(0 <= AExtremity1);
00041 assert(!AZVector.isNull());
00042
00043 FMap = AMap;
00044
00045 FDirectVertex = ADirectVertex;
00046 FExtremity1 = AExtremity1;
00047
00048 if (fabs(AZVector.getX()) > fabs(AZVector.getY()))
00049 {
00050 if (fabs(AZVector.getX()) > fabs(AZVector.getZ()))
00051 {
00052 FCoord1 = 1;
00053 FCoord2 = 2;
00054 }
00055 else
00056 {
00057 FCoord1 = 0;
00058 FCoord2 = 1;
00059 }
00060 }
00061 else
00062 {
00063 if (fabs(AZVector.getY()) > fabs(AZVector.getZ()))
00064 {
00065 FCoord1 = 0;
00066 FCoord2 = 2;
00067 }
00068 else
00069 {
00070 FCoord1 = 0;
00071 FCoord2 = 1;
00072 }
00073 }
00074 }
00075
00076 CDartLexicoCompare::CDartLexicoCompare(CGMapVertex * AMap,
00077 int ADirectVertex, int AExtremity1,
00078 const CVertex & AZVector,
00079 bool AExactComparison)
00080 : CDartCompare(AMap, ADirectVertex, AExtremity1, AZVector)
00081 {
00082 FExactComparison = AExactComparison;
00083 }
00084
00085 CDartVertexerticalCompare::CDartVertexerticalCompare(CGMapVertex * AMap,
00086 int ADirectVertex, int AExtremity1,
00087 const CVertex & AZVector)
00088 : CDartCompare(AMap, ADirectVertex, AExtremity1, AZVector)
00089 {
00090 }
00091
00092 TCoordinate CDartVertexerticalCompare::FX = 0 ;
00093
00094 CDartAngularCompare::CDartAngularCompare(CGMapVertex * AMap,
00095 int ADirectVertex,
00096 const CVertex & AZVector)
00097 : CDartCompare(AMap, ADirectVertex, 0, AZVector)
00098 {
00099 FZVector = AZVector;
00100 }
00101
00102 CIntersection::CIntersection(const TCoordinate & ALambda, int AIdentity)
00103 {
00104 FLambda = ALambda;
00105 FIdentity = AIdentity;
00106 }
00107
00108 CDartLinearCompare::CDartLinearCompare()
00109 {
00110 }
00111
00112 #define GET_VERTEX(DART) (FMap-> \
00113 getDirectInfoAsAttributeVertex(DART, FDirectVertex))
00114
00115 void CDartCompare::project(const CVertex & AVertex,
00116 TCoordinate & AX, TCoordinate & AY) const
00117 {
00118 AX = AVertex.getCoord(FCoord1);
00119 AY = AVertex.getCoord(FCoord2);
00120 }
00121
00122 bool CDartLexicoCompare::operator()
00123 (CDartVertex * ADart1, CDartVertex * ADart2) const
00124 {
00125 if (ADart1==ADart2)
00126 return false;
00127
00128
00129
00130
00131 static TCoordinate x1, y1, x2, y2;
00132
00133 project(* GET_VERTEX(ADart1), x1, y1);
00134 project(* GET_VERTEX(ADart2), x2, y2);
00135
00136
00137 if (FExactComparison)
00138 {
00139 if (x1 != x2)
00140 return x1 < x2;
00141
00142 if (y1 != y2)
00143 return y1 < y2;
00144 }
00145 else
00146 {
00147 if (!areEqual(x1, x2))
00148 return x1 < x2;
00149
00150 if (!areEqual(y1, y2))
00151 return y1 < y2;
00152 }
00153
00154
00155 bool in1 = FMap->isMarked(ADart1, FExtremity1);
00156 bool in2 = FMap->isMarked(ADart2, FExtremity1);
00157
00158
00159
00160
00161 if (in1 != in2)
00162 return in1;
00163
00164
00165
00166 return ADart1 < ADart2;
00167 }
00168
00169 bool CDartVertexerticalCompare::operator()
00170 (CDartVertex * ADart1, CDartVertex * ADart2) const
00171 {
00172 if (ADart1==ADart2)
00173 return false;
00174
00175
00176
00177 static TCoordinate xA,yA, xB,yB, xC,yC, xD,yD;
00178
00179 project(* GET_VERTEX( ADart1 ), xA, yA);
00180 project(* GET_VERTEX(FMap->alpha0(ADart1)), xB, yB);
00181 project(* GET_VERTEX( ADart2 ), xC, yC);
00182 project(* GET_VERTEX(FMap->alpha0(ADart2)), xD, yD);
00183
00184
00185 TCoordinate dxAB = xB - xA;
00186 TCoordinate dxCD = xD - xC;
00187
00188
00189 TCoordinate dyAB = yB - yA;
00190 TCoordinate dyCD = yD - yC;
00191
00192
00193 TCoordinate tAB = isZero(dxAB) ? 0.0 : (FX - xA) / dxAB;
00194 TCoordinate tCD = isZero(dxCD) ? 0.0 : (FX - xC) / dxCD;
00195
00196 TCoordinate yAB = yA + tAB * dyAB;
00197 TCoordinate yCD = yC + tCD * dyCD;
00198
00199
00200 if (!areEqual(yAB, yCD))
00201 return yAB < yCD;
00202
00203
00204 bool in1 = FMap->isMarked(ADart1, FExtremity1);
00205 bool in2 = FMap->isMarked(ADart2, FExtremity1);
00206
00207
00208
00209 if (in1 != in2)
00210 return in1;
00211
00212
00213 assert(areEqual(tAB, 0.0) || areEqual(tAB, 1.0) ||
00214 areEqual(tCD, 0.0) || areEqual(tCD, 1.0) );
00215
00216 bool inverseAB = areEqual(tAB, 1.0);
00217 bool inverseCD = areEqual(tCD, 1.0);
00218
00219 bool verticalAB = isZero(dxAB);
00220 bool verticalCD = isZero(dxCD);
00221
00222 if (verticalAB || verticalCD)
00223 {
00224 if (!verticalAB)
00225 return true;
00226
00227 if (!verticalCD)
00228 return false;
00229
00230 return ADart1 < ADart2;
00231 }
00232
00233 TCoordinate tanAB = dyAB / dxAB;
00234 TCoordinate tanCD = dyCD / dxCD;
00235
00236 if (inverseAB) tanAB = - tanAB;
00237 if (inverseCD) tanCD = - tanCD;
00238
00239 if (areEqual(tanAB, tanCD))
00240 return ADart1 < ADart2;
00241
00242 return tanAB < tanCD;
00243 }
00244
00245 void CDartVertexerticalCompare::setCurrentPoint(const CVertex & AVertex)
00246 {
00247
00248
00249 static TCoordinate y;
00250 project(AVertex, FX, y);
00251 }
00252
00253 bool CDartAngularCompare::operator()
00254 (CDartVertex * ADart1, CDartVertex * ADart2) const
00255 {
00256 if (ADart1==ADart2)
00257 return false;
00258
00259 const CVertex O =
00260 (* GET_VERTEX(ADart1) + * GET_VERTEX(ADart2)) / 2;
00261
00262 const CVertex & A = * GET_VERTEX(FMap->alpha0(ADart1));
00263 const CVertex & B = * GET_VERTEX(FMap->alpha0(ADart2));
00264
00265 TCoordinate angle = CGeometry::getAngle(A-O, B-O, FZVector);
00266
00267
00268
00269
00270 return angle < 0;
00271 }
00272
00273 #undef GET_VERTEX
00274
00275 bool CDartLinearCompare::operator()(CIntersection * AIntersection1,
00276 CIntersection * AIntersection2) const
00277 {
00278 assert(AIntersection1->FIdentity != AIntersection2->FIdentity);
00279
00280 if (areEqual(AIntersection1->FLambda, AIntersection2->FLambda))
00281 return AIntersection1->FIdentity < AIntersection2->FIdentity;
00282
00283 return AIntersection1->FLambda < AIntersection2->FLambda;
00284 }
00285