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