kpresenter

KoPointArray.cpp

00001 // -*- Mode: c++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4; -*-
00002 /* This file is part of the KDE project
00003    Copyright (C) 2001 Laurent MONTEL <lmontel@mandrakesoft.com>
00004 
00005    This library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Library General Public
00007    License as published by the Free Software Foundation; either
00008    version 2 of the License, or (at your option) any later version.
00009 
00010    This library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Library General Public License for more details.
00014 
00015    You should have received a copy of the GNU Library General Public License
00016    along with this library; see the file COPYING.LIB.  If not, write to
00017    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00018  * Boston, MA 02110-1301, USA.
00019 */
00020 
00021 #include "KoPointArray.h"
00022 #include <KoRect.h>
00023 #include <stdarg.h>
00024 #include <KoZoomHandler.h>
00025 
00026 void KoPointArray::translate( double dx, double dy )
00027 {
00028     register KoPoint *p = data();
00029     register int i = size();
00030     KoPoint pt( dx, dy );
00031     while ( i-- ) {
00032         *p += pt;
00033         p++;
00034     }
00035 }
00036 
00037 void KoPointArray::point( uint index, double *x, double *y ) const
00038 {
00039     KoPoint p = QMemArray<KoPoint>::at( index );
00040     if ( x )
00041         *x = (double)p.x();
00042     if ( y )
00043         *y = (double)p.y();
00044 }
00045 
00046 KoPoint KoPointArray::point( uint index ) const
00047 { // #### index out of bounds
00048     return QMemArray<KoPoint>::at( index );
00049 }
00050 
00051 void KoPointArray::setPoint( uint index, double x, double y )
00052 { // #### index out of bounds
00053     QMemArray<KoPoint>::at( index ) = KoPoint( x, y );
00054 }
00055 
00056 
00057 
00058 bool KoPointArray::putPoints( int index, int nPoints, double firstx, double firsty,
00059                               ... )
00060 {
00061     va_list ap;
00062     if ( index + nPoints > (int)size() ) {  // extend array
00063         if ( !resize(index + nPoints) )
00064             return FALSE;
00065     }
00066     if ( nPoints <= 0 )
00067         return TRUE;
00068     setPoint( index, firstx, firsty );      // set first point
00069     int i = index + 1;
00070     double x, y;
00071     nPoints--;
00072     va_start( ap, firsty );
00073     while ( nPoints-- ) {
00074         x = va_arg( ap, double );
00075         y = va_arg( ap, double );
00076         setPoint( i++, x, y );
00077     }
00078     va_end( ap );
00079     return TRUE;
00080 }
00081 
00082 void split(const double *p, double *l, double *r)
00083 {
00084     double tmpx;
00085     double tmpy;
00086 
00087     l[0] =  p[0];
00088     l[1] =  p[1];
00089     r[6] =  p[6];
00090     r[7] =  p[7];
00091 
00092     l[2] = (p[0]+ p[2])/2;
00093     l[3] = (p[1]+ p[3])/2;
00094     tmpx = (p[2]+ p[4])/2;
00095     tmpy = (p[3]+ p[5])/2;
00096     r[4] = (p[4]+ p[6])/2;
00097     r[5] = (p[5]+ p[7])/2;
00098 
00099     l[4] = (l[2]+ tmpx)/2;
00100     l[5] = (l[3]+ tmpy)/2;
00101     r[2] = (tmpx + r[4])/2;
00102     r[3] = (tmpy + r[5])/2;
00103 
00104     l[6] = (l[4]+ r[2])/2;
00105     l[7] = (l[5]+ r[3])/2;
00106     r[0] = l[6];
00107     r[1] = l[7];
00108 }
00109 
00110 // Based on:
00111 //
00112 //   A Fast 2D Point-On-Line Test
00113 //   by Alan Paeth
00114 //   from "Graphics Gems", Academic Press, 1990
00115 static
00116 int pnt_on_line( const int* p, const int* q, const int* t )
00117 {
00118 /*
00119  * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty)
00120  * return 0 if T is not on the line through      <--P--Q-->
00121  *        1 if T is on the open ray ending at P: <--P
00122  *        2 if T is on the closed interior along:   P--Q
00123  *        3 if T is on the open ray beginning at Q:    Q-->
00124  *
00125  * Example: consider the line P = (3,2), Q = (17,7). A plot
00126  * of the test points T(x,y) (with 0 mapped onto '.') yields:
00127  *
00128  *     8| . . . . . . . . . . . . . . . . . 3 3
00129  *  Y  7| . . . . . . . . . . . . . . 2 2 Q 3 3    Q = 2
00130  *     6| . . . . . . . . . . . 2 2 2 2 2 . . .
00131  *  a  5| . . . . . . . . 2 2 2 2 2 2 . . . . .
00132  *  x  4| . . . . . 2 2 2 2 2 2 . . . . . . . .
00133  *  i  3| . . . 2 2 2 2 2 . . . . . . . . . . .
00134  *  s  2| 1 1 P 2 2 . . . . . . . . . . . . . .    P = 2
00135  *     1| 1 1 . . . . . . . . . . . . . . . . .
00136  *      +--------------------------------------
00137  *        1 2 3 4 5 X-axis 10        15      19
00138  *
00139  * Point-Line distance is normalized with the Infinity Norm
00140  * avoiding square-root code and tightening the test vs the
00141  * Manhattan Norm. All math is done on the field of integers.
00142  * The latter replaces the initial ">= MAX(...)" test with
00143  * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality
00144  * and norm, yielding a broader target line for selection.
00145  * The tightest test is employed here for best discrimination
00146  * in merging collinear (to grid coordinates) vertex chains
00147  * into a larger, spanning vectors within the Lemming editor.
00148  */
00149 
00150     // if all points are coincident, return condition 2 (on line)
00151     if(q[0]==p[0] && q[1]==p[1] && q[0]==t[0] && q[1]==t[1]) {
00152         return 2;
00153     }
00154 
00155     if ( QABS((q[1]-p[1])*(t[0]-p[0])-(t[1]-p[1])*(q[0]-p[0])) >=
00156          (QMAX(QABS(q[0]-p[0]), QABS(q[1]-p[1])))) return 0;
00157 
00158     if (((q[0]<p[0])&&(p[0]<t[0])) || ((q[1]<p[1])&&(p[1]<t[1])))
00159         return 1 ;
00160     if (((t[0]<p[0])&&(p[0]<q[0])) || ((t[1]<p[1])&&(p[1]<q[1])))
00161         return 1 ;
00162     if (((p[0]<q[0])&&(q[0]<t[0])) || ((p[1]<q[1])&&(q[1]<t[1])))
00163         return 3 ;
00164     if (((t[0]<q[0])&&(q[0]<p[0])) || ((t[1]<q[1])&&(q[1]<p[1])))
00165         return 3 ;
00166 
00167     return 2 ;
00168 }
00169 
00170 static
00171 void polygonizeQBezier( double* acc, int& accsize, const double ctrl[],
00172                         int maxsize )
00173 {
00174     if ( accsize > maxsize / 2 )
00175     {
00176         // This never happens in practice.
00177 
00178         if ( accsize >= maxsize-4 )
00179             return;
00180         // Running out of space - approximate by a line.
00181         acc[accsize++] = ctrl[0];
00182         acc[accsize++] = ctrl[1];
00183         acc[accsize++] = ctrl[6];
00184         acc[accsize++] = ctrl[7];
00185         return;
00186     }
00187 
00188     //intersects:
00189     double l[8];
00190     double r[8];
00191     split( ctrl, l, r);
00192 
00193     // convert to integers for line condition check
00194     int c0[2]; c0[0] = int(ctrl[0]); c0[1] = int(ctrl[1]);
00195     int c1[2]; c1[0] = int(ctrl[2]); c1[1] = int(ctrl[3]);
00196     int c2[2]; c2[0] = int(ctrl[4]); c2[1] = int(ctrl[5]);
00197     int c3[2]; c3[0] = int(ctrl[6]); c3[1] = int(ctrl[7]);
00198 
00199     // #### Duplication needed?
00200     if ( QABS(c1[0]-c0[0]) <= 1 && QABS(c1[1]-c0[1]) <= 1
00201          && QABS(c2[0]-c0[0]) <= 1 && QABS(c2[1]-c0[1]) <= 1
00202          && QABS(c3[0]-c1[0]) <= 1 && QABS(c3[1]-c0[1]) <= 1 )
00203     {
00204         // Approximate by one line.
00205         // Dont need to write last pt as it is the same as first pt
00206         // on the next segment
00207         acc[accsize++] = l[0];
00208         acc[accsize++] = l[1];
00209         return;
00210     }
00211 
00212     if ( ( pnt_on_line( c0, c3, c1 ) == 2 && pnt_on_line( c0, c3, c2 ) == 2 )
00213          || ( QABS(c1[0]-c0[0]) <= 1 && QABS(c1[1]-c0[1]) <= 1
00214               && QABS(c2[0]-c0[0]) <= 1 && QABS(c2[1]-c0[1]) <= 1
00215               && QABS(c3[0]-c1[0]) <= 1 && QABS(c3[1]-c0[1]) <= 1 ) )
00216     {
00217         // Approximate by one line.
00218         // Dont need to write last pt as it is the same as first pt
00219         // on the next segment
00220         acc[accsize++] = l[0];
00221         acc[accsize++] = l[1];
00222         return;
00223     }
00224 
00225     // Too big and too curved - recusively subdivide.
00226     polygonizeQBezier( acc, accsize, l, maxsize );
00227     polygonizeQBezier( acc, accsize, r, maxsize );
00228 }
00229 
00230 
00231 KoRect KoPointArray::boundingRect() const
00232 {
00233     if ( isEmpty() )
00234         return KoRect( 0, 0, 0, 0 );        // null rectangle
00235     register KoPoint *pd = data();
00236     double minx, maxx, miny, maxy;
00237     minx = maxx = pd->x();
00238     miny = maxy = pd->y();
00239     pd++;
00240     for ( int i=1; i<(int)size(); i++ ) {   // find min+max x and y
00241         if ( pd->x() < minx )
00242             minx = pd->x();
00243         else if ( pd->x() > maxx )
00244             maxx = pd->x();
00245         if ( pd->y() < miny )
00246             miny = pd->y();
00247         else if ( pd->y() > maxy )
00248             maxy = pd->y();
00249         pd++;
00250     }
00251     return KoRect( KoPoint(minx,miny), KoPoint(maxx,maxy) );
00252 }
00253 
00254 
00255 KoPointArray KoPointArray::cubicBezier() const
00256 {
00257     if ( size() != 4 ) {
00258 #if defined(QT_CHECK_RANGE)
00259         qWarning( "QPointArray::bezier: The array must have 4 control points" );
00260 #endif
00261         KoPointArray pa;
00262         return pa;
00263     } else {
00264         KoRect r = boundingRect();
00265         int m = (int)(4+2*QMAX(r.width(),r.height()));
00266         double *p = new double[m];
00267         double ctrl[8];
00268         int i;
00269         for (i=0; i<4; i++) {
00270             ctrl[i*2] = at(i).x();
00271             ctrl[i*2+1] = at(i).y();
00272         }
00273         int len=0;
00274         polygonizeQBezier( p, len, ctrl, m );
00275         KoPointArray pa((len/2)+1); // one extra point for last point on line
00276         int j=0;
00277         for (i=0; j<len; i++) {
00278             double x = qRound(p[j++]);
00279             double y = qRound(p[j++]);
00280             pa[i] = KoPoint(x,y);
00281         }
00282         // add last pt on the line, which will be at the last control pt
00283         pa[(int)pa.size()-1] = at(3);
00284         delete[] p;
00285 
00286         return pa;
00287     }
00288 }
00289 
00290 QPointArray KoPointArray::zoomPointArray( const KoZoomHandler* zoomHandler ) const
00291 {
00292     QPointArray tmpPoints(size());
00293     for ( uint i= 0; i<size();i++ ) {
00294         KoPoint p = at( i );
00295         tmpPoints.putPoints( i, 1, zoomHandler->zoomItX(p.x()),zoomHandler->zoomItY(p.y()) );
00296     }
00297     return tmpPoints;
00298 }
00299 
00300 QPointArray KoPointArray::zoomPointArray( const KoZoomHandler* zoomHandler, int penWidth ) const
00301 {
00302     double fx;
00303     double fy;
00304     KoSize ext = boundingRect().size();
00305     int pw = zoomHandler->zoomItX( penWidth ) / 2;
00306 
00307     fx = (double)( zoomHandler->zoomItX(ext.width()) - 2 * pw ) / ext.width();
00308     fy = (double)( zoomHandler->zoomItY(ext.height()) - 2 * pw ) / ext.height();
00309 
00310     unsigned int index = 0;
00311     QPointArray tmpPoints;
00312     KoPointArray::ConstIterator it;
00313     for ( it = begin(); it != end(); ++it, ++index ) {
00314         int tmpX = qRound((*it).x() * fx + pw);
00315         int tmpY = qRound((*it).y() * fy + pw);
00316 
00317         tmpPoints.putPoints( index, 1, tmpX, tmpY );
00318     }
00319     return tmpPoints;
00320 }
KDE Home | KDE Accessibility Home | Description of Access Keys