karbon

vbooleancmd.cc

00001 /* This file is part of the KDE project
00002    Copyright (C) 2001, The Karbon Developers
00003    Copyright (C) 2002, The Karbon Developers
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 
00022 #include <qptrlist.h>
00023 #include <qvaluelist.h>
00024 
00025 #include <klocale.h>
00026 
00027 #include "vbooleancmd.h"
00028 #include "vpath.h"
00029 #include "vsegment.h"
00030 #include "vselection.h"
00031 #include "vdocument.h"
00032 
00033 VBooleanCmd::VBooleanCmd( VDocument *doc, VBooleanType type )
00034     : VCommand( doc, i18n( "Boolean Operation" ) )
00035 {
00036     m_selection = document()->selection()->clone();
00037     m_type = type;
00038 }
00039 
00040 VBooleanCmd::~VBooleanCmd()
00041 {
00042     delete( m_selection );
00043 }
00044 
00045 void
00046 VBooleanCmd::execute()
00047 {
00048     VObjectListIterator itr( m_selection->objects() );
00049     for ( ; itr.current() ; ++itr )
00050     {
00051 // TODO: pair wise visiting.
00052     }
00053 
00054 //  document()->append(  );
00055     document()->selection()->clear();
00056 }
00057 
00058 void
00059 VBooleanCmd::unexecute()
00060 {
00061 }
00062 
00063 bool
00064 VBooleanCmd::visit( VObject& object1, VObject& object2 )
00065 {
00066     m_path1 = 0L;
00067     m_path2 = 0L;
00068     object1.accept( *this );
00069     object2.accept( *this );
00070 
00071     return success();
00072 }
00073 
00074 void
00075 VBooleanCmd::visitVSubpath( VSubpath& path )
00076 {
00077     if( m_path1 == 0L )
00078         m_path1 = &path;
00079     else if( m_path2 == 0L )
00080     {
00081         m_path2 = &path;
00082 
00083         // intersection parameters (t):
00084         VParamList params1;
00085         VParamList params2;
00086         VParamList::iterator pItr;
00087 
00088         double prevParam;
00089 
00090         m_path1->first();
00091 
00092         // ommit "begin" segment:
00093         while( m_path1->next() )
00094         {
00095             params1.clear();
00096 
00097             m_path2->first();
00098 
00099             // ommit "begin" segment:
00100             while( m_path2->next() )
00101             {
00102                 params2.clear();
00103             
00104                 recursiveSubdivision(
00105                     *m_path1->current(), 0.0, 1.0,
00106                     *m_path2->current(), 0.0, 1.0,
00107                     params1, params2 );
00108 
00109                 qHeapSort( params2 );
00110 
00111                 prevParam = 0.0;
00112 
00113                 // walk down all intersection params and insert knots:
00114                 for( pItr = params2.begin(); pItr != params2.end(); ++pItr )
00115                 {
00116                     m_path2->insert(
00117                         m_path2->current()->splitAt(
00118                             ( *pItr - prevParam )/( 1.0 - prevParam ) ) );
00119 
00120                     m_path2->next();
00121                     prevParam = *pItr;
00122                 }
00123             }
00124 
00125             qHeapSort( params1 );
00126 
00127             prevParam = 0.0;
00128 
00129             // walk down all intersection params and insert knots:
00130             for( pItr = params1.begin(); pItr != params1.end(); ++pItr )
00131             {
00132                 m_path1->insert(
00133                     m_path1->current()->splitAt(
00134                         ( *pItr - prevParam )/( 1.0 - prevParam ) ) );
00135 
00136                 m_path1->next();
00137                 prevParam = *pItr;
00138             }
00139         }
00140     }
00141 }
00142 
00143 void
00144 VBooleanCmd::recursiveSubdivision(
00145     const VSegment& segment1, double t0_1, double t1_1,
00146     const VSegment& segment2, double t0_2, double t1_2,
00147     VParamList& params1, VParamList& params2 )
00148 {
00149     if(
00150         !segment1.boundingBox().intersects(
00151             segment2.boundingBox() ) )
00152     {
00153         return;
00154     }
00155 
00156     if( segment1.isFlat() )
00157     {
00158         // calculate intersection of line segments:
00159         if( segment2.isFlat() )
00160         {
00161             KoPoint v1  = segment1.knot() - segment1.prev()->knot();
00162             KoPoint v2  = segment2.knot() - segment2.prev()->knot();
00163 
00164             double det = v2.x() * v1.y() - v2.y() * v1.x();
00165 
00166             if( 1.0 + det == 1.0 )
00167                 return;
00168             else
00169             {
00170                 KoPoint v = segment2.prev()->knot() - segment1.prev()->knot();
00171                 const double one_det = 1.0 / det;
00172 
00173                 double t1 = one_det * ( v2.x() * v.y() - v2.y() * v.x() );
00174                 double t2 = one_det * ( v1.x() * v.y() - v1.y() * v.x() );
00175 
00176                 if ( t1 < 0.0 || t1 > 1.0 || t2 < 0.0 || t2 > 1.0 )
00177                     return;
00178 
00179                 params1.append( t0_1 + t1 * ( t1_1 - t0_1 ) );
00180                 params2.append( t0_2 + t2 * ( t1_2 - t0_2 ) );
00181             }
00182         }
00183         else
00184         {
00185             // "copy segment" and split it at midpoint:
00186             VSubpath path2( segment2 );
00187             path2.insert( path2.current()->splitAt( 0.5 ) );
00188 
00189             double mid2 = 0.5 * ( t0_2 + t1_2 );
00190 
00191             recursiveSubdivision(
00192                 *path2.current(), t0_2, mid2,
00193                 segment1,         t0_1, t1_1, params2, params1 );
00194             recursiveSubdivision(
00195                 *path2.next(),    mid2, t1_2,
00196                 segment1,         t0_1, t1_1, params2, params1 );
00197         }
00198     }
00199     else
00200     {
00201         // "copy segment" and split it at midpoint:
00202         VSubpath path1( segment1 );
00203         path1.insert( path1.current()->splitAt( 0.5 ) );
00204 
00205         double mid1 = 0.5 * ( t0_1 + t1_1 );
00206 
00207         if( segment2.isFlat() )
00208         {
00209             recursiveSubdivision(
00210                 *path1.current(), t0_1, mid1,
00211                 segment2,         t0_2, t1_2, params1, params2 );
00212             recursiveSubdivision(
00213                 *path1.next(),    mid1, t1_1,
00214                 segment2,         t0_2, t1_2, params1, params2 );
00215         }
00216         else
00217         {
00218             // "copy segment" and split it at midpoint:
00219             VSubpath path2( segment2 );
00220             path2.insert( path2.current()->splitAt( 0.5 ) );
00221 
00222             double mid2 = 0.5 * ( t0_2 + t1_2 );
00223 
00224             recursiveSubdivision(
00225                 *path1.current(), t0_1, mid1,
00226                 *path2.current(), t0_2, mid2, params1, params2 );
00227             recursiveSubdivision(
00228                 *path1.next(),    mid1, t1_1,
00229                 *path2.current(), t0_2, mid2, params1, params2 );
00230 
00231             recursiveSubdivision(
00232                 *path1.prev(),    t0_1, mid1,
00233                 *path2.next(),    mid2, t1_2, params1, params2 );
00234             recursiveSubdivision(
00235                 *path1.next(),    mid1, t1_1,
00236                 *path2.current(), mid2, t1_2, params1, params2 );
00237         }
00238     }
00239 }
00240 
KDE Home | KDE Accessibility Home | Description of Access Keys