karbon

vsegment.cc

00001 /* This file is part of the KDE project
00002    Copyright (C) 2001, 2002, 2003 The Karbon Developers
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License as published by the Free Software Foundation; either
00007    version 2 of the License, or (at your option) any later version.
00008 
00009    This library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Library General Public License for more details.
00013 
00014    You should have received a copy of the GNU Library General Public License
00015    along with this library; see the file COPYING.LIB.  If not, write to
00016    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00017  * Boston, MA 02110-1301, USA.
00018 */
00019 
00020 #include <math.h>
00021 
00022 #include <qdom.h>
00023 
00024 #include "vpainter.h"
00025 #include "vpath.h"
00026 #include "vsegment.h"
00027 
00028 #include <kdebug.h>
00029 
00030 VSegment::VSegment( unsigned short deg )
00031 {
00032     m_degree = deg;
00033 
00034     m_nodes = new VNodeData[ degree() ];
00035 
00036     for( unsigned short i = 0; i < degree(); ++i )
00037         selectPoint( i );
00038 
00039     m_state = normal;
00040 
00041     m_prev = 0L;
00042     m_next = 0L;
00043 }
00044 
00045 VSegment::VSegment( const VSegment& segment )
00046 {
00047     m_degree = segment.degree();
00048 
00049     m_nodes = new VNodeData[ degree() ];
00050 
00051     m_state = segment.m_state;
00052 
00053     // Copying the pointers m_prev/m_next has some advantages (see VSegment::length()).
00054     // Inserting a segment into a path overwrites these anyway.
00055     m_prev = segment.m_prev;
00056     m_next = segment.m_next;
00057 
00058     // Copy points.
00059     for( unsigned short i = 0; i < degree(); i++ )
00060     {
00061         setPoint( i, segment.point( i ) );
00062         selectPoint( i, segment.pointIsSelected( i ) );
00063     }
00064 }
00065 
00066 VSegment::~VSegment()
00067 {
00068     delete[]( m_nodes );
00069 }
00070 
00071 void
00072 VSegment::setDegree( unsigned short deg )
00073 {
00074     // Do nothing if old and new degrees are identical.
00075     if( degree() == deg )
00076         return;
00077 
00078     // TODO : this code is fishy, please make it sane
00079 
00080     // Remember old nodes.
00081     VNodeData* oldNodes = m_nodes;
00082     KoPoint oldKnot = knot();
00083 
00084     // Allocate new node data.
00085     m_nodes = new VNodeData[ deg ];
00086 
00087     if( deg == 1 )
00088         m_nodes[ 0 ].m_vector = oldKnot;
00089     else
00090     {
00091         // Copy old node data (from the knot "backwards".
00092         unsigned short offset = kMax( 0, deg - m_degree );
00093 
00094         for( unsigned short i = offset; i < deg; ++i )
00095         {
00096             m_nodes[ i ].m_vector = oldNodes[ i - offset ].m_vector;
00097         }
00098 
00099         // Fill with "zeros" if necessary.
00100         for( unsigned short i = 0; i < offset; ++i )
00101         {
00102             m_nodes[ i ].m_vector = KoPoint( 0.0, 0.0 );
00103         }
00104     }
00105 
00106     // Set new degree.
00107     m_degree = deg;
00108 
00109     // Delete old nodes.
00110     delete[]( oldNodes );
00111 }
00112 
00113 void
00114 VSegment::draw( VPainter* painter ) const
00115 {
00116     // Don't draw a deleted segment.
00117     if( state() == deleted )
00118         return;
00119 
00120 
00121     if( prev() )
00122     {
00123         if( degree() == 3 )
00124         {
00125             painter->curveTo( point( 0 ), point( 1 ), point( 2 ) );
00126         }
00127         else
00128         {
00129             painter->lineTo( knot() );
00130         }
00131     }
00132     else
00133     {
00134         painter->moveTo( knot() );
00135     }
00136 }
00137 
00138 bool
00139 VSegment::isFlat( double flatness ) const
00140 {
00141     // Lines and "begin" segments are flat.
00142     if(
00143         !prev() ||
00144         degree() == 1 )
00145     {
00146         return true;
00147     }
00148 
00149 
00150     // Iterate over control points.
00151     for( unsigned short i = 0; i < degree() - 1; ++i )
00152     {
00153         if(
00154             height( prev()->knot(), point( i ), knot() ) / chordLength()
00155             >= flatness )
00156         {
00157             return false;
00158         }
00159     }
00160 
00161     return true;
00162 }
00163 
00164 KoPoint
00165 VSegment::pointAt( double t ) const
00166 {
00167     KoPoint p;
00168 
00169     pointDerivativesAt( t, &p );
00170 
00171     return p;
00172 }
00173 
00174 void
00175 VSegment::pointDerivativesAt( double t, KoPoint* p,
00176                               KoPoint* d1, KoPoint* d2 ) const
00177 {
00178     if( !prev() )
00179         return;
00180 
00181 
00182     // Optimise the line case.
00183     if( degree() == 1 )
00184     {
00185         const KoPoint diff = knot() - prev()->knot();
00186 
00187         if( p )
00188             *p = prev()->knot() + diff * t;
00189 
00190         if( d1 )
00191             *d1 = diff;
00192 
00193         if( d2 )
00194             *d2 = KoPoint( 0.0, 0.0 );
00195 
00196         return;
00197     }
00198 
00199 
00200     // Beziers.
00201 
00202     // Copy points.
00203     KoPoint* q = new KoPoint[ degree() + 1 ];
00204 
00205     q[ 0 ] = prev()->knot();
00206 
00207     for( unsigned short i = 0; i < degree(); ++i )
00208     {
00209         q[ i + 1 ] = point( i );
00210     }
00211 
00212 
00213     // The De Casteljau algorithm.
00214     for( unsigned short j = 1; j <= degree(); j++ )
00215     {
00216         for( unsigned short i = 0; i <= degree() - j; i++ )
00217         {
00218             q[ i ] = ( 1.0 - t ) * q[ i ] + t * q[ i + 1 ];
00219         }
00220 
00221         // Save second derivative now that we have it.
00222         if( j == degree() - 2 )
00223         {
00224             if( d2 )
00225                 *d2 = degree() * ( degree() - 1 )
00226                       * ( q[ 2 ] - 2 * q[ 1 ] + q[ 0 ] );
00227         }
00228 
00229         // Save first derivative now that we have it.
00230         else if( j == degree() - 1 )
00231         {
00232             if( d1 )
00233                 *d1 = degree() * ( q[ 1 ] - q[ 0 ] );
00234         }
00235     }
00236 
00237     // Save point.
00238     if( p )
00239         *p = q[ 0 ];
00240 
00241     delete[]( q );
00242 
00243 
00244     return;
00245 }
00246 
00247 KoPoint
00248 VSegment::tangentAt( double t ) const
00249 {
00250     KoPoint tangent;
00251 
00252     pointTangentNormalAt( t, 0L, &tangent );
00253 
00254     return tangent;
00255 }
00256 
00257 void
00258 VSegment::pointTangentNormalAt( double t, KoPoint* p,
00259                                 KoPoint* tn, KoPoint* n ) const
00260 {
00261     // Calculate derivative if necessary.
00262     KoPoint d;
00263 
00264     pointDerivativesAt( t, p, tn || n ? &d : 0L );
00265 
00266 
00267     // Normalize derivative.
00268     if( tn || n )
00269     {
00270         const double norm =
00271             sqrt( d.x() * d.x() + d.y() * d.y() );
00272 
00273         d = norm ? d * ( 1.0 / norm ) : KoPoint( 0.0, 0.0 );
00274     }
00275 
00276     // Assign tangent vector.
00277     if( tn )
00278         *tn = d;
00279 
00280     // Calculate normal vector.
00281     if( n )
00282     {
00283         // Calculate vector product of "binormal" x tangent
00284         // (0,0,1) x (dx,dy,0), which is simply (dy,-dx,0).
00285         n->setX( d.y() );
00286         n->setY( -d.x() );
00287     }
00288 }
00289 
00290 double
00291 VSegment::length( double t ) const
00292 {
00293     if( !prev() || t == 0.0 )
00294     {
00295         return 0.0;
00296     }
00297 
00298 
00299     // Optimise the line case.
00300     if( degree() == 1 )
00301     {
00302         return
00303             t * chordLength();
00304     }
00305 
00306 
00307     /* This algortihm is by Jens Gravesen <gravesen AT mat DOT dth DOT dk>.
00308      * We calculate the chord length "chord"=|P0P3| and the length of the control point
00309      * polygon "poly"=|P0P1|+|P1P2|+|P2P3|. The approximation for the bezier length is
00310      * 0.5 * poly + 0.5 * chord. "poly - chord" is a measure for the error.
00311      * We subdivide each segment until the error is smaller than a given tolerance
00312      * and add up the subresults.
00313      */
00314 
00315     // "Copy segment" splitted at t into a path.
00316     VSubpath path( 0L );
00317     path.moveTo( prev()->knot() );
00318 
00319     // Optimize a bit: most of the time we'll need the
00320     // length of the whole segment.
00321     if( t == 1.0 )
00322         path.append( this->clone() );
00323     else
00324     {
00325         VSegment* copy = this->clone();
00326         path.append( copy->splitAt( t ) );
00327         delete copy;
00328     }
00329 
00330 
00331     double chord;
00332     double poly;
00333 
00334     double length = 0.0;
00335 
00336     while( path.current() )
00337     {
00338         chord = path.current()->chordLength();
00339         poly = path.current()->polyLength();
00340 
00341         if(
00342             poly &&
00343             ( poly - chord ) / poly > VGlobal::lengthTolerance )
00344         {
00345             // Split at midpoint.
00346             path.insert(
00347                 path.current()->splitAt( 0.5 ) );
00348         }
00349         else
00350         {
00351             length += 0.5 * poly + 0.5 * chord;
00352             path.next();
00353         }
00354     }
00355 
00356 
00357     return length;
00358 }
00359 
00360 double
00361 VSegment::chordLength() const
00362 {
00363     if( !prev() )
00364         return 0.0;
00365 
00366 
00367     KoPoint d = knot() - prev()->knot();
00368 
00369     return sqrt( d * d );
00370 }
00371 
00372 double
00373 VSegment::polyLength() const
00374 {
00375     if( !prev() )
00376         return 0.0;
00377 
00378 
00379     // Start with distance |first point - previous knot|.
00380     KoPoint d = point( 0 ) - prev()->knot();
00381 
00382     double length = sqrt( d * d );
00383 
00384     // Iterate over remaining points.
00385     for( unsigned short i = 1; i < degree(); ++i )
00386     {
00387         d = point( i ) - point( i - 1 );
00388         length += sqrt( d * d );
00389     }
00390 
00391 
00392     return length;
00393 }
00394 
00395 double
00396 VSegment::lengthParam( double len ) const
00397 {
00398     if(
00399         !prev() ||
00400         len == 0.0 )        // We divide by len below.
00401     {
00402         return 0.0;
00403     }
00404 
00405 
00406     // Optimise the line case.
00407     if( degree() == 1 )
00408     {
00409         return
00410             len / chordLength();
00411     }
00412 
00413 
00414     // Perform a successive interval bisection.
00415     double param1 = 0.0;
00416     double paramMid = 0.5;
00417     double param2 = 1.0;
00418 
00419     double lengthMid = length( paramMid );
00420 
00421     while( QABS( lengthMid - len ) / len > VGlobal::paramLengthTolerance )
00422     {
00423         if( lengthMid < len )
00424             param1 = paramMid;
00425         else
00426             param2 = paramMid;
00427 
00428         paramMid = 0.5 * ( param2 + param1 );
00429 
00430         lengthMid = length( paramMid );
00431     }
00432 
00433     return paramMid;
00434 }
00435 
00436 double
00437 VSegment::nearestPointParam( const KoPoint& p ) const
00438 {
00439     if( !prev() )
00440     {
00441         return 1.0;
00442     }
00443 
00444 
00445     /* This function solves the "nearest point on curve" problem. That means, it
00446      * calculates the point q (to be precise: it's parameter t) on this segment, which
00447      * is located nearest to the input point P.
00448      * The basic idea is best described (because it is freely available) in "Phoenix:
00449      * An Interactive Curve Design System Based on the Automatic Fitting of
00450      * Hand-Sketched Curves", Philip J. Schneider (Master thesis, University of
00451      * Washington).
00452      *
00453      * For the nearest point q = C(t) on this segment, the first derivative is
00454      * orthogonal to the distance vector "C(t) - P". In other words we are looking for
00455      * solutions of f(t) = ( C(t) - P ) * C'(t) = 0.
00456      * ( C(t) - P ) is a nth degree curve, C'(t) a n-1th degree curve => f(t) is a
00457      * (2n - 1)th degree curve and thus has up to 2n - 1 distinct solutions.
00458      * We solve the problem f(t) = 0 by using something called "Approximate Inversion Method".
00459      * Let's write f(t) explicitly (with c_i = p_i - P and d_j = p_{j+1} - p_j):
00460      *
00461      *         n                     n-1
00462      * f(t) = SUM c_i * B^n_i(t)  *  SUM d_j * B^{n-1}_j(t)
00463      *        i=0                    j=0
00464      *
00465      *         n  n-1
00466      *      = SUM SUM w_{ij} * B^{2n-1}_{i+j}(t)
00467      *        i=0 j=0
00468      *
00469      * with w_{ij} = c_i * d_j * z_{ij} and
00470      *
00471      *          BinomialCoeff( n, i ) * BinomialCoeff( n - i ,j )
00472      * z_{ij} = -----------------------------------------------
00473      *                   BinomialCoeff( 2n - 1, i + j )
00474      *
00475      * This Bernstein-Bezier polynom representation can now be solved for it's roots.
00476      */
00477 
00478 
00479     // Calculate the c_i = point( i ) - P.
00480     KoPoint* c = new KoPoint[ degree() + 1 ];
00481 
00482     c[ 0 ] = prev()->knot() - p;
00483 
00484     for( unsigned short i = 1; i <= degree(); ++i )
00485     {
00486         c[ i ] = point( i - 1 ) - p;
00487     }
00488 
00489 
00490     // Calculate the d_j = point( j + 1 ) - point( j ).
00491     KoPoint* d = new KoPoint[ degree() ];
00492 
00493     d[ 0 ] = point( 0 ) - prev()->knot();
00494 
00495     for( unsigned short j = 1; j <= degree() - 1; ++j )
00496     {
00497         d[ j ] = 3.0 * ( point( j ) - point( j - 1 ) );
00498     }
00499 
00500 
00501     // Calculate the z_{ij}.
00502     double* z = new double[ degree() * ( degree() + 1 ) ];
00503 
00504     for( unsigned short j = 0; j <= degree() - 1; ++j )
00505     {
00506         for( unsigned short i = 0; i <= degree(); ++i )
00507         {
00508             z[ j * ( degree() + 1 ) + i ] =
00509                 static_cast<double>(
00510                     VGlobal::binomialCoeff( degree(), i ) *
00511                     VGlobal::binomialCoeff( degree() - i, j ) )
00512                 /
00513                 static_cast<double>(
00514                     VGlobal::binomialCoeff( 2 * degree() - 1, i + j ) );
00515         }
00516     }
00517 
00518 
00519     // Calculate the dot products of c_i and d_i.
00520     double* products = new double[ degree() * ( degree() + 1 ) ];
00521 
00522     for( unsigned short j = 0; j <= degree() - 1; ++j )
00523     {
00524         for( unsigned short i = 0; i <= degree(); ++i )
00525         {
00526             products[ j * ( degree() + 1 ) + i ] =
00527                 d[ j ] * c[ i ];
00528         }
00529     }
00530 
00531     // We don't need the c_i and d_i anymore.
00532     delete[]( d );
00533     delete[]( c );
00534 
00535 
00536     // Calculate the control points of the new 2n-1th degree curve.
00537     VSubpath newCurve( 0L );
00538     newCurve.append( new VSegment( 2 * degree() - 1 ) );
00539 
00540     // Set up control points in the ( u, f(u) )-plane.
00541     for( unsigned short u = 0; u <= 2 * degree() - 1; ++u )
00542     {
00543         newCurve.current()->setP(
00544             u,
00545             KoPoint(
00546                 static_cast<double>( u ) / static_cast<double>( 2 * degree() - 1 ),
00547                 0.0 ) );
00548     }
00549 
00550 
00551     // Set f(u)-values.
00552     for( unsigned short k = 0; k <= 2 * degree() - 1; ++k )
00553     {
00554         unsigned short min = kMin( k, degree() );
00555 
00556         for(
00557             unsigned short i = kMax( 0, k - ( degree() - 1 ) );
00558             i <= min;
00559             ++i )
00560         {
00561             unsigned short j = k - i;
00562 
00563             // p_k += products[j][i] * z[j][i].
00564             newCurve.getLast()->setP(
00565                 k,
00566                 KoPoint(
00567                     newCurve.getLast()->p( k ).x(),
00568                     newCurve.getLast()->p( k ).y() +
00569                         products[ j * ( degree() + 1 ) + i ] *
00570                             z[ j * ( degree() + 1 ) + i ] ) );
00571         }
00572     }
00573 
00574     // We don't need the c_i/d_i dot products and the z_{ij} anymore.
00575     delete[]( products );
00576     delete[]( z );
00577 
00578 kdDebug(38000) << "results" << endl;
00579 for( int i = 0; i <= 2 * degree() - 1; ++i )
00580 {
00581 kdDebug(38000) << newCurve.getLast()->p( i ).x() << " "
00582 << newCurve.getLast()->p( i ).y() << endl;
00583 }
00584 kdDebug(38000) << endl;
00585 
00586     // Find roots.
00587     QValueList<double> params;
00588 
00589     newCurve.getLast()->rootParams( params );
00590 
00591 
00592     // Now compare the distances of the candidate points.
00593     double resultParam;
00594     double distanceSquared;
00595     double oldDistanceSquared;
00596     KoPoint dist;
00597 
00598     // First candidate is the previous knot.
00599     dist = prev()->knot() - p;
00600     distanceSquared = dist * dist;
00601     resultParam = 0.0;
00602 
00603     // Iterate over the found candidate params.
00604     for( QValueListConstIterator<double> itr = params.begin(); itr != params.end(); ++itr )
00605     {
00606         pointDerivativesAt( *itr, &dist );
00607         dist -= p;
00608         oldDistanceSquared = distanceSquared;
00609         distanceSquared = dist * dist;
00610 
00611         if( distanceSquared < oldDistanceSquared )
00612             resultParam = *itr;
00613     }
00614 
00615     // Last candidate is the knot.
00616     dist = knot() - p;
00617     oldDistanceSquared = distanceSquared;
00618     distanceSquared = dist * dist;
00619 
00620     if( distanceSquared < oldDistanceSquared )
00621         resultParam = 1.0;
00622 
00623 
00624     return resultParam;
00625 }
00626 
00627 void
00628 VSegment::rootParams( QValueList<double>& params ) const
00629 {
00630     if( !prev() )
00631     {
00632         return;
00633     }
00634 
00635 
00636     // Calculate how often the control polygon crosses the x-axis
00637     // This is the upper limit for the number of roots.
00638     switch( controlPolygonZeros() )
00639     {
00640         // No solutions.
00641         case 0:
00642             return;
00643         // Exactly one solution.
00644         case 1:
00645             if( isFlat( VGlobal::flatnessTolerance / chordLength() ) )
00646             {
00647                 // Calculate intersection of chord with x-axis.
00648                 KoPoint chord = knot() - prev()->knot();
00649 
00650 kdDebug(38000) << prev()->knot().x()  << " " << prev()->knot().y()
00651 << knot().x() << " " << knot().y() << " ---> "
00652 << ( chord.x() * prev()->knot().y() - chord.y() * prev()->knot().x() ) / - chord.y() << endl;
00653                 params.append(
00654                     ( chord.x() * prev()->knot().y() - chord.y() * prev()->knot().x() )
00655                     / - chord.y() );
00656 
00657                 return;
00658             }
00659             break;
00660     }
00661 
00662     // Many solutions. Do recursive midpoint subdivision.
00663     VSubpath path( *this );
00664     path.insert( path.current()->splitAt( 0.5 ) );
00665 
00666     path.current()->rootParams( params );
00667     path.next()->rootParams( params );
00668 }
00669 
00670 int
00671 VSegment::controlPolygonZeros() const
00672 {
00673     if( !prev() )
00674     {
00675         return 0;
00676     }
00677 
00678 
00679     int signChanges = 0;
00680 
00681     int sign = VGlobal::sign( prev()->knot().y() );
00682     int oldSign;
00683 
00684     for( unsigned short i = 0; i < degree(); ++i )
00685     {
00686         oldSign = sign;
00687         sign = VGlobal::sign( point( i ).y() );
00688 
00689         if( sign != oldSign )
00690         {
00691             ++signChanges;
00692         }
00693     }
00694 
00695 
00696     return signChanges;
00697 }
00698 
00699 bool
00700 VSegment::isSmooth( const VSegment& next ) const
00701 {
00702     // Return false if this segment is a "begin".
00703     if( !prev() )
00704         return false;
00705 
00706 
00707     // Calculate tangents.
00708     KoPoint t1;
00709     KoPoint t2;
00710 
00711     pointTangentNormalAt( 1.0, 0L, &t1 );
00712 
00713     next.pointTangentNormalAt( 0.0, 0L, &t2 );
00714 
00715 
00716     // Dot product.
00717     if( t1 * t2 >= VGlobal::parallelTolerance )
00718         return true;
00719 
00720     return false;
00721 }
00722 
00723 KoRect
00724 VSegment::boundingBox() const
00725 {
00726     // Initialize with knot.
00727     KoRect rect( knot(), knot() );
00728 
00729     // Add p0, if it exists.
00730     if( prev() )
00731     {
00732         if( prev()->knot().x() < rect.left() )
00733             rect.setLeft( prev()->knot().x() );
00734 
00735         if( prev()->knot().x() > rect.right() )
00736             rect.setRight( prev()->knot().x() );
00737 
00738         if( prev()->knot().y() < rect.top() )
00739             rect.setTop( prev()->knot().y() );
00740 
00741         if( prev()->knot().y() > rect.bottom() )
00742             rect.setBottom( prev()->knot().y() );
00743     }
00744 
00745     if( degree() == 3 )
00746     {
00747         /* 
00748         The basic idea for calculating the axis aligned bounding box (AABB) for bezier segments
00749         was found in comp.graphics.algorithms:
00750         
00751         Both the x coordinate and the y coordinate are polynomial. Newton told 
00752         us that at a maximum or minimum the derivative will be zero. Take all 
00753         those points, and take the ends; their AABB will be that of the curve. 
00754         
00755         We have a helpful trick for the derivatives: use the curve defined by 
00756         differences of successive control points. 
00757         This is a quadratic Bezier curve:
00758                 
00759                 2
00760         r(t) = Sum Bi,2(t) *Pi = B0,2(t) * P0 + B1,2(t) * P1 + B2,2(t) * P2
00761                i=0
00762 
00763         r(t) = (1-t)^2 * P0 + 2t(1-t) * P1 + t^2 * P2
00764 
00765         r(t) = (P2 - 2*P1 + P0) * t^2 + (2*P1 - 2*P0) * t + P0
00766 
00767         Setting r(t) to zero and using the x and y coordinates of differences of
00768         successive control points lets us find the paramters t, where the original 
00769         bezier curve has a minimum or a maximum.
00770         */
00771         double t[4];
00772     
00773         // calcualting the differnces between successive control points
00774         KoPoint x0 = p(1)-p(0);
00775         KoPoint x1 = p(2)-p(1);
00776         KoPoint x2 = p(3)-p(2);
00777 
00778         // calculating the coefficents
00779         KoPoint a = x2 - 2.0*x1 + x0;
00780         KoPoint b = 2.0*x1 - 2.0*x0;
00781         KoPoint c = x0;
00782 
00783         // calculating parameter t at minimum/maximum in x-direction
00784         if( a.x() == 0.0 )
00785         {
00786             t[0] = - c.x() / b.x();
00787             t[1] = -1.0;
00788         }
00789         else
00790         {
00791             double rx = b.x()*b.x() - 4.0*a.x()*c.x();
00792             if( rx < 0.0 )
00793                 rx = 0.0;
00794             t[0] = ( -b.x() + sqrt( rx ) ) / (2.0*a.x());
00795             t[1] = ( -b.x() - sqrt( rx ) ) / (2.0*a.x());
00796         }
00797 
00798         // calculating parameter t at minimum/maximum in y-direction
00799         if( a.y() == 0.0 )
00800         {
00801             t[2] = - c.y() / b.y();
00802             t[3] = -1.0;
00803         }
00804         else
00805         {
00806             double ry = b.y()*b.y() - 4.0*a.y()*c.y();
00807             if( ry < 0.0 )
00808                 ry = 0.0;
00809             t[2] = ( -b.y() + sqrt( ry ) ) / (2.0*a.y());
00810             t[3] = ( -b.y() - sqrt( ry ) ) / (2.0*a.y());
00811         }
00812 
00813         // calculate points at found minimum/maximum and update bounding box
00814         for( int i = 0; i < 4; ++i ) 
00815         {
00816             if( t[i] >= 0.0 && t[i] <= 1.0 )
00817             {
00818                 KoPoint p = pointAt( t[i] );
00819     
00820                 if( p.x() < rect.left() )
00821                     rect.setLeft( p.x() );
00822         
00823                 if( p.x() > rect.right() )
00824                     rect.setRight( p.x() );
00825 
00826                 if( p.y() < rect.top() )
00827                     rect.setTop( p.y() );
00828         
00829                 if( p.y() > rect.bottom() )
00830                     rect.setBottom( p.y() );
00831             }
00832         }
00833     
00834         return rect;
00835     }
00836 
00837     for( unsigned short i = 0; i < degree() - 1; ++i )
00838     {
00839         if( point( i ).x() < rect.left() )
00840             rect.setLeft( point( i ).x() );
00841 
00842         if( point( i ).x() > rect.right() )
00843             rect.setRight( point( i ).x() );
00844 
00845         if( point( i ).y() < rect.top() )
00846             rect.setTop( point( i ).y() );
00847 
00848         if( point( i ).y() > rect.bottom() )
00849             rect.setBottom( point( i ).y() );
00850     }
00851 
00852 
00853     return rect;
00854 }
00855 
00856 VSegment*
00857 VSegment::splitAt( double t )
00858 {
00859     if( !prev() )
00860     {
00861         return 0L;
00862     }
00863 
00864 
00865     // Create new segment.
00866     VSegment* segment = new VSegment( degree() );
00867 
00868     // Set segment state.
00869     segment->m_state = m_state;
00870 
00871 
00872     // Lines are easy: no need to modify the current segment.
00873     if( degree() == 1 )
00874     {
00875         segment->setKnot(
00876             prev()->knot() +
00877             ( knot() - prev()->knot() ) * t );
00878 
00879         return segment;
00880     }
00881 
00882 
00883     // Beziers.
00884 
00885     // Copy points.
00886     KoPoint* q = new KoPoint[ degree() + 1 ];
00887 
00888     q[ 0 ] = prev()->knot();
00889 
00890     for( unsigned short i = 0; i < degree(); ++i )
00891     {
00892         q[ i + 1 ] = point( i );
00893     }
00894 
00895 
00896     // The De Casteljau algorithm.
00897     for( unsigned short j = 1; j <= degree(); ++j )
00898     {
00899         for( unsigned short i = 0; i <= degree() - j; ++i )
00900         {
00901             q[ i ] = ( 1.0 - t ) * q[ i ] + t * q[ i + 1 ];
00902         }
00903 
00904         // Modify the new segment.
00905         segment->setPoint( j - 1, q[ 0 ] );
00906     }
00907 
00908     // Modify the current segment (no need to modify the knot though).
00909     for( unsigned short i = 1; i < degree(); ++i )
00910     {
00911         setPoint( i - 1, q[ i ] );
00912     }
00913 
00914 
00915     delete[]( q );
00916 
00917 
00918     return segment;
00919 }
00920 
00921 double
00922 VSegment::height(
00923     const KoPoint& a,
00924     const KoPoint& p,
00925     const KoPoint& b )
00926 {
00927     // Calculate determinant of AP and AB to obtain projection of vector AP to
00928     // the orthogonal vector of AB.
00929     const double det =
00930         p.x() * a.y() + b.x() * p.y() - p.x() * b.y() -
00931         a.x() * p.y() + a.x() * b.y() - b.x() * a.y();
00932 
00933     // Calculate norm = length(AB).
00934     const KoPoint ab = b - a;
00935     const double norm = sqrt( ab * ab );
00936 
00937     // If norm is very small, simply use distance AP.
00938     if( norm < VGlobal::verySmallNumber )
00939         return
00940             sqrt(
00941                 ( p.x() - a.x() ) * ( p.x() - a.x() ) +
00942                 ( p.y() - a.y() ) * ( p.y() - a.y() ) );
00943 
00944     // Normalize.
00945     return QABS( det ) / norm;
00946 }
00947 
00948 bool
00949 VSegment::linesIntersect(
00950     const KoPoint& a0,
00951     const KoPoint& a1,
00952     const KoPoint& b0,
00953     const KoPoint& b1 )
00954 {
00955     const KoPoint delta_a = a1 - a0;
00956     const double det_a = a1.x() * a0.y() - a1.y() * a0.x();
00957 
00958     const double r_b0 = delta_a.y() * b0.x() - delta_a.x() * b0.y() + det_a;
00959     const double r_b1 = delta_a.y() * b1.x() - delta_a.x() * b1.y() + det_a;
00960 
00961     if( r_b0 != 0.0 && r_b1 != 0.0 && r_b0 * r_b1 > 0.0 )
00962         return false;
00963 
00964     const KoPoint delta_b = b1 - b0;
00965 
00966     const double det_b = b1.x() * b0.y() - b1.y() * b0.x();
00967 
00968     const double r_a0 = delta_b.y() * a0.x() - delta_b.x() * a0.y() + det_b;
00969     const double r_a1 = delta_b.y() * a1.x() - delta_b.x() * a1.y() + det_b;
00970 
00971     if( r_a0 != 0.0 && r_a1 != 0.0 && r_a0 * r_a1 > 0.0 )
00972         return false;
00973 
00974     return true;
00975 }
00976 
00977 bool
00978 VSegment::intersects( const VSegment& segment ) const
00979 {
00980     if(
00981         !prev() ||
00982         !segment.prev() )
00983     {
00984         return false;
00985     }
00986 
00987 
00988     //TODO: this just dumbs down beziers to lines!
00989     return linesIntersect( segment.prev()->knot(), segment.knot(), prev()->knot(), knot() );
00990 }
00991 
00992 // TODO: Move this function into "userland"
00993 uint
00994 VSegment::nodeNear( const KoPoint& p, double isNearRange ) const
00995 {
00996     int index = 0;
00997 
00998     for( unsigned short i = 0; i < degree(); ++i )
00999     {
01000         if( point( 0 ).isNear( p, isNearRange ) )
01001         {
01002             index = i + 1;
01003             break;
01004         }
01005     }
01006 
01007     return index;
01008 }
01009 
01010 VSegment*
01011 VSegment::revert() const
01012 {
01013     if( !prev() )
01014         return 0L;
01015 
01016     // Create new segment.
01017     VSegment* segment = new VSegment( degree() );
01018 
01019     segment->m_state = m_state;
01020 
01021 
01022     // Swap points.
01023     for( unsigned short i = 0; i < degree() - 1; ++i )
01024     {
01025         segment->setPoint( i, point( degree() - 2 - i ) );
01026     }
01027 
01028     segment->setKnot( prev()->knot() );
01029 
01030 
01031     // TODO swap node attributes (selected)
01032 
01033     return segment;
01034 }
01035 
01036 VSegment*
01037 VSegment::prev() const
01038 {
01039     VSegment* segment = m_prev;
01040 
01041     while( segment && segment->state() == deleted )
01042     {
01043         segment = segment->m_prev;
01044     }
01045 
01046     return segment;
01047 }
01048 
01049 VSegment*
01050 VSegment::next() const
01051 {
01052     VSegment* segment = m_next;
01053 
01054     while( segment && segment->state() == deleted )
01055     {
01056         segment = segment->m_next;
01057     }
01058 
01059     return segment;
01060 }
01061 
01062 // TODO: remove this backward compatibility function after koffice 1.3.x
01063 void
01064 VSegment::load( const QDomElement& element )
01065 {
01066     if( element.tagName() == "CURVE" )
01067     {
01068         setDegree( 3 );
01069 
01070         setPoint(
01071             0,
01072             KoPoint(
01073                 element.attribute( "x1" ).toDouble(),
01074                 element.attribute( "y1" ).toDouble() ) );
01075 
01076         setPoint(
01077             1,
01078             KoPoint(
01079                 element.attribute( "x2" ).toDouble(),
01080                 element.attribute( "y2" ).toDouble() ) );
01081 
01082         setKnot(
01083             KoPoint(
01084                 element.attribute( "x3" ).toDouble(),
01085                 element.attribute( "y3" ).toDouble() ) );
01086     }
01087     else if( element.tagName() == "LINE" )
01088     {
01089         setDegree( 1 );
01090 
01091         setKnot(
01092             KoPoint(
01093                 element.attribute( "x" ).toDouble(),
01094                 element.attribute( "y" ).toDouble() ) );
01095     }
01096     else if( element.tagName() == "MOVE" )
01097     {
01098         setDegree( 1 );
01099 
01100         setKnot(
01101             KoPoint(
01102                 element.attribute( "x" ).toDouble(),
01103                 element.attribute( "y" ).toDouble() ) );
01104     }
01105 }
01106 
01107 VSegment*
01108 VSegment::clone() const
01109 {
01110     return new VSegment( *this );
01111 }
01112 
KDE Home | KDE Accessibility Home | Description of Access Keys