diff options
Diffstat (limited to 'src/kernel/qpointarray.cpp')
| -rw-r--r-- | src/kernel/qpointarray.cpp | 1109 |
1 files changed, 1109 insertions, 0 deletions
diff --git a/src/kernel/qpointarray.cpp b/src/kernel/qpointarray.cpp new file mode 100644 index 000000000..8659c5181 --- /dev/null +++ b/src/kernel/qpointarray.cpp @@ -0,0 +1,1109 @@ +/**************************************************************************** +** +** Implementation of TQPointArray class +** +** Created : 940213 +** +** Copyright (C) 1992-2008 Trolltech ASA. All rights reserved. +** +** This file is part of the kernel module of the TQt GUI Toolkit. +** +** This file may be used under the terms of the GNU General +** Public License versions 2.0 or 3.0 as published by the Free +** Software Foundation and appearing in the files LICENSE.GPL2 +** and LICENSE.GPL3 included in the packaging of this file. +** Alternatively you may (at your option) use any later version +** of the GNU General Public License if such license has been +** publicly approved by Trolltech ASA (or its successors, if any) +** and the KDE Free TQt Foundation. +** +** Please review the following information to ensure GNU General +** Public Licensing retquirements will be met: +** http://trolltech.com/products/qt/licenses/licensing/opensource/. +** If you are unsure which license is appropriate for your use, please +** review the following information: +** http://trolltech.com/products/qt/licenses/licensing/licensingoverview +** or contact the sales department at sales@trolltech.com. +** +** This file may be used under the terms of the Q Public License as +** defined by Trolltech ASA and appearing in the file LICENSE.TQPL +** included in the packaging of this file. Licensees holding valid TQt +** Commercial licenses may use this file in accordance with the TQt +** Commercial License Agreement provided with the Software. +** +** This file is provided "AS IS" with NO WARRANTY OF ANY KIND, +** INCLUDING THE WARRANTIES OF DESIGN, MERCHANTABILITY AND FITNESS FOR +** A PARTICULAR PURPOSE. Trolltech reserves all rights not granted +** herein. +** +**********************************************************************/ + +#include "qpointarray.h" +#include "qrect.h" +#include "qdatastream.h" +#include "qwmatrix.h" +#include <stdarg.h> + +const double Q_PI = 3.14159265358979323846; // pi // one more useful comment + + +/*! + \class TQPointArray qpointarray.h + \brief The TQPointArray class provides an array of points. + + \ingroup images + \ingroup graphics + \ingroup shared + + A TQPointArray is an array of TQPoint objects. In addition to the + functions provided by TQMemArray, TQPointArray provides some + point-specific functions. + + For convenient reading and writing of the point data use + setPoints(), putPoints(), point(), and setPoint(). + + For geometry operations use boundingRect() and translate(). There + is also the TQWMatrix::map() function for more general + transformations of TQPointArrays. You can also create arcs and + ellipses with makeArc() and makeEllipse(). + + Among others, TQPointArray is used by TQPainter::drawLineSegments(), + TQPainter::drawPolyline(), TQPainter::drawPolygon() and + TQPainter::drawCubicBezier(). + + Note that because this class is a TQMemArray, copying an array and + modifying the copy modifies the original as well, i.e. a shallow + copy. If you need a deep copy use copy() or detach(), for example: + + \code + void drawGiraffe( const TQPointArray & r, TQPainter * p ) + { + TQPointArray tmp = r; + tmp.detach(); + // some code that modifies tmp + p->drawPoints( tmp ); + } + \endcode + + If you forget the tmp.detach(), the const array will be modified. + + \sa TQPainter TQWMatrix TQMemArray +*/ + + +/***************************************************************************** + TQPointArray member functions + *****************************************************************************/ + +/*! + \fn TQPointArray::TQPointArray() + + Constructs a null point array. + + \sa isNull() +*/ + +/*! + \fn TQPointArray::TQPointArray( int size ) + + Constructs a point array with room for \a size points. Makes a + null array if \a size == 0. + + \sa resize(), isNull() +*/ + +/*! + \fn TQPointArray::TQPointArray( const TQPointArray &a ) + + Constructs a shallow copy of the point array \a a. + + \sa copy() detach() +*/ + +/*! + Constructs a point array from the rectangle \a r. + + If \a closed is FALSE, then the point array just contains the + following four points in the listed order: r.topLeft(), + r.topRight(), r.bottomRight() and r.bottomLeft(). + + If \a closed is TRUE, then a fifth point is set to r.topLeft(). +*/ + +TQPointArray::TQPointArray( const TQRect &r, bool closed ) +{ + setPoints( 4, r.left(), r.top(), + r.right(), r.top(), + r.right(), r.bottom(), + r.left(), r.bottom() ); + if ( closed ) { + resize( 5 ); + setPoint( 4, r.left(), r.top() ); + } +} + +/*! + \internal + Constructs a point array with \a nPoints points, taken from the + \a points array. + + Equivalent to setPoints(nPoints, points). +*/ + +TQPointArray::TQPointArray( int nPoints, const TQCOORD *points ) +{ + setPoints( nPoints, points ); +} + + +/*! + \fn TQPointArray::~TQPointArray() + + Destroys the point array. +*/ + + +/*! + \fn TQPointArray &TQPointArray::operator=( const TQPointArray &a ) + + Assigns a shallow copy of \a a to this point array and returns a + reference to this point array. + + Equivalent to assign(a). + + \sa copy() detach() +*/ + +/*! + \fn TQPointArray TQPointArray::copy() const + + Creates a deep copy of the array. + + \sa detach() +*/ + + + +/*! + Translates all points in the array by \a (dx, dy). +*/ + +void TQPointArray::translate( int dx, int dy ) +{ + register TQPoint *p = data(); + register int i = size(); + TQPoint pt( dx, dy ); + while ( i-- ) { + *p += pt; + p++; + } +} + + +/*! + Reads the coordinates of the point at position \a index within the + array and writes them into \a *x and \a *y. +*/ + +void TQPointArray::point( uint index, int *x, int *y ) const +{ + TQPoint p = TQMemArray<TQPoint>::at( index ); + if ( x ) + *x = (int)p.x(); + if ( y ) + *y = (int)p.y(); +} + +/*! + \overload + + Returns the point at position \a index within the array. +*/ + +TQPoint TQPointArray::point( uint index ) const +{ // #### index out of bounds + return TQMemArray<TQPoint>::at( index ); +} + +/*! + \fn void TQPointArray::setPoint( uint i, const TQPoint &p ) + + \overload + + Sets the point at array index \a i to \a p. +*/ + +/*! + Sets the point at position \a index in the array to \a (x, y). +*/ + +void TQPointArray::setPoint( uint index, int x, int y ) +{ // #### index out of bounds + TQMemArray<TQPoint>::at( index ) = TQPoint( x, y ); +} + +/*! + \internal + Resizes the array to \a nPoints and sets the points in the array to + the values taken from \a points. + + Returns TRUE if successful, or FALSE if the array could not be + resized (normally due to lack of memory). + + The example code creates an array with two points (1,2) and (3,4): + \code + static TQCOORD points[] = { 1,2, 3,4 }; + TQPointArray a; + a.setPoints( 2, points ); + \endcode + + \sa resize(), putPoints() +*/ + +bool TQPointArray::setPoints( int nPoints, const TQCOORD *points ) +{ + if ( !resize(nPoints) ) + return FALSE; + int i = 0; + while ( nPoints-- ) { // make array of points + setPoint( i++, *points, *(points+1) ); + points++; + points++; + } + return TRUE; +} + +/*! + \overload + + Resizes the array to \a nPoints and sets the points in the array + to the values taken from the variable argument list. + + Returns TRUE if successful, or FALSE if the array could not be + resized (typically due to lack of memory). + + The example code creates an array with two points (1,2) and (3,4): + + \code + TQPointArray a; + a.setPoints( 2, 1,2, 3,4 ); + \endcode + + The points are given as a sequence of integers, starting with \a + firstx then \a firsty, and so on. + + \sa resize(), putPoints() +*/ + +bool TQPointArray::setPoints( int nPoints, int firstx, int firsty, ... ) +{ + va_list ap; + if ( !resize(nPoints) ) + return FALSE; + setPoint( 0, firstx, firsty ); // set first point + int i = 1, x, y; + nPoints--; + va_start( ap, firsty ); + while ( nPoints-- ) { + x = va_arg( ap, int ); + y = va_arg( ap, int ); + setPoint( i++, x, y ); + } + va_end( ap ); + return TRUE; +} + +/*! \overload + \internal + Copies \a nPoints points from the \a points coord array into + this point array, and resizes the point array if + \c{index+nPoints} exceeds the size of the array. + + Returns TRUE if successful, or FALSE if the array could not be + resized (typically due to lack of memory). + +*/ + +bool TQPointArray::putPoints( int index, int nPoints, const TQCOORD *points ) +{ + if ( index + nPoints > (int)size() ) { // extend array + if ( !resize( index + nPoints ) ) + return FALSE; + } + int i = index; + while ( nPoints-- ) { // make array of points + setPoint( i++, *points, *(points+1) ); + points++; + points++; + } + return TRUE; +} + +/*! + Copies \a nPoints points from the variable argument list into this + point array from position \a index, and resizes the point array if + \c{index+nPoints} exceeds the size of the array. + + Returns TRUE if successful, or FALSE if the array could not be + resized (typically due to lack of memory). + + The example code creates an array with three points (4,5), (6,7) + and (8,9), by expanding the array from 1 to 3 points: + + \code + TQPointArray a( 1 ); + a[0] = TQPoint( 4, 5 ); + a.putPoints( 1, 2, 6,7, 8,9 ); // index == 1, points == 2 + \endcode + + This has the same result, but here putPoints overwrites rather + than extends: + \code + TQPointArray a( 3 ); + a.putPoints( 0, 3, 4,5, 0,0, 8,9 ); + a.putPoints( 1, 1, 6,7 ); + \endcode + + The points are given as a sequence of integers, starting with \a + firstx then \a firsty, and so on. + + \sa resize() +*/ + +bool TQPointArray::putPoints( int index, int nPoints, int firstx, int firsty, + ... ) +{ + va_list ap; + if ( index + nPoints > (int)size() ) { // extend array + if ( !resize(index + nPoints) ) + return FALSE; + } + if ( nPoints <= 0 ) + return TRUE; + setPoint( index, firstx, firsty ); // set first point + int i = index + 1, x, y; + nPoints--; + va_start( ap, firsty ); + while ( nPoints-- ) { + x = va_arg( ap, int ); + y = va_arg( ap, int ); + setPoint( i++, x, y ); + } + va_end( ap ); + return TRUE; +} + + +/*! + \overload + + This version of the function copies \a nPoints from \a from into + this array, starting at \a index in this array and \a fromIndex in + \a from. \a fromIndex is 0 by default. + + \code + TQPointArray a; + a.putPoints( 0, 3, 1,2, 0,0, 5,6 ); + // a is now the three-point array ( 1,2, 0,0, 5,6 ); + TQPointArray b; + b.putPoints( 0, 3, 4,4, 5,5, 6,6 ); + // b is now ( 4,4, 5,5, 6,6 ); + a.putPoints( 2, 3, b ); + // a is now ( 1,2, 0,0, 4,4, 5,5, 6,6 ); + \endcode +*/ + +bool TQPointArray::putPoints( int index, int nPoints, + const TQPointArray & from, int fromIndex ) +{ + if ( index + nPoints > (int)size() ) { // extend array + if ( !resize(index + nPoints) ) + return FALSE; + } + if ( nPoints <= 0 ) + return TRUE; + int n = 0; + while( n < nPoints ) { + setPoint( index+n, from[fromIndex+n] ); + n++; + } + return TRUE; +} + + +/*! + Returns the bounding rectangle of the points in the array, or + TQRect(0,0,0,0) if the array is empty. +*/ + +TQRect TQPointArray::boundingRect() const +{ + if ( isEmpty() ) + return TQRect( 0, 0, 0, 0 ); // null rectangle + register TQPoint *pd = data(); + int minx, maxx, miny, maxy; + minx = maxx = pd->x(); + miny = maxy = pd->y(); + pd++; + for ( int i=1; i<(int)size(); i++ ) { // find min+max x and y + if ( pd->x() < minx ) + minx = pd->x(); + else if ( pd->x() > maxx ) + maxx = pd->x(); + if ( pd->y() < miny ) + miny = pd->y(); + else if ( pd->y() > maxy ) + maxy = pd->y(); + pd++; + } + return TQRect( TQPoint(minx,miny), TQPoint(maxx,maxy) ); +} + + +static inline int fix_angle( int a ) +{ + if ( a > 16*360 ) + a %= 16*360; + else if ( a < -16*360 ) { + a = -( (-a) % (16*360) ); + } + return a; +} + +/*! + Sets the points of the array to those describing an arc of an + ellipse with size, width \a w by height \a h, and position (\a x, + \a y), starting from angle \a a1 and spanning by angle \a a2. The + resulting array has sufficient resolution for pixel accuracy (see + the overloaded function which takes an additional TQWMatrix + parameter). + + Angles are specified in 16ths of a degree, i.e. a full circle + equals 5760 (16*360). Positive values mean counter-clockwise, + whereas negative values mean the clockwise direction. Zero degrees + is at the 3 o'clock position. + + See the \link qcanvasellipse.html#anglediagram angle diagram\endlink. +*/ + +void TQPointArray::makeArc( int x, int y, int w, int h, int a1, int a2 ) +{ +#if !defined(QT_OLD_MAKEELLIPSE) && !defined(QT_NO_TRANSFORMATIONS) + TQWMatrix unit; + makeArc(x,y,w,h,a1,a2,unit); +#else + a1 = fix_angle( a1 ); + if ( a1 < 0 ) + a1 += 16*360; + a2 = fix_angle( a2 ); + int a3 = a2 > 0 ? a2 : -a2; // abs angle + makeEllipse( x, y, w, h ); + int npts = a3*size()/(16*360); // # points in arc array + TQPointArray a(npts); + int i = a1*size()/(16*360); + int j = 0; + if ( a2 > 0 ) { + while ( npts-- ) { + if ( i >= (int)size() ) // wrap index + i = 0; + a.TQMemArray<TQPoint>::at( j++ ) = TQMemArray<TQPoint>::at( i++ ); + } + } else { + while ( npts-- ) { + if ( i < 0 ) // wrap index + i = (int)size()-1; + a.TQMemArray<TQPoint>::at( j++ ) = TQMemArray<TQPoint>::at( i-- ); + } + } + *this = a; + return; +#endif +} + +#ifndef QT_NO_TRANSFORMATIONS +// Based upon: +// parelarc.c from Graphics Gems III +// VanAken / Simar, "A Parametric Elliptical Arc Algorithm" +// +static void +qtr_elips(TQPointArray& a, int off, double dxP, double dyP, double dxQ, double dyQ, double dxK, double dyK, int m) +{ +#define PIV2 102944 /* fixed point PI/2 */ +#define TWOPI 411775 /* fixed point 2*PI */ +#define HALF 32768 /* fixed point 1/2 */ + + int xP, yP, xQ, yQ, xK, yK; + xP = int(dxP * 65536.0); yP = int(dyP * 65536.0); + xQ = int(dxQ * 65536.0); yQ = int(dyQ * 65536.0); + xK = int(dxK * 65536.0); yK = int(dyK * 65536.0); + + int i; + int vx, ux, vy, uy, xJ, yJ; + + vx = xK - xQ; /* displacements from center */ + ux = xK - xP; + vy = yK - yQ; + uy = yK - yP; + xJ = xP - vx + HALF; /* center of ellipse J */ + yJ = yP - vy + HALF; + + int r; + ux -= (r = ux >> (2*m + 3)); /* cancel 2nd-order error */ + ux -= (r >>= (2*m + 4)); /* cancel 4th-order error */ + ux -= r >> (2*m + 3); /* cancel 6th-order error */ + ux += vx >> (m + 1); /* cancel 1st-order error */ + uy -= (r = uy >> (2*m + 3)); /* cancel 2nd-order error */ + uy -= (r >>= (2*m + 4)); /* cancel 4th-order error */ + uy -= r >> (2*m + 3); /* cancel 6th-order error */ + uy += vy >> (m + 1); /* cancel 1st-order error */ + + const int qn = a.size()/4; + for (i = 0; i < qn; i++) { + a[off+i] = TQPoint((xJ + vx) >> 16, (yJ + vy) >> 16); + ux -= vx >> m; + vx += ux >> m; + uy -= vy >> m; + vy += uy >> m; + } + +#undef PIV2 +#undef TWOPI +#undef HALF +} + + +/*! + \overload + + Sets the points of the array to those describing an arc of an + ellipse with width \a w and height \a h and position (\a x, \a y), + starting from angle \a a1, and spanning angle by \a a2, and + transformed by the matrix \a xf. The resulting array has + sufficient resolution for pixel accuracy. + + Angles are specified in 16ths of a degree, i.e. a full circle + equals 5760 (16*360). Positive values mean counter-clockwise, + whereas negative values mean the clockwise direction. Zero degrees + is at the 3 o'clock position. + + See the \link qcanvasellipse.html#anglediagram angle diagram\endlink. +*/ +void TQPointArray::makeArc( int x, int y, int w, int h, + int a1, int a2, + const TQWMatrix& xf ) +{ +#define PIV2 102944 /* fixed point PI/2 */ + if ( --w < 0 || --h < 0 || !a2 ) { + resize( 0 ); + return; + } + + bool rev = a2 < 0; + if ( rev ) { + a1 += a2; + a2 = -a2; + } + a1 = fix_angle( a1 ); + if ( a1 < 0 ) + a1 += 16*360; + a2 = fix_angle( a2 ); + + bool arc = a1 != 0 || a2 != 360*16 || rev; + + double xP, yP, xQ, yQ, xK, yK; + + xf.map(x+w, y+h/2.0, &xP, &yP); + xf.map(x+w/2.0, y, &xQ, &yQ); + xf.map(x+w, y, &xK, &yK); + + int m = 3; + int max; + int q = int(TQMAX(TQABS(xP-xQ),TQABS(yP-yQ))); + if ( arc ) + q *= 2; + do { + m++; + max = 4*(1 + (PIV2 >> (16 - m)) ); + } while (max < q && m < 16); // 16 limits memory usage on HUGE arcs + + double inc = 1.0/(1<<m); + + const int qn = (PIV2 >> (16 - m)); + resize(qn*4); + + qtr_elips(*this, 0, xP, yP, xQ, yQ, xK, yK, m); + xP = xQ; yP = yQ; + xf.map(x, y+h/2.0, &xQ, &yQ); + xf.map(x, y, &xK, &yK); + qtr_elips(*this, qn, xP, yP, xQ, yQ, xK, yK, m); + xP = xQ; yP = yQ; + xf.map(x+w/2.0, y+h, &xQ, &yQ); + xf.map(x, y+h, &xK, &yK); + qtr_elips(*this, qn*2, xP, yP, xQ, yQ, xK, yK, m); + xP = xQ; yP = yQ; + xf.map(x+w, y+h/2.0, &xQ, &yQ); + xf.map(x+w, y+h, &xK, &yK); + qtr_elips(*this, qn*3, xP, yP, xQ, yQ, xK, yK, m); + + int n = size(); + + if ( arc ) { + double da1 = double(a1)*Q_PI / (360*8); + double da3 = double(a2+a1)*Q_PI / (360*8); + int i = int(da1/inc+0.5); + int l = int(da3/inc+0.5); + int k = (l-i)+1; + TQPointArray r(k); + int j = 0; + + if ( rev ) { + while ( k-- ) + r[j++] = at((i+k)%n); + } else { + while ( j < k ) { + r[j] = at((i+j)%n); + j++; + } + } + *this = r; + } +#undef PIV2 +} + +#endif // QT_NO_TRANSFORMATIONS + +/*! + Sets the points of the array to those describing an ellipse with + size, width \a w by height \a h, and position (\a x, \a y). + + The returned array has sufficient resolution for use as pixels. +*/ +void TQPointArray::makeEllipse( int x, int y, int w, int h ) +{ // midpoint, 1/4 ellipse +#if !defined(QT_OLD_MAKEELLIPSE) && !defined(QT_NO_TRANSFORMATIONS) + TQWMatrix unit; + makeArc(x,y,w,h,0,360*16,unit); + return; +#else + if ( w <= 0 || h <= 0 ) { + if ( w == 0 || h == 0 ) { + resize( 0 ); + return; + } + if ( w < 0 ) { // negative width + w = -w; + x -= w; + } + if ( h < 0 ) { // negative height + h = -h; + y -= h; + } + } + int s = (w+h+2)/2; // max size of xx,yy array + int *px = new int[s]; // 1/4th of ellipse + int *py = new int[s]; + int xx, yy, i=0; + double d1, d2; + double a2=(w/2)*(w/2), b2=(h/2)*(h/2); + xx = 0; + yy = int(h/2); + d1 = b2 - a2*(h/2) + 0.25*a2; + px[i] = xx; + py[i] = yy; + i++; + while ( a2*(yy-0.5) > b2*(xx+0.5) ) { // region 1 + if ( d1 < 0 ) { + d1 = d1 + b2*(3.0+2*xx); + xx++; + } else { + d1 = d1 + b2*(3.0+2*xx) + 2.0*a2*(1-yy); + xx++; + yy--; + } + px[i] = xx; + py[i] = yy; + i++; + } + d2 = b2*(xx+0.5)*(xx+0.5) + a2*(yy-1)*(yy-1) - a2*b2; + while ( yy > 0 ) { // region 2 + if ( d2 < 0 ) { + d2 = d2 + 2.0*b2*(xx+1) + a2*(3-2*yy); + xx++; + yy--; + } else { + d2 = d2 + a2*(3-2*yy); + yy--; + } + px[i] = xx; + py[i] = yy; + i++; + } + s = i; + resize( 4*s ); // make full point array + x += w/2; + y += h/2; + for ( i=0; i<s; i++ ) { // mirror + xx = px[i]; + yy = py[i]; + setPoint( s-i-1, x+xx, y-yy ); + setPoint( s+i, x-xx, y-yy ); + setPoint( 3*s-i-1, x-xx, y+yy ); + setPoint( 3*s+i, x+xx, y+yy ); + } + delete[] px; + delete[] py; +#endif +} + +#ifndef QT_NO_BEZIER +// Work functions for TQPointArray::cubicBezier() +static +void split(const double *p, double *l, double *r) +{ + double tmpx; + double tmpy; + + l[0] = p[0]; + l[1] = p[1]; + r[6] = p[6]; + r[7] = p[7]; + + l[2] = (p[0]+ p[2])/2; + l[3] = (p[1]+ p[3])/2; + tmpx = (p[2]+ p[4])/2; + tmpy = (p[3]+ p[5])/2; + r[4] = (p[4]+ p[6])/2; + r[5] = (p[5]+ p[7])/2; + + l[4] = (l[2]+ tmpx)/2; + l[5] = (l[3]+ tmpy)/2; + r[2] = (tmpx + r[4])/2; + r[3] = (tmpy + r[5])/2; + + l[6] = (l[4]+ r[2])/2; + l[7] = (l[5]+ r[3])/2; + r[0] = l[6]; + r[1] = l[7]; +} + +// Based on: +// +// A Fast 2D Point-On-Line Test +// by Alan Paeth +// from "Graphics Gems", Academic Press, 1990 +static +int pnt_on_line( const int* p, const int* q, const int* t ) +{ +/* + * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty) + * return 0 if T is not on the line through <--P--Q--> + * 1 if T is on the open ray ending at P: <--P + * 2 if T is on the closed interior along: P--Q + * 3 if T is on the open ray beginning at Q: Q--> + * + * Example: consider the line P = (3,2), Q = (17,7). A plot + * of the test points T(x,y) (with 0 mapped onto '.') yields: + * + * 8| . . . . . . . . . . . . . . . . . 3 3 + * Y 7| . . . . . . . . . . . . . . 2 2 Q 3 3 Q = 2 + * 6| . . . . . . . . . . . 2 2 2 2 2 . . . + * a 5| . . . . . . . . 2 2 2 2 2 2 . . . . . + * x 4| . . . . . 2 2 2 2 2 2 . . . . . . . . + * i 3| . . . 2 2 2 2 2 . . . . . . . . . . . + * s 2| 1 1 P 2 2 . . . . . . . . . . . . . . P = 2 + * 1| 1 1 . . . . . . . . . . . . . . . . . + * +-------------------------------------- + * 1 2 3 4 5 X-axis 10 15 19 + * + * Point-Line distance is normalized with the Infinity Norm + * avoiding square-root code and tightening the test vs the + * Manhattan Norm. All math is done on the field of integers. + * The latter replaces the initial ">= MAX(...)" test with + * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality + * and norm, yielding a broader target line for selection. + * The tightest test is employed here for best discrimination + * in merging collinear (to grid coordinates) vertex chains + * into a larger, spanning vectors within the Lemming editor. + */ + + // if all points are coincident, return condition 2 (on line) + if(q[0]==p[0] && q[1]==p[1] && q[0]==t[0] && q[1]==t[1]) { + return 2; + } + + if ( TQABS((q[1]-p[1])*(t[0]-p[0])-(t[1]-p[1])*(q[0]-p[0])) >= + (TQMAX(TQABS(q[0]-p[0]), TQABS(q[1]-p[1])))) return 0; + + if (((q[0]<p[0])&&(p[0]<t[0])) || ((q[1]<p[1])&&(p[1]<t[1]))) + return 1 ; + if (((t[0]<p[0])&&(p[0]<q[0])) || ((t[1]<p[1])&&(p[1]<q[1]))) + return 1 ; + if (((p[0]<q[0])&&(q[0]<t[0])) || ((p[1]<q[1])&&(q[1]<t[1]))) + return 3 ; + if (((t[0]<q[0])&&(q[0]<p[0])) || ((t[1]<q[1])&&(q[1]<p[1]))) + return 3 ; + + return 2 ; +} +static +void polygonizeTQBezier( double* acc, int& accsize, const double ctrl[], + int maxsize ) +{ + if ( accsize > maxsize / 2 ) + { + // This never happens in practice. + + if ( accsize >= maxsize-4 ) + return; + // Running out of space - approximate by a line. + acc[accsize++] = ctrl[0]; + acc[accsize++] = ctrl[1]; + acc[accsize++] = ctrl[6]; + acc[accsize++] = ctrl[7]; + return; + } + + //intersects: + double l[8]; + double r[8]; + split( ctrl, l, r); + + // convert to integers for line condition check + int c0[2]; c0[0] = int(ctrl[0]); c0[1] = int(ctrl[1]); + int c1[2]; c1[0] = int(ctrl[2]); c1[1] = int(ctrl[3]); + int c2[2]; c2[0] = int(ctrl[4]); c2[1] = int(ctrl[5]); + int c3[2]; c3[0] = int(ctrl[6]); c3[1] = int(ctrl[7]); + + // #### Duplication needed? + if ( TQABS(c1[0]-c0[0]) <= 1 && TQABS(c1[1]-c0[1]) <= 1 + && TQABS(c2[0]-c0[0]) <= 1 && TQABS(c2[1]-c0[1]) <= 1 + && TQABS(c3[0]-c1[0]) <= 1 && TQABS(c3[1]-c0[1]) <= 1 ) + { + // Approximate by one line. + // Dont need to write last pt as it is the same as first pt + // on the next segment + acc[accsize++] = l[0]; + acc[accsize++] = l[1]; + return; + } + + if ( ( pnt_on_line( c0, c3, c1 ) == 2 && pnt_on_line( c0, c3, c2 ) == 2 ) + || ( TQABS(c1[0]-c0[0]) <= 1 && TQABS(c1[1]-c0[1]) <= 1 + && TQABS(c2[0]-c0[0]) <= 1 && TQABS(c2[1]-c0[1]) <= 1 + && TQABS(c3[0]-c1[0]) <= 1 && TQABS(c3[1]-c0[1]) <= 1 ) ) + { + // Approximate by one line. + // Dont need to write last pt as it is the same as first pt + // on the next segment + acc[accsize++] = l[0]; + acc[accsize++] = l[1]; + return; + } + + // Too big and too curved - recusively subdivide. + polygonizeTQBezier( acc, accsize, l, maxsize ); + polygonizeTQBezier( acc, accsize, r, maxsize ); +} + +/*! + Returns the Bezier points for the four control points in this + array. +*/ + +TQPointArray TQPointArray::cubicBezier() const +{ +#ifdef USE_SIMPLE_QBEZIER_CODE + if ( size() != 4 ) { +#if defined(QT_CHECK_RANGE) + qWarning( "TQPointArray::bezier: The array must have 4 control points" ); +#endif + TQPointArray p; + return p; + } + + int v; + float xvec[4]; + float yvec[4]; + for ( v=0; v<4; v++ ) { // store all x,y in xvec,yvec + int x, y; + point( v, &x, &y ); + xvec[v] = (float)x; + yvec[v] = (float)y; + } + + TQRect r = boundingRect(); + int m = TQMAX(r.width(),r.height())/2; + m = TQMIN(m,30); // m = number of result points + if ( m < 2 ) // at least two points + m = 2; + TQPointArray p( m ); // p = Bezier point array + register TQPointData *pd = p.data(); + + float x0 = xvec[0], y0 = yvec[0]; + float dt = 1.0F/m; + float cx = 3.0F * (xvec[1] - x0); + float bx = 3.0F * (xvec[2] - xvec[1]) - cx; + float ax = xvec[3] - (x0 + cx + bx); + float cy = 3.0F * (yvec[1] - y0); + float by = 3.0F * (yvec[2] - yvec[1]) - cy; + float ay = yvec[3] - (y0 + cy + by); + float t = dt; + + pd->rx() = (TQCOORD)xvec[0]; + pd->ry() = (TQCOORD)yvec[0]; + pd++; + m -= 2; + + while ( m-- ) { + pd->rx() = (TQCOORD)qRound( ((ax * t + bx) * t + cx) * t + x0 ); + pd->ry() = (TQCOORD)qRound( ((ay * t + by) * t + cy) * t + y0 ); + pd++; + t += dt; + } + + pd->rx() = (TQCOORD)xvec[3]; + pd->ry() = (TQCOORD)yvec[3]; + + return p; +#else + + if ( size() != 4 ) { +#if defined(QT_CHECK_RANGE) + qWarning( "TQPointArray::bezier: The array must have 4 control points" ); +#endif + TQPointArray pa; + return pa; + } else { + TQRect r = boundingRect(); + int m = 4+2*TQMAX(r.width(),r.height()); + double *p = new double[m]; + double ctrl[8]; + int i; + for (i=0; i<4; i++) { + ctrl[i*2] = at(i).x(); + ctrl[i*2+1] = at(i).y(); + } + int len=0; + polygonizeTQBezier( p, len, ctrl, m ); + TQPointArray pa((len/2)+1); // one extra point for last point on line + int j=0; + for (i=0; j<len; i++) { + int x = qRound(p[j++]); + int y = qRound(p[j++]); + pa[i] = TQPoint(x,y); + } + // add last pt on the line, which will be at the last control pt + pa[(int)pa.size()-1] = at(3); + delete[] p; + + return pa; + } + +#endif +} +#endif //QT_NO_BEZIER + +/***************************************************************************** + TQPointArray stream functions + *****************************************************************************/ +#ifndef QT_NO_DATASTREAM +/*! + \relates TQPointArray + + Writes the point array, \a a to the stream \a s and returns a + reference to the stream. + + \sa \link datastreamformat.html Format of the TQDataStream operators \endlink +*/ + +TQDataStream &operator<<( TQDataStream &s, const TQPointArray &a ) +{ + register uint i; + uint len = a.size(); + s << len; // write size of array + for ( i=0; i<len; i++ ) // write each point + s << a.point( i ); + return s; +} + +/*! + \relates TQPointArray + + Reads a point array, \a a from the stream \a s and returns a + reference to the stream. + + \sa \link datastreamformat.html Format of the TQDataStream operators \endlink +*/ + +TQDataStream &operator>>( TQDataStream &s, TQPointArray &a ) +{ + register uint i; + uint len; + s >> len; // read size of array + if ( !a.resize( len ) ) // no memory + return s; + TQPoint p; + for ( i=0; i<len; i++ ) { // read each point + s >> p; + a.setPoint( i, p ); + } + return s; +} +#endif //QT_NO_DATASTREAM + + + +struct TQShortPoint { // Binary compatible with XPoint + short x, y; +}; + +uint TQPointArray::splen = 0; +void* TQPointArray::sp = 0; // Really a TQShortPoint* + +/*! + \internal + + Converts the point coords to short (16bit) size, compatible with + X11's XPoint structure. The pointer returned points to a static + array, so its contents will be overwritten the next time this + function is called. +*/ + +void* TQPointArray::shortPoints( int index, int nPoints ) const +{ + + if ( isNull() || !nPoints ) + return 0; + TQPoint* p = data(); + p += index; + uint i = nPoints < 0 ? size() : nPoints; + if ( splen < i ) { + if ( sp ) + delete[] ((TQShortPoint*)sp); + sp = new TQShortPoint[i]; + splen = i; + } + TQShortPoint* ps = (TQShortPoint*)sp; + while ( i-- ) { + ps->x = (short)p->x(); + ps->y = (short)p->y(); + p++; + ps++; + } + return sp; +} + + +/*! + \internal + + Deallocates the internal buffer used by shortPoints(). +*/ + +void TQPointArray::cleanBuffers() +{ + if ( sp ) + delete[] ((TQShortPoint*)sp); + sp = 0; + splen = 0; +} |