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