Quantum GIS API Documentation
1.7.4
|
00001 /*************************************************************************** 00002 qgsclipper.h - a class that clips line 00003 segments and polygons 00004 ------------------- 00005 begin : March 2004 00006 copyright : (C) 2005 by Gavin Macaulay 00007 email : 00008 ***************************************************************************/ 00009 00010 /*************************************************************************** 00011 * * 00012 * This program is free software; you can redistribute it and/or modify * 00013 * it under the terms of the GNU General Public License as published by * 00014 * the Free Software Foundation; either version 2 of the License, or * 00015 * (at your option) any later version. * 00016 * * 00017 ***************************************************************************/ 00018 /* $Id$ */ 00019 00020 #ifndef QGSCLIPPER_H 00021 #define QGSCLIPPER_H 00022 00023 #include "qgis.h" 00024 #include "qgspoint.h" 00025 #include "qgsrectangle.h" 00026 00027 #include <vector> 00028 #include <utility> 00029 00030 #include <QPolygonF> 00031 00042 class CORE_EXPORT QgsClipper 00043 { 00044 public: 00045 00046 // Coordinates of the rectangular box that we trim to. 00047 // 00048 // These are the limits for X11 screen coordinates. The actual 00049 // values are +/-32767, but we allow a little bit of space for 00050 // rounding errors. 00051 00052 // You may wonder why the clipping is done to these coordindates 00053 // rather than the boundaries of the qgis canvas. Reasons include: 00054 // - making the boundaries static const allows the compiler to 00055 // optimise the code that uses these values more than if they changed 00056 // for every call to the trim code. 00057 // - clipping takes quite a bit of CPU effort, and the less that this is 00058 // done the better. More stuff would have to be clipped if the 00059 // boundaries were the qgis canvas (but this may be offset by 00060 // having less to draw). 00061 // 00062 // The limit is set to 30,000 instead of 32768 because that things 00063 // still go wrong. 00064 00065 static const double MAX_X; 00066 static const double MIN_X; 00067 static const double MAX_Y; 00068 static const double MIN_Y; 00069 00070 00071 // A handy way to refer to the four boundaries 00072 enum Boundary {XMax, XMin, YMax, YMin}; 00073 00074 // Trims the given feature to a rectangular box. Returns the trimmed 00075 // feature in x and y. The shapeOpen parameter determines whether 00076 // the function treats the points as a closed shape (polygon), or as 00077 // an open shape (linestring). 00078 static void trimFeature( std::vector<double>& x, 00079 std::vector<double>& y, 00080 bool shapeOpen ); 00081 00082 static void trimPolygon( QPolygonF& pts, const QgsRectangle& clipRect ); 00083 00088 static unsigned char* clippedLineWKB( unsigned char* wkb, const QgsRectangle& clipExtent, QPolygonF& line ); 00089 00090 private: 00091 00092 // Used when testing for equivalance to 0.0 00093 static const double SMALL_NUM; 00094 00095 // Trims the given feature to the given boundary. Returns the 00096 // trimmed feature in the outX and outY vectors. 00097 static void trimFeatureToBoundary( const std::vector<double>& inX, 00098 const std::vector<double>& inY, 00099 std::vector<double>& outX, 00100 std::vector<double>& outY, 00101 Boundary b, 00102 bool shapeOpen ); 00103 00104 static void trimPolygonToBoundary( const QPolygonF& inPts, QPolygonF& outPts, const QgsRectangle& rect, Boundary b, double boundaryValue ); 00105 00106 // Determines if a point is inside or outside the given boundary 00107 static bool inside( const double x, const double y, Boundary b ); 00108 00109 static bool inside( const QPointF& pt, Boundary b, double val ); 00110 00111 // Calculates the intersection point between a line defined by a 00112 // (x1, y1), and (x2, y2) and the given boundary 00113 static QgsPoint intersect( const double x1, const double y1, 00114 const double x2, const double y2, 00115 Boundary b ); 00116 00117 static QPointF intersectRect( const QPointF& pt1, 00118 const QPointF& pt2, 00119 Boundary b, const QgsRectangle& rect ); 00120 00121 //Implementation of 'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467) 00122 static bool clipLineSegment( double xLeft, double xRight, double yBottom, double yTop, double& x0, double& y0, double& x1, double& y1 ); 00123 00132 static void connectSeparatedLines( double x0, double y0, double x1, double y1, 00133 const QgsRectangle& clipRect, QPolygonF& pts ); 00134 00135 //low level clip methods for fast clip algorithm 00136 static void clipStartTop( double& x0, double& y0, const double& x1, const double& y1, double yMax ); 00137 static void clipStartBottom( double& x0, double& y0, const double& x1, const double& y1, double yMin ); 00138 static void clipStartRight( double& x0, double& y0, const double& x1, const double& y1, double xMax ); 00139 static void clipStartLeft( double& x0, double& y0, const double& x1, const double& y1, double xMin ); 00140 static void clipEndTop( const double& x0, const double& y0, double& x1, double& y1, double yMax ); 00141 static void clipEndBottom( const double& x0, const double& y0, double& x1, double& y1, double yMin ); 00142 static void clipEndRight( const double& x0, const double& y0, double& x1, double& y1, double xMax ); 00143 static void clipEndLeft( const double& x0, const double& y0, double& x1, double& y1, double xMin ); 00144 }; 00145 00146 // The inline functions 00147 00148 // Trim the feature using Sutherland and Hodgman's 00149 // polygon-clipping algorithm. See J. D. Foley, A. van Dam, 00150 // S. K. Feiner, and J. F. Hughes, Computer Graphics, Principles and 00151 // Practice. Addison-Wesley Systems Programming Series, 00152 // Addison-Wesley, 2nd ed., 1991. 00153 00154 // I understand that this is not the most efficient algorithm, but is 00155 // one (the only?) that is guaranteed to always give the correct 00156 // result. 00157 00158 inline void QgsClipper::trimFeature( std::vector<double>& x, 00159 std::vector<double>& y, 00160 bool shapeOpen ) 00161 { 00162 std::vector<double> tmpX; 00163 std::vector<double> tmpY; 00164 trimFeatureToBoundary( x, y, tmpX, tmpY, XMax, shapeOpen ); 00165 00166 x.clear(); 00167 y.clear(); 00168 trimFeatureToBoundary( tmpX, tmpY, x, y, YMax, shapeOpen ); 00169 00170 tmpX.clear(); 00171 tmpY.clear(); 00172 trimFeatureToBoundary( x, y, tmpX, tmpY, XMin, shapeOpen ); 00173 00174 x.clear(); 00175 y.clear(); 00176 trimFeatureToBoundary( tmpX, tmpY, x, y, YMin, shapeOpen ); 00177 } 00178 00179 inline void QgsClipper::trimPolygon( QPolygonF& pts, const QgsRectangle& clipRect ) 00180 { 00181 QPolygonF tmpPts; 00182 tmpPts.reserve( pts.size() ); 00183 00184 trimPolygonToBoundary( pts, tmpPts, clipRect, XMax, clipRect.xMaximum() ); 00185 pts.clear(); 00186 trimPolygonToBoundary( tmpPts, pts, clipRect, YMax, clipRect.yMaximum() ); 00187 tmpPts.clear(); 00188 trimPolygonToBoundary( pts, tmpPts, clipRect, XMin, clipRect.xMinimum() ); 00189 pts.clear(); 00190 trimPolygonToBoundary( tmpPts, pts, clipRect, YMin, clipRect.yMinimum() ); 00191 } 00192 00193 // An auxilary function that is part of the polygon trimming 00194 // code. Will trim the given polygon to the given boundary and return 00195 // the trimmed polygon in the out pointer. Uses Sutherland and 00196 // Hodgman's polygon-clipping algorithm. 00197 00198 inline void QgsClipper::trimFeatureToBoundary( 00199 const std::vector<double>& inX, 00200 const std::vector<double>& inY, 00201 std::vector<double>& outX, 00202 std::vector<double>& outY, 00203 Boundary b, bool shapeOpen ) 00204 { 00205 // The shapeOpen parameter selects whether this function treats the 00206 // shape as open or closed. False is appropriate for polygons and 00207 // true for polylines. 00208 00209 unsigned int i1 = inX.size() - 1; // start with last point 00210 00211 // and compare to the first point initially. 00212 for ( unsigned int i2 = 0; i2 < inX.size() ; ++i2 ) 00213 { 00214 // look at each edge of the polygon in turn 00215 00216 //ignore segments with nan or inf coordinates 00217 if ( qIsNaN( inX[i2] ) || qIsNaN( inY[i2] ) || qIsInf( inX[i2] ) || qIsInf( inY[i2] ) 00218 || qIsNaN( inX[i1] ) || qIsNaN( inY[i1] ) || qIsInf( inX[i1] ) || qIsInf( inY[i1] ) ) 00219 { 00220 i1 = i2; 00221 continue; 00222 } 00223 00224 00225 if ( inside( inX[i2], inY[i2], b ) ) // end point of edge is inside boundary 00226 { 00227 if ( inside( inX[i1], inY[i1], b ) ) 00228 { 00229 outX.push_back( inX[i2] ); 00230 outY.push_back( inY[i2] ); 00231 } 00232 else 00233 { 00234 // edge crosses into the boundary, so trim back to the boundary, and 00235 // store both ends of the new edge 00236 if ( !( i2 == 0 && shapeOpen ) ) 00237 { 00238 QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b ); 00239 outX.push_back( p.x() ); 00240 outY.push_back( p.y() ); 00241 } 00242 00243 outX.push_back( inX[i2] ); 00244 outY.push_back( inY[i2] ); 00245 } 00246 } 00247 else // end point of edge is outside boundary 00248 { 00249 // start point is in boundary, so need to trim back 00250 if ( inside( inX[i1], inY[i1], b ) ) 00251 { 00252 if ( !( i2 == 0 && shapeOpen ) ) 00253 { 00254 QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b ); 00255 outX.push_back( p.x() ); 00256 outY.push_back( p.y() ); 00257 } 00258 } 00259 } 00260 i1 = i2; 00261 } 00262 } 00263 00264 inline void QgsClipper::trimPolygonToBoundary( const QPolygonF& inPts, QPolygonF& outPts, const QgsRectangle& rect, Boundary b, double boundaryValue ) 00265 { 00266 unsigned int i1 = inPts.size() - 1; // start with last point 00267 00268 // and compare to the first point initially. 00269 for ( int i2 = 0; i2 < inPts.size() ; ++i2 ) 00270 { // look at each edge of the polygon in turn 00271 if ( inside( inPts[i2], b, boundaryValue ) ) // end point of edge is inside boundary 00272 { 00273 if ( inside( inPts[i1], b, boundaryValue ) ) 00274 { 00275 outPts.append( inPts[i2] ); 00276 } 00277 else 00278 { 00279 // edge crosses into the boundary, so trim back to the boundary, and 00280 // store both ends of the new edge 00281 outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) ); 00282 outPts.append( inPts[i2] ); 00283 } 00284 } 00285 else // end point of edge is outside boundary 00286 { 00287 // start point is in boundary, so need to trim back 00288 if ( inside( inPts[i1], b, boundaryValue ) ) 00289 { 00290 outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) ); 00291 } 00292 } 00293 i1 = i2; 00294 } 00295 } 00296 00297 // An auxilary function to trimPolygonToBoundarY() that returns 00298 // whether a point is inside or outside the given boundary. 00299 00300 inline bool QgsClipper::inside( const double x, const double y, Boundary b ) 00301 { 00302 switch ( b ) 00303 { 00304 case XMax: // x < MAX_X is inside 00305 if ( x < MAX_X ) 00306 return true; 00307 break; 00308 case XMin: // x > MIN_X is inside 00309 if ( x > MIN_X ) 00310 return true; 00311 break; 00312 case YMax: // y < MAX_Y is inside 00313 if ( y < MAX_Y ) 00314 return true; 00315 break; 00316 case YMin: // y > MIN_Y is inside 00317 if ( y > MIN_Y ) 00318 return true; 00319 break; 00320 } 00321 return false; 00322 } 00323 00324 inline bool QgsClipper::inside( const QPointF& pt, Boundary b, double val ) 00325 { 00326 switch ( b ) 00327 { 00328 case XMax: // x < MAX_X is inside 00329 return ( pt.x() < val ); 00330 case XMin: // x > MIN_X is inside 00331 return ( pt.x() > val ); 00332 case YMax: // y < MAX_Y is inside 00333 return ( pt.y() < val ); 00334 case YMin: // y > MIN_Y is inside 00335 return ( pt.y() > val ); 00336 } 00337 return false; 00338 } 00339 00340 00341 // An auxilary function to trimPolygonToBoundarY() that calculates and 00342 // returns the intersection of the line defined by the given points 00343 // and the given boundary. 00344 00345 inline QgsPoint QgsClipper::intersect( const double x1, const double y1, 00346 const double x2, const double y2, 00347 Boundary b ) 00348 { 00349 // This function assumes that the two given points (x1, y1), and 00350 // (x2, y2) cross the given boundary. Making this assumption allows 00351 // some optimisations. 00352 00353 double r_n = SMALL_NUM, r_d = SMALL_NUM; 00354 00355 switch ( b ) 00356 { 00357 case XMax: // x = MAX_X boundary 00358 r_n = -( x1 - MAX_X ) * ( MAX_Y - MIN_Y ); 00359 r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y ); 00360 break; 00361 case XMin: // x = MIN_X boundary 00362 r_n = -( x1 - MIN_X ) * ( MAX_Y - MIN_Y ); 00363 r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y ); 00364 break; 00365 case YMax: // y = MAX_Y boundary 00366 r_n = ( y1 - MAX_Y ) * ( MAX_X - MIN_X ); 00367 r_d = -( y2 - y1 ) * ( MAX_X - MIN_X ); 00368 break; 00369 case YMin: // y = MIN_Y boundary 00370 r_n = ( y1 - MIN_Y ) * ( MAX_X - MIN_X ); 00371 r_d = -( y2 - y1 ) * ( MAX_X - MIN_X ); 00372 break; 00373 } 00374 00375 QgsPoint p; 00376 00377 if ( qAbs( r_d ) > SMALL_NUM && qAbs( r_n ) > SMALL_NUM ) 00378 { // they cross 00379 double r = r_n / r_d; 00380 p.set( x1 + r*( x2 - x1 ), y1 + r*( y2 - y1 ) ); 00381 } 00382 else 00383 { 00384 // Should never get here, but if we do for some reason, cause a 00385 // clunk because something else is wrong if we do. 00386 Q_ASSERT( qAbs( r_d ) > SMALL_NUM && qAbs( r_n ) > SMALL_NUM ); 00387 } 00388 00389 return p; 00390 } 00391 00392 inline QPointF QgsClipper::intersectRect( const QPointF& pt1, 00393 const QPointF& pt2, 00394 Boundary b, const QgsRectangle& rect ) 00395 { 00396 // This function assumes that the two given points (x1, y1), and 00397 // (x2, y2) cross the given boundary. Making this assumption allows 00398 // some optimisations. 00399 00400 double r_n = SMALL_NUM, r_d = SMALL_NUM; 00401 const double x1 = pt1.x(), x2 = pt2.x(); 00402 const double y1 = pt1.y(), y2 = pt2.y(); 00403 00404 switch ( b ) 00405 { 00406 case XMax: // x = MAX_X boundary 00407 r_n = -( x1 - rect.xMaximum() ) * ( rect.yMaximum() - rect.yMinimum() ); 00408 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() ); 00409 break; 00410 case XMin: // x = MIN_X boundary 00411 r_n = -( x1 - rect.xMinimum() ) * ( rect.yMaximum() - rect.yMinimum() ); 00412 r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() ); 00413 break; 00414 case YMax: // y = MAX_Y boundary 00415 r_n = ( y1 - rect.yMaximum() ) * ( rect.xMaximum() - rect.xMinimum() ); 00416 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() ); 00417 break; 00418 case YMin: // y = MIN_Y boundary 00419 r_n = ( y1 - rect.yMinimum() ) * ( rect.xMaximum() - rect.xMinimum() ); 00420 r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() ); 00421 break; 00422 } 00423 00424 double r = 0; 00425 if ( !doubleNear( r_d, 0.0 ) ) 00426 { 00427 r = r_n / r_d; 00428 } 00429 return QPointF( x1 + r*( x2 - x1 ), y1 + r*( y2 - y1 ) ); 00430 } 00431 00432 inline void QgsClipper::clipStartTop( double& x0, double& y0, const double& x1, const double& y1, double yMax ) 00433 { 00434 x0 += ( x1 - x0 ) * ( yMax - y0 ) / ( y1 - y0 ); 00435 y0 = yMax; 00436 } 00437 00438 inline void QgsClipper::clipStartBottom( double& x0, double& y0, const double& x1, const double& y1, double yMin ) 00439 { 00440 x0 += ( x1 - x0 ) * ( yMin - y0 ) / ( y1 - y0 ); 00441 y0 = yMin; 00442 } 00443 00444 inline void QgsClipper::clipStartRight( double& x0, double& y0, const double& x1, const double& y1, double xMax ) 00445 { 00446 y0 += ( y1 - y0 ) * ( xMax - x0 ) / ( x1 - x0 ); 00447 x0 = xMax; 00448 } 00449 00450 inline void QgsClipper::clipStartLeft( double& x0, double& y0, const double& x1, const double& y1, double xMin ) 00451 { 00452 y0 += ( y1 - y0 ) * ( xMin - x0 ) / ( x1 - x0 ); 00453 x0 = xMin; 00454 } 00455 00456 inline void QgsClipper::clipEndTop( const double& x0, const double& y0, double& x1, double& y1, double yMax ) 00457 { 00458 x1 += ( x1 - x0 ) * ( yMax - y1 ) / ( y1 - y0 ); 00459 y1 = yMax; 00460 } 00461 00462 inline void QgsClipper::clipEndBottom( const double& x0, const double& y0, double& x1, double& y1, double yMin ) 00463 { 00464 x1 += ( x1 - x0 ) * ( yMin - y1 ) / ( y1 - y0 ); 00465 y1 = yMin; 00466 } 00467 00468 inline void QgsClipper::clipEndRight( const double& x0, const double& y0, double& x1, double& y1, double xMax ) 00469 { 00470 y1 += ( y1 - y0 ) * ( xMax - x1 ) / ( x1 - x0 ); 00471 x1 = xMax; 00472 } 00473 00474 inline void QgsClipper::clipEndLeft( const double& x0, const double& y0, double& x1, double& y1, double xMin ) 00475 { 00476 y1 += ( y1 - y0 ) * ( xMin - x1 ) / ( x1 - x0 ); 00477 x1 = xMin; 00478 } 00479 00480 //'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467) 00481 inline bool QgsClipper::clipLineSegment( double xLeft, double xRight, double yBottom, double yTop, double& x0, double& y0, double& x1, double& y1 ) 00482 { 00483 int lineCode = 0; 00484 00485 if ( y1 < yBottom ) 00486 lineCode |= 4; 00487 else if ( y1 > yTop ) 00488 lineCode |= 8; 00489 00490 if ( x1 > xRight ) 00491 lineCode |= 2; 00492 else if ( x1 < xLeft ) 00493 lineCode |= 1; 00494 00495 if ( y0 < yBottom ) 00496 lineCode |= 64; 00497 else if ( y0 > yTop ) 00498 lineCode |= 128; 00499 00500 if ( x0 > xRight ) 00501 lineCode |= 32; 00502 else if ( x0 < xLeft ) 00503 lineCode |= 16; 00504 00505 switch ( lineCode ) 00506 { 00507 case 0: //completely inside 00508 return true; 00509 00510 case 1: 00511 clipEndLeft( x0, y0, x1, y1, xLeft ); 00512 return true; 00513 00514 case 2: 00515 clipEndRight( x0, y0, x1, y1, xRight ); 00516 return true; 00517 00518 case 4: 00519 clipEndBottom( x0, y0, x1, y1, yBottom ); 00520 return true; 00521 00522 case 5: 00523 clipEndLeft( x0, y0, x1, y1, xLeft ); 00524 if ( y1 < yBottom ) 00525 clipEndBottom( x0, y0, x1, y1, yBottom ); 00526 return true; 00527 00528 case 6: 00529 clipEndRight( x0, y0, x1, y1, xRight ); 00530 if ( y1 < yBottom ) 00531 clipEndBottom( x0, y0, x1, y1, yBottom ); 00532 return true; 00533 00534 case 8: 00535 clipEndTop( x0, y0, x1, y1, yTop ); 00536 return true; 00537 00538 case 9: 00539 clipEndLeft( x0, y0, x1, y1, xLeft ); 00540 if ( y1 > yTop ) 00541 clipEndTop( x0, y0, x1, y1, yTop ); 00542 return true; 00543 00544 case 10: 00545 clipEndRight( x0, y0, x1, y1, xRight ); 00546 if ( y1 > yTop ) 00547 clipEndTop( x0, y0, x1, y1, yTop ); 00548 return true; 00549 00550 case 16: 00551 clipStartLeft( x0, y0, x1, y1, xLeft ); 00552 return true; 00553 00554 case 18: 00555 clipStartLeft( x0, y0, x1, y1, xLeft ); 00556 clipEndRight( x0, y0, x1, y1, xRight ); 00557 return true; 00558 00559 case 20: 00560 clipStartLeft( x0, y0, x1, y1, xLeft ); 00561 if ( y0 < yBottom ) 00562 return false; 00563 clipEndBottom( x0, y0, x1, y1, yBottom ); 00564 return true; 00565 00566 case 22: 00567 clipStartLeft( x0, y0, x1, y1, xLeft ); 00568 if ( y0 < yBottom ) 00569 return false; 00570 clipEndBottom( x0, y0, x1, y1, yBottom ); 00571 if ( x1 > xRight ) 00572 clipEndRight( x0, y0, x1, y1, xRight ); 00573 return true; 00574 00575 case 24: 00576 clipStartLeft( x0, y0, x1, y1, xLeft ); 00577 if ( y0 > yTop ) 00578 return false; 00579 clipEndTop( x0, y0, x1, y1, yTop ); 00580 return true; 00581 00582 case 26: 00583 clipStartLeft( x0, y0, x1, y1, xLeft ); 00584 if ( y0 > yTop ) 00585 return false; 00586 clipEndTop( x0, y0, x1, y1, yTop ); 00587 if ( x1 > xRight ) 00588 clipEndRight( x0, y0, x1, y1, xRight ); 00589 return true; 00590 00591 case 32: 00592 clipStartRight( x0, y0, x1, y1, xRight ); 00593 return true; 00594 00595 case 33: 00596 clipStartRight( x0, y0, x1, y1, xRight ); 00597 clipEndLeft( x0, y0, x1, y1, xLeft ); 00598 return true; 00599 00600 case 36: 00601 clipStartRight( x0, y0, x1, y1, xRight ); 00602 if ( y0 < yBottom ) 00603 return false; 00604 clipEndBottom( x0, y0, x1, y1, yBottom ); 00605 return true; 00606 00607 case 37: 00608 clipStartRight( x0, y0, x1, y1, xRight ); 00609 if ( y0 < yBottom ) 00610 return false; 00611 clipEndBottom( x0, y0, x1, y1, yBottom ); 00612 if ( x1 < xLeft ) 00613 clipEndLeft( x0, y0, x1, y1, xLeft ); 00614 return true; 00615 00616 case 40: 00617 clipStartRight( x0, y0, x1, y1, xRight ); 00618 if ( y0 > yTop ) 00619 return false; 00620 clipEndTop( x0, y0, x1, y1, yTop ); 00621 return true; 00622 00623 case 41: 00624 clipStartRight( x0, y0, x1, y1, xRight ); 00625 if ( y0 > yTop ) 00626 return false; 00627 clipEndTop( x0, y0, x1, y1, yTop ); 00628 if ( x1 < xLeft ) 00629 clipEndLeft( x0, y0, x1, y1, xLeft ); 00630 return true; 00631 00632 case 64: 00633 clipStartBottom( x0, y0, x1, y1, yBottom ); 00634 return true; 00635 00636 case 65: 00637 clipStartBottom( x0, y0, x1, y1, yBottom ); 00638 if ( x0 < xLeft ) 00639 return false; 00640 clipEndLeft( x0, y0, x1, y1, xLeft ); 00641 if ( y1 < yBottom ) 00642 clipEndBottom( x0, y0, x1, y1, yBottom ); 00643 return true; 00644 00645 case 66: 00646 clipStartBottom( x0, y0, x1, y1, yBottom ); 00647 if ( x0 > xRight ) 00648 return false; 00649 clipEndRight( x0, y0, x1, y1, xRight ); 00650 return true; 00651 00652 case 72: 00653 clipStartBottom( x0, y0, x1, y1, yBottom ); 00654 clipEndTop( x0, y0, x1, y1, yTop ); 00655 return true; 00656 00657 case 73: 00658 clipStartBottom( x0, y0, x1, y1, yBottom ); 00659 if ( x0 < xLeft ) 00660 return false; 00661 clipEndLeft( x0, y0, x1, y1, xLeft ); 00662 if ( y1 > yTop ) 00663 clipEndTop( x0, y0, x1, y1, yTop ); 00664 return true; 00665 00666 case 74: 00667 clipStartBottom( x0, y0, x1, y1, yBottom ); 00668 if ( x0 > xRight ) 00669 return false; 00670 clipEndRight( x0, y0, x1, y1, xRight ); 00671 if ( y1 > yTop ) 00672 clipEndTop( x0, y0, x1, y1, yTop ); 00673 return true; 00674 00675 case 80: 00676 clipStartLeft( x0, y0, x1, y1, xLeft ); 00677 if ( y0 < yBottom ) 00678 clipStartBottom( x0, y0, x1, y1, yBottom ); 00679 return true; 00680 00681 case 82: 00682 clipEndRight( x0, y0, x1, y1, xRight ); 00683 if ( y1 < yBottom ) 00684 return false; 00685 clipStartBottom( x0, y0, x1, y1, yBottom ); 00686 if ( x0 < xLeft ) 00687 clipStartLeft( x0, y0, x1, y1, xLeft ); 00688 return true; 00689 00690 case 88: 00691 clipEndTop( x0, y0, x1, y1, yTop ); 00692 if ( x1 < xLeft ) 00693 return false; 00694 clipStartBottom( x0, y0, x1, y1, yBottom ); 00695 if ( x0 < xLeft ) 00696 clipStartLeft( x0, y0, x1, y1, xLeft ); 00697 return true; 00698 00699 case 90: 00700 clipStartLeft( x0, y0, x1, y1, xLeft ); 00701 if ( y0 > yTop ) 00702 return false; 00703 clipEndRight( x0, y0, x1, y1, xRight ); 00704 if ( y1 < yBottom ) 00705 return false; 00706 if ( y0 < yBottom ) 00707 clipStartBottom( x0, y0, x1, y1, yBottom ); 00708 if ( y1 > yTop ) 00709 clipEndTop( x0, y0, x1, y1, yTop ); 00710 return true; 00711 00712 case 96: 00713 clipStartRight( x0, y0, x1, y1, xRight ); 00714 if ( y0 < yBottom ) 00715 clipStartBottom( x0, y0, x1, y1, yBottom ); 00716 return true; 00717 00718 case 97: 00719 clipEndLeft( x0, y0, x1, y1, xLeft ); 00720 if ( y1 < yBottom ) 00721 return false; 00722 clipStartBottom( x0, y0, x1, y1, yBottom ); 00723 if ( x0 > xRight ) 00724 clipStartRight( x0, y0, x1, y1, xRight ); 00725 return true; 00726 00727 case 104: 00728 clipEndTop( x0, y0, x1, y1, yTop ); 00729 if ( x1 > xRight ) 00730 return false; 00731 clipStartRight( x0, y0, x1, y1, xRight ); 00732 if ( y0 < yBottom ) 00733 clipStartBottom( x0, y0, x1, y1, yBottom ); 00734 return true; 00735 00736 case 105: 00737 clipEndLeft( x0, y0, x1, y1, xLeft ); 00738 if ( y1 < yBottom ) 00739 return false; 00740 clipStartRight( x0, y0, x1, y1, xRight ); 00741 if ( y0 > yTop ) 00742 return false; 00743 if ( y1 > yTop ) 00744 clipEndTop( x0, y0, x1, y1, yTop ); 00745 if ( y0 < yBottom ) 00746 clipStartBottom( x0, y0, x1, y1, yBottom ); 00747 return true; 00748 00749 case 128: 00750 clipStartTop( x0, y0, x1, y1, yTop ); 00751 return true; 00752 00753 case 129: 00754 clipStartTop( x0, y0, x1, y1, yTop ); 00755 if ( x0 < xLeft ) 00756 return false; 00757 clipEndLeft( x0, y0, x1, y1, xLeft ); 00758 return true; 00759 00760 case 130: 00761 clipStartTop( x0, y0, x1, y1, yTop ); 00762 if ( x0 > xRight ) 00763 return false; 00764 clipEndRight( x0, y0, x1, y1, xRight ); 00765 return true; 00766 00767 case 132: 00768 clipStartTop( x0, y0, x1, y1, yTop ); 00769 clipEndBottom( x0, y0, x1, y1, yBottom ); 00770 return true; 00771 00772 case 133: 00773 clipStartTop( x0, y0, x1, y1, yTop ); 00774 if ( x0 < xLeft ) 00775 return false; 00776 clipEndLeft( x0, y0, x1, y1, xLeft ); 00777 if ( y1 < yBottom ) 00778 clipEndBottom( x0, y0, x1, y1, yBottom ); 00779 return true; 00780 00781 case 134: 00782 clipStartTop( x0, y0, x1, y1, yTop ); 00783 if ( x0 > xRight ) 00784 return false; 00785 clipEndRight( x0, y0, x1, y1, xRight ); 00786 if ( y1 < yBottom ) 00787 clipEndBottom( x0, y0, x1, y1, yBottom ); 00788 return true; 00789 00790 case 144: 00791 clipStartLeft( x0, y0, x1, y1, xLeft ); 00792 if ( y0 > yTop ) 00793 clipStartTop( x0, y0, x1, y1, yTop ); 00794 return true; 00795 00796 case 146: 00797 clipEndRight( x0, y0, x1, y1, xRight ); 00798 if ( y1 > yTop ) 00799 return false; 00800 clipStartTop( x0, y0, x1, y1, yTop ); 00801 if ( x0 < xLeft ) 00802 clipStartLeft( x0, y0, x1, y1, xLeft ); 00803 return true; 00804 00805 case 148: 00806 clipEndBottom( x0, y0, x1, y1, yBottom ); 00807 if ( x1 < xLeft ) 00808 return false; 00809 clipStartLeft( x0, y0, x1, y1, xLeft ); 00810 if ( y0 > yTop ) 00811 clipStartTop( x0, y0, x1, y1, yTop ); 00812 return true; 00813 00814 case 150: 00815 clipStartLeft( x0, y0, x1, y1, xLeft ); 00816 if ( y0 < yBottom ) 00817 return false; 00818 clipEndRight( x0, y0, x1, y1, xRight ); 00819 if ( y1 > yTop ) 00820 return false; 00821 if ( y0 > yTop ) 00822 clipStartTop( x0, y0, x1, y1, yTop ); 00823 if ( y1 < yBottom ) 00824 clipEndBottom( x0, y0, x1, y1, yBottom ); 00825 return true; 00826 00827 case 160: 00828 clipStartRight( x0, y0, x1, y1, xRight ); 00829 if ( y0 > yTop ) 00830 clipStartTop( x0, y0, x1, y1, yTop ); 00831 return true; 00832 00833 case 161: 00834 clipEndLeft( x0, y0, x1, y1, xLeft ); 00835 if ( y1 > yTop ) 00836 return false; 00837 clipStartTop( x0, y0, x1, y1, yTop ); 00838 if ( x0 > xRight ) 00839 clipStartRight( x0, y0, x1, y1, xRight ); 00840 return true; 00841 00842 case 164: 00843 clipEndBottom( x0, y0, x1, y1, yBottom ); 00844 if ( x1 > xRight ) 00845 return false; 00846 clipStartRight( x0, y0, x1, y1, xRight ); 00847 if ( y0 > yTop ) 00848 clipStartTop( x0, y0, x1, y1, yTop ); 00849 return true; 00850 00851 case 165: 00852 clipEndLeft( x0, y0, x1, y1, xLeft ); 00853 if ( y1 > yTop ) 00854 return false; 00855 clipStartRight( x0, y0, x1, y1, xRight ); 00856 if ( y0 < yBottom ) 00857 return false; 00858 if ( y1 < yBottom ) 00859 clipEndBottom( x0, y0, x1, y1, yBottom ); 00860 if ( y0 > yTop ) 00861 clipStartTop( x0, y0, x1, y1, yTop ); 00862 return true; 00863 } 00864 00865 return false; 00866 00867 } 00868 00869 00870 #endif