Quantum GIS API Documentation  1.7.5-Wroclaw
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
qgsclipper.h
Go to the documentation of this file.
1 /***************************************************************************
2  qgsclipper.h - a class that clips line
3  segments and polygons
4  -------------------
5  begin : March 2004
6  copyright : (C) 2005 by Gavin Macaulay
7  email :
8  ***************************************************************************/
9 
10 /***************************************************************************
11  * *
12  * This program is free software; you can redistribute it and/or modify *
13  * it under the terms of the GNU General Public License as published by *
14  * the Free Software Foundation; either version 2 of the License, or *
15  * (at your option) any later version. *
16  * *
17  ***************************************************************************/
18 /* $Id$ */
19 
20 #ifndef QGSCLIPPER_H
21 #define QGSCLIPPER_H
22 
23 #include "qgis.h"
24 #include "qgspoint.h"
25 #include "qgsrectangle.h"
26 
27 #include <vector>
28 #include <utility>
29 
30 #include <QPolygonF>
31 
42 class CORE_EXPORT QgsClipper
43 {
44  public:
45 
46  // Coordinates of the rectangular box that we trim to.
47  //
48  // These are the limits for X11 screen coordinates. The actual
49  // values are +/-32767, but we allow a little bit of space for
50  // rounding errors.
51 
52  // You may wonder why the clipping is done to these coordindates
53  // rather than the boundaries of the qgis canvas. Reasons include:
54  // - making the boundaries static const allows the compiler to
55  // optimise the code that uses these values more than if they changed
56  // for every call to the trim code.
57  // - clipping takes quite a bit of CPU effort, and the less that this is
58  // done the better. More stuff would have to be clipped if the
59  // boundaries were the qgis canvas (but this may be offset by
60  // having less to draw).
61  //
62  // The limit is set to 30,000 instead of 32768 because that things
63  // still go wrong.
64 
65  static const double MAX_X;
66  static const double MIN_X;
67  static const double MAX_Y;
68  static const double MIN_Y;
69 
70 
71  // A handy way to refer to the four boundaries
72  enum Boundary {XMax, XMin, YMax, YMin};
73 
74  // Trims the given feature to a rectangular box. Returns the trimmed
75  // feature in x and y. The shapeOpen parameter determines whether
76  // the function treats the points as a closed shape (polygon), or as
77  // an open shape (linestring).
78  static void trimFeature( std::vector<double>& x,
79  std::vector<double>& y,
80  bool shapeOpen );
81 
82  static void trimPolygon( QPolygonF& pts, const QgsRectangle& clipRect );
83 
88  static unsigned char* clippedLineWKB( unsigned char* wkb, const QgsRectangle& clipExtent, QPolygonF& line );
89 
90  private:
91 
92  // Used when testing for equivalance to 0.0
93  static const double SMALL_NUM;
94 
95  // Trims the given feature to the given boundary. Returns the
96  // trimmed feature in the outX and outY vectors.
97  static void trimFeatureToBoundary( const std::vector<double>& inX,
98  const std::vector<double>& inY,
99  std::vector<double>& outX,
100  std::vector<double>& outY,
101  Boundary b,
102  bool shapeOpen );
103 
104  static void trimPolygonToBoundary( const QPolygonF& inPts, QPolygonF& outPts, const QgsRectangle& rect, Boundary b, double boundaryValue );
105 
106  // Determines if a point is inside or outside the given boundary
107  static bool inside( const double x, const double y, Boundary b );
108 
109  static bool inside( const QPointF& pt, Boundary b, double val );
110 
111  // Calculates the intersection point between a line defined by a
112  // (x1, y1), and (x2, y2) and the given boundary
113  static QgsPoint intersect( const double x1, const double y1,
114  const double x2, const double y2,
115  Boundary b );
116 
117  static QPointF intersectRect( const QPointF& pt1,
118  const QPointF& pt2,
119  Boundary b, const QgsRectangle& rect );
120 
121  //Implementation of 'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467)
122  static bool clipLineSegment( double xLeft, double xRight, double yBottom, double yTop, double& x0, double& y0, double& x1, double& y1 );
123 
132  static void connectSeparatedLines( double x0, double y0, double x1, double y1,
133  const QgsRectangle& clipRect, QPolygonF& pts );
134 
135  //low level clip methods for fast clip algorithm
136  static void clipStartTop( double& x0, double& y0, const double& x1, const double& y1, double yMax );
137  static void clipStartBottom( double& x0, double& y0, const double& x1, const double& y1, double yMin );
138  static void clipStartRight( double& x0, double& y0, const double& x1, const double& y1, double xMax );
139  static void clipStartLeft( double& x0, double& y0, const double& x1, const double& y1, double xMin );
140  static void clipEndTop( const double& x0, const double& y0, double& x1, double& y1, double yMax );
141  static void clipEndBottom( const double& x0, const double& y0, double& x1, double& y1, double yMin );
142  static void clipEndRight( const double& x0, const double& y0, double& x1, double& y1, double xMax );
143  static void clipEndLeft( const double& x0, const double& y0, double& x1, double& y1, double xMin );
144 };
145 
146 // The inline functions
147 
148 // Trim the feature using Sutherland and Hodgman's
149 // polygon-clipping algorithm. See J. D. Foley, A. van Dam,
150 // S. K. Feiner, and J. F. Hughes, Computer Graphics, Principles and
151 // Practice. Addison-Wesley Systems Programming Series,
152 // Addison-Wesley, 2nd ed., 1991.
153 
154 // I understand that this is not the most efficient algorithm, but is
155 // one (the only?) that is guaranteed to always give the correct
156 // result.
157 
158 inline void QgsClipper::trimFeature( std::vector<double>& x,
159  std::vector<double>& y,
160  bool shapeOpen )
161 {
162  std::vector<double> tmpX;
163  std::vector<double> tmpY;
164  trimFeatureToBoundary( x, y, tmpX, tmpY, XMax, shapeOpen );
165 
166  x.clear();
167  y.clear();
168  trimFeatureToBoundary( tmpX, tmpY, x, y, YMax, shapeOpen );
169 
170  tmpX.clear();
171  tmpY.clear();
172  trimFeatureToBoundary( x, y, tmpX, tmpY, XMin, shapeOpen );
173 
174  x.clear();
175  y.clear();
176  trimFeatureToBoundary( tmpX, tmpY, x, y, YMin, shapeOpen );
177 }
178 
179 inline void QgsClipper::trimPolygon( QPolygonF& pts, const QgsRectangle& clipRect )
180 {
181  QPolygonF tmpPts;
182  tmpPts.reserve( pts.size() );
183 
184  trimPolygonToBoundary( pts, tmpPts, clipRect, XMax, clipRect.xMaximum() );
185  pts.clear();
186  trimPolygonToBoundary( tmpPts, pts, clipRect, YMax, clipRect.yMaximum() );
187  tmpPts.clear();
188  trimPolygonToBoundary( pts, tmpPts, clipRect, XMin, clipRect.xMinimum() );
189  pts.clear();
190  trimPolygonToBoundary( tmpPts, pts, clipRect, YMin, clipRect.yMinimum() );
191 }
192 
193 // An auxilary function that is part of the polygon trimming
194 // code. Will trim the given polygon to the given boundary and return
195 // the trimmed polygon in the out pointer. Uses Sutherland and
196 // Hodgman's polygon-clipping algorithm.
197 
199  const std::vector<double>& inX,
200  const std::vector<double>& inY,
201  std::vector<double>& outX,
202  std::vector<double>& outY,
203  Boundary b, bool shapeOpen )
204 {
205  // The shapeOpen parameter selects whether this function treats the
206  // shape as open or closed. False is appropriate for polygons and
207  // true for polylines.
208 
209  unsigned int i1 = inX.size() - 1; // start with last point
210 
211  // and compare to the first point initially.
212  for ( unsigned int i2 = 0; i2 < inX.size() ; ++i2 )
213  {
214  // look at each edge of the polygon in turn
215 
216  //ignore segments with nan or inf coordinates
217  if ( qIsNaN( inX[i2] ) || qIsNaN( inY[i2] ) || qIsInf( inX[i2] ) || qIsInf( inY[i2] )
218  || qIsNaN( inX[i1] ) || qIsNaN( inY[i1] ) || qIsInf( inX[i1] ) || qIsInf( inY[i1] ) )
219  {
220  i1 = i2;
221  continue;
222  }
223 
224 
225  if ( inside( inX[i2], inY[i2], b ) ) // end point of edge is inside boundary
226  {
227  if ( inside( inX[i1], inY[i1], b ) )
228  {
229  outX.push_back( inX[i2] );
230  outY.push_back( inY[i2] );
231  }
232  else
233  {
234  // edge crosses into the boundary, so trim back to the boundary, and
235  // store both ends of the new edge
236  if ( !( i2 == 0 && shapeOpen ) )
237  {
238  QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
239  outX.push_back( p.x() );
240  outY.push_back( p.y() );
241  }
242 
243  outX.push_back( inX[i2] );
244  outY.push_back( inY[i2] );
245  }
246  }
247  else // end point of edge is outside boundary
248  {
249  // start point is in boundary, so need to trim back
250  if ( inside( inX[i1], inY[i1], b ) )
251  {
252  if ( !( i2 == 0 && shapeOpen ) )
253  {
254  QgsPoint p = intersect( inX[i1], inY[i1], inX[i2], inY[i2], b );
255  outX.push_back( p.x() );
256  outY.push_back( p.y() );
257  }
258  }
259  }
260  i1 = i2;
261  }
262 }
263 
264 inline void QgsClipper::trimPolygonToBoundary( const QPolygonF& inPts, QPolygonF& outPts, const QgsRectangle& rect, Boundary b, double boundaryValue )
265 {
266  unsigned int i1 = inPts.size() - 1; // start with last point
267 
268  // and compare to the first point initially.
269  for ( int i2 = 0; i2 < inPts.size() ; ++i2 )
270  { // look at each edge of the polygon in turn
271  if ( inside( inPts[i2], b, boundaryValue ) ) // end point of edge is inside boundary
272  {
273  if ( inside( inPts[i1], b, boundaryValue ) )
274  {
275  outPts.append( inPts[i2] );
276  }
277  else
278  {
279  // edge crosses into the boundary, so trim back to the boundary, and
280  // store both ends of the new edge
281  outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) );
282  outPts.append( inPts[i2] );
283  }
284  }
285  else // end point of edge is outside boundary
286  {
287  // start point is in boundary, so need to trim back
288  if ( inside( inPts[i1], b, boundaryValue ) )
289  {
290  outPts.append( intersectRect( inPts[i1], inPts[i2], b, rect ) );
291  }
292  }
293  i1 = i2;
294  }
295 }
296 
297 // An auxilary function to trimPolygonToBoundarY() that returns
298 // whether a point is inside or outside the given boundary.
299 
300 inline bool QgsClipper::inside( const double x, const double y, Boundary b )
301 {
302  switch ( b )
303  {
304  case XMax: // x < MAX_X is inside
305  if ( x < MAX_X )
306  return true;
307  break;
308  case XMin: // x > MIN_X is inside
309  if ( x > MIN_X )
310  return true;
311  break;
312  case YMax: // y < MAX_Y is inside
313  if ( y < MAX_Y )
314  return true;
315  break;
316  case YMin: // y > MIN_Y is inside
317  if ( y > MIN_Y )
318  return true;
319  break;
320  }
321  return false;
322 }
323 
324 inline bool QgsClipper::inside( const QPointF& pt, Boundary b, double val )
325 {
326  switch ( b )
327  {
328  case XMax: // x < MAX_X is inside
329  return ( pt.x() < val );
330  case XMin: // x > MIN_X is inside
331  return ( pt.x() > val );
332  case YMax: // y < MAX_Y is inside
333  return ( pt.y() < val );
334  case YMin: // y > MIN_Y is inside
335  return ( pt.y() > val );
336  }
337  return false;
338 }
339 
340 
341 // An auxilary function to trimPolygonToBoundarY() that calculates and
342 // returns the intersection of the line defined by the given points
343 // and the given boundary.
344 
345 inline QgsPoint QgsClipper::intersect( const double x1, const double y1,
346  const double x2, const double y2,
347  Boundary b )
348 {
349  // This function assumes that the two given points (x1, y1), and
350  // (x2, y2) cross the given boundary. Making this assumption allows
351  // some optimisations.
352 
353  double r_n = SMALL_NUM, r_d = SMALL_NUM;
354 
355  switch ( b )
356  {
357  case XMax: // x = MAX_X boundary
358  r_n = -( x1 - MAX_X ) * ( MAX_Y - MIN_Y );
359  r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y );
360  break;
361  case XMin: // x = MIN_X boundary
362  r_n = -( x1 - MIN_X ) * ( MAX_Y - MIN_Y );
363  r_d = ( x2 - x1 ) * ( MAX_Y - MIN_Y );
364  break;
365  case YMax: // y = MAX_Y boundary
366  r_n = ( y1 - MAX_Y ) * ( MAX_X - MIN_X );
367  r_d = -( y2 - y1 ) * ( MAX_X - MIN_X );
368  break;
369  case YMin: // y = MIN_Y boundary
370  r_n = ( y1 - MIN_Y ) * ( MAX_X - MIN_X );
371  r_d = -( y2 - y1 ) * ( MAX_X - MIN_X );
372  break;
373  }
374 
375  QgsPoint p;
376 
377  if ( qAbs( r_d ) > SMALL_NUM && qAbs( r_n ) > SMALL_NUM )
378  { // they cross
379  double r = r_n / r_d;
380  p.set( x1 + r*( x2 - x1 ), y1 + r*( y2 - y1 ) );
381  }
382  else
383  {
384  // Should never get here, but if we do for some reason, cause a
385  // clunk because something else is wrong if we do.
386  Q_ASSERT( qAbs( r_d ) > SMALL_NUM && qAbs( r_n ) > SMALL_NUM );
387  }
388 
389  return p;
390 }
391 
392 inline QPointF QgsClipper::intersectRect( const QPointF& pt1,
393  const QPointF& pt2,
394  Boundary b, const QgsRectangle& rect )
395 {
396  // This function assumes that the two given points (x1, y1), and
397  // (x2, y2) cross the given boundary. Making this assumption allows
398  // some optimisations.
399 
400  double r_n = SMALL_NUM, r_d = SMALL_NUM;
401  const double x1 = pt1.x(), x2 = pt2.x();
402  const double y1 = pt1.y(), y2 = pt2.y();
403 
404  switch ( b )
405  {
406  case XMax: // x = MAX_X boundary
407  r_n = -( x1 - rect.xMaximum() ) * ( rect.yMaximum() - rect.yMinimum() );
408  r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
409  break;
410  case XMin: // x = MIN_X boundary
411  r_n = -( x1 - rect.xMinimum() ) * ( rect.yMaximum() - rect.yMinimum() );
412  r_d = ( x2 - x1 ) * ( rect.yMaximum() - rect.yMinimum() );
413  break;
414  case YMax: // y = MAX_Y boundary
415  r_n = ( y1 - rect.yMaximum() ) * ( rect.xMaximum() - rect.xMinimum() );
416  r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
417  break;
418  case YMin: // y = MIN_Y boundary
419  r_n = ( y1 - rect.yMinimum() ) * ( rect.xMaximum() - rect.xMinimum() );
420  r_d = -( y2 - y1 ) * ( rect.xMaximum() - rect.xMinimum() );
421  break;
422  }
423 
424  double r = 0;
425  if ( !doubleNear( r_d, 0.0 ) )
426  {
427  r = r_n / r_d;
428  }
429  return QPointF( x1 + r*( x2 - x1 ), y1 + r*( y2 - y1 ) );
430 }
431 
432 inline void QgsClipper::clipStartTop( double& x0, double& y0, const double& x1, const double& y1, double yMax )
433 {
434  x0 += ( x1 - x0 ) * ( yMax - y0 ) / ( y1 - y0 );
435  y0 = yMax;
436 }
437 
438 inline void QgsClipper::clipStartBottom( double& x0, double& y0, const double& x1, const double& y1, double yMin )
439 {
440  x0 += ( x1 - x0 ) * ( yMin - y0 ) / ( y1 - y0 );
441  y0 = yMin;
442 }
443 
444 inline void QgsClipper::clipStartRight( double& x0, double& y0, const double& x1, const double& y1, double xMax )
445 {
446  y0 += ( y1 - y0 ) * ( xMax - x0 ) / ( x1 - x0 );
447  x0 = xMax;
448 }
449 
450 inline void QgsClipper::clipStartLeft( double& x0, double& y0, const double& x1, const double& y1, double xMin )
451 {
452  y0 += ( y1 - y0 ) * ( xMin - x0 ) / ( x1 - x0 );
453  x0 = xMin;
454 }
455 
456 inline void QgsClipper::clipEndTop( const double& x0, const double& y0, double& x1, double& y1, double yMax )
457 {
458  x1 += ( x1 - x0 ) * ( yMax - y1 ) / ( y1 - y0 );
459  y1 = yMax;
460 }
461 
462 inline void QgsClipper::clipEndBottom( const double& x0, const double& y0, double& x1, double& y1, double yMin )
463 {
464  x1 += ( x1 - x0 ) * ( yMin - y1 ) / ( y1 - y0 );
465  y1 = yMin;
466 }
467 
468 inline void QgsClipper::clipEndRight( const double& x0, const double& y0, double& x1, double& y1, double xMax )
469 {
470  y1 += ( y1 - y0 ) * ( xMax - x1 ) / ( x1 - x0 );
471  x1 = xMax;
472 }
473 
474 inline void QgsClipper::clipEndLeft( const double& x0, const double& y0, double& x1, double& y1, double xMin )
475 {
476  y1 += ( y1 - y0 ) * ( xMin - x1 ) / ( x1 - x0 );
477  x1 = xMin;
478 }
479 
480 //'Fast clipping' algorithm (Sobkow et al. 1987, Computers & Graphics Vol.11, 4, p.459-467)
481 inline bool QgsClipper::clipLineSegment( double xLeft, double xRight, double yBottom, double yTop, double& x0, double& y0, double& x1, double& y1 )
482 {
483  int lineCode = 0;
484 
485  if ( y1 < yBottom )
486  lineCode |= 4;
487  else if ( y1 > yTop )
488  lineCode |= 8;
489 
490  if ( x1 > xRight )
491  lineCode |= 2;
492  else if ( x1 < xLeft )
493  lineCode |= 1;
494 
495  if ( y0 < yBottom )
496  lineCode |= 64;
497  else if ( y0 > yTop )
498  lineCode |= 128;
499 
500  if ( x0 > xRight )
501  lineCode |= 32;
502  else if ( x0 < xLeft )
503  lineCode |= 16;
504 
505  switch ( lineCode )
506  {
507  case 0: //completely inside
508  return true;
509 
510  case 1:
511  clipEndLeft( x0, y0, x1, y1, xLeft );
512  return true;
513 
514  case 2:
515  clipEndRight( x0, y0, x1, y1, xRight );
516  return true;
517 
518  case 4:
519  clipEndBottom( x0, y0, x1, y1, yBottom );
520  return true;
521 
522  case 5:
523  clipEndLeft( x0, y0, x1, y1, xLeft );
524  if ( y1 < yBottom )
525  clipEndBottom( x0, y0, x1, y1, yBottom );
526  return true;
527 
528  case 6:
529  clipEndRight( x0, y0, x1, y1, xRight );
530  if ( y1 < yBottom )
531  clipEndBottom( x0, y0, x1, y1, yBottom );
532  return true;
533 
534  case 8:
535  clipEndTop( x0, y0, x1, y1, yTop );
536  return true;
537 
538  case 9:
539  clipEndLeft( x0, y0, x1, y1, xLeft );
540  if ( y1 > yTop )
541  clipEndTop( x0, y0, x1, y1, yTop );
542  return true;
543 
544  case 10:
545  clipEndRight( x0, y0, x1, y1, xRight );
546  if ( y1 > yTop )
547  clipEndTop( x0, y0, x1, y1, yTop );
548  return true;
549 
550  case 16:
551  clipStartLeft( x0, y0, x1, y1, xLeft );
552  return true;
553 
554  case 18:
555  clipStartLeft( x0, y0, x1, y1, xLeft );
556  clipEndRight( x0, y0, x1, y1, xRight );
557  return true;
558 
559  case 20:
560  clipStartLeft( x0, y0, x1, y1, xLeft );
561  if ( y0 < yBottom )
562  return false;
563  clipEndBottom( x0, y0, x1, y1, yBottom );
564  return true;
565 
566  case 22:
567  clipStartLeft( x0, y0, x1, y1, xLeft );
568  if ( y0 < yBottom )
569  return false;
570  clipEndBottom( x0, y0, x1, y1, yBottom );
571  if ( x1 > xRight )
572  clipEndRight( x0, y0, x1, y1, xRight );
573  return true;
574 
575  case 24:
576  clipStartLeft( x0, y0, x1, y1, xLeft );
577  if ( y0 > yTop )
578  return false;
579  clipEndTop( x0, y0, x1, y1, yTop );
580  return true;
581 
582  case 26:
583  clipStartLeft( x0, y0, x1, y1, xLeft );
584  if ( y0 > yTop )
585  return false;
586  clipEndTop( x0, y0, x1, y1, yTop );
587  if ( x1 > xRight )
588  clipEndRight( x0, y0, x1, y1, xRight );
589  return true;
590 
591  case 32:
592  clipStartRight( x0, y0, x1, y1, xRight );
593  return true;
594 
595  case 33:
596  clipStartRight( x0, y0, x1, y1, xRight );
597  clipEndLeft( x0, y0, x1, y1, xLeft );
598  return true;
599 
600  case 36:
601  clipStartRight( x0, y0, x1, y1, xRight );
602  if ( y0 < yBottom )
603  return false;
604  clipEndBottom( x0, y0, x1, y1, yBottom );
605  return true;
606 
607  case 37:
608  clipStartRight( x0, y0, x1, y1, xRight );
609  if ( y0 < yBottom )
610  return false;
611  clipEndBottom( x0, y0, x1, y1, yBottom );
612  if ( x1 < xLeft )
613  clipEndLeft( x0, y0, x1, y1, xLeft );
614  return true;
615 
616  case 40:
617  clipStartRight( x0, y0, x1, y1, xRight );
618  if ( y0 > yTop )
619  return false;
620  clipEndTop( x0, y0, x1, y1, yTop );
621  return true;
622 
623  case 41:
624  clipStartRight( x0, y0, x1, y1, xRight );
625  if ( y0 > yTop )
626  return false;
627  clipEndTop( x0, y0, x1, y1, yTop );
628  if ( x1 < xLeft )
629  clipEndLeft( x0, y0, x1, y1, xLeft );
630  return true;
631 
632  case 64:
633  clipStartBottom( x0, y0, x1, y1, yBottom );
634  return true;
635 
636  case 65:
637  clipStartBottom( x0, y0, x1, y1, yBottom );
638  if ( x0 < xLeft )
639  return false;
640  clipEndLeft( x0, y0, x1, y1, xLeft );
641  if ( y1 < yBottom )
642  clipEndBottom( x0, y0, x1, y1, yBottom );
643  return true;
644 
645  case 66:
646  clipStartBottom( x0, y0, x1, y1, yBottom );
647  if ( x0 > xRight )
648  return false;
649  clipEndRight( x0, y0, x1, y1, xRight );
650  return true;
651 
652  case 72:
653  clipStartBottom( x0, y0, x1, y1, yBottom );
654  clipEndTop( x0, y0, x1, y1, yTop );
655  return true;
656 
657  case 73:
658  clipStartBottom( x0, y0, x1, y1, yBottom );
659  if ( x0 < xLeft )
660  return false;
661  clipEndLeft( x0, y0, x1, y1, xLeft );
662  if ( y1 > yTop )
663  clipEndTop( x0, y0, x1, y1, yTop );
664  return true;
665 
666  case 74:
667  clipStartBottom( x0, y0, x1, y1, yBottom );
668  if ( x0 > xRight )
669  return false;
670  clipEndRight( x0, y0, x1, y1, xRight );
671  if ( y1 > yTop )
672  clipEndTop( x0, y0, x1, y1, yTop );
673  return true;
674 
675  case 80:
676  clipStartLeft( x0, y0, x1, y1, xLeft );
677  if ( y0 < yBottom )
678  clipStartBottom( x0, y0, x1, y1, yBottom );
679  return true;
680 
681  case 82:
682  clipEndRight( x0, y0, x1, y1, xRight );
683  if ( y1 < yBottom )
684  return false;
685  clipStartBottom( x0, y0, x1, y1, yBottom );
686  if ( x0 < xLeft )
687  clipStartLeft( x0, y0, x1, y1, xLeft );
688  return true;
689 
690  case 88:
691  clipEndTop( x0, y0, x1, y1, yTop );
692  if ( x1 < xLeft )
693  return false;
694  clipStartBottom( x0, y0, x1, y1, yBottom );
695  if ( x0 < xLeft )
696  clipStartLeft( x0, y0, x1, y1, xLeft );
697  return true;
698 
699  case 90:
700  clipStartLeft( x0, y0, x1, y1, xLeft );
701  if ( y0 > yTop )
702  return false;
703  clipEndRight( x0, y0, x1, y1, xRight );
704  if ( y1 < yBottom )
705  return false;
706  if ( y0 < yBottom )
707  clipStartBottom( x0, y0, x1, y1, yBottom );
708  if ( y1 > yTop )
709  clipEndTop( x0, y0, x1, y1, yTop );
710  return true;
711 
712  case 96:
713  clipStartRight( x0, y0, x1, y1, xRight );
714  if ( y0 < yBottom )
715  clipStartBottom( x0, y0, x1, y1, yBottom );
716  return true;
717 
718  case 97:
719  clipEndLeft( x0, y0, x1, y1, xLeft );
720  if ( y1 < yBottom )
721  return false;
722  clipStartBottom( x0, y0, x1, y1, yBottom );
723  if ( x0 > xRight )
724  clipStartRight( x0, y0, x1, y1, xRight );
725  return true;
726 
727  case 104:
728  clipEndTop( x0, y0, x1, y1, yTop );
729  if ( x1 > xRight )
730  return false;
731  clipStartRight( x0, y0, x1, y1, xRight );
732  if ( y0 < yBottom )
733  clipStartBottom( x0, y0, x1, y1, yBottom );
734  return true;
735 
736  case 105:
737  clipEndLeft( x0, y0, x1, y1, xLeft );
738  if ( y1 < yBottom )
739  return false;
740  clipStartRight( x0, y0, x1, y1, xRight );
741  if ( y0 > yTop )
742  return false;
743  if ( y1 > yTop )
744  clipEndTop( x0, y0, x1, y1, yTop );
745  if ( y0 < yBottom )
746  clipStartBottom( x0, y0, x1, y1, yBottom );
747  return true;
748 
749  case 128:
750  clipStartTop( x0, y0, x1, y1, yTop );
751  return true;
752 
753  case 129:
754  clipStartTop( x0, y0, x1, y1, yTop );
755  if ( x0 < xLeft )
756  return false;
757  clipEndLeft( x0, y0, x1, y1, xLeft );
758  return true;
759 
760  case 130:
761  clipStartTop( x0, y0, x1, y1, yTop );
762  if ( x0 > xRight )
763  return false;
764  clipEndRight( x0, y0, x1, y1, xRight );
765  return true;
766 
767  case 132:
768  clipStartTop( x0, y0, x1, y1, yTop );
769  clipEndBottom( x0, y0, x1, y1, yBottom );
770  return true;
771 
772  case 133:
773  clipStartTop( x0, y0, x1, y1, yTop );
774  if ( x0 < xLeft )
775  return false;
776  clipEndLeft( x0, y0, x1, y1, xLeft );
777  if ( y1 < yBottom )
778  clipEndBottom( x0, y0, x1, y1, yBottom );
779  return true;
780 
781  case 134:
782  clipStartTop( x0, y0, x1, y1, yTop );
783  if ( x0 > xRight )
784  return false;
785  clipEndRight( x0, y0, x1, y1, xRight );
786  if ( y1 < yBottom )
787  clipEndBottom( x0, y0, x1, y1, yBottom );
788  return true;
789 
790  case 144:
791  clipStartLeft( x0, y0, x1, y1, xLeft );
792  if ( y0 > yTop )
793  clipStartTop( x0, y0, x1, y1, yTop );
794  return true;
795 
796  case 146:
797  clipEndRight( x0, y0, x1, y1, xRight );
798  if ( y1 > yTop )
799  return false;
800  clipStartTop( x0, y0, x1, y1, yTop );
801  if ( x0 < xLeft )
802  clipStartLeft( x0, y0, x1, y1, xLeft );
803  return true;
804 
805  case 148:
806  clipEndBottom( x0, y0, x1, y1, yBottom );
807  if ( x1 < xLeft )
808  return false;
809  clipStartLeft( x0, y0, x1, y1, xLeft );
810  if ( y0 > yTop )
811  clipStartTop( x0, y0, x1, y1, yTop );
812  return true;
813 
814  case 150:
815  clipStartLeft( x0, y0, x1, y1, xLeft );
816  if ( y0 < yBottom )
817  return false;
818  clipEndRight( x0, y0, x1, y1, xRight );
819  if ( y1 > yTop )
820  return false;
821  if ( y0 > yTop )
822  clipStartTop( x0, y0, x1, y1, yTop );
823  if ( y1 < yBottom )
824  clipEndBottom( x0, y0, x1, y1, yBottom );
825  return true;
826 
827  case 160:
828  clipStartRight( x0, y0, x1, y1, xRight );
829  if ( y0 > yTop )
830  clipStartTop( x0, y0, x1, y1, yTop );
831  return true;
832 
833  case 161:
834  clipEndLeft( x0, y0, x1, y1, xLeft );
835  if ( y1 > yTop )
836  return false;
837  clipStartTop( x0, y0, x1, y1, yTop );
838  if ( x0 > xRight )
839  clipStartRight( x0, y0, x1, y1, xRight );
840  return true;
841 
842  case 164:
843  clipEndBottom( x0, y0, x1, y1, yBottom );
844  if ( x1 > xRight )
845  return false;
846  clipStartRight( x0, y0, x1, y1, xRight );
847  if ( y0 > yTop )
848  clipStartTop( x0, y0, x1, y1, yTop );
849  return true;
850 
851  case 165:
852  clipEndLeft( x0, y0, x1, y1, xLeft );
853  if ( y1 > yTop )
854  return false;
855  clipStartRight( x0, y0, x1, y1, xRight );
856  if ( y0 < yBottom )
857  return false;
858  if ( y1 < yBottom )
859  clipEndBottom( x0, y0, x1, y1, yBottom );
860  if ( y0 > yTop )
861  clipStartTop( x0, y0, x1, y1, yTop );
862  return true;
863  }
864 
865  return false;
866 
867 }
868 
869 
870 #endif