00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
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
00052 }
00053
00054
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
00084 VParamList params1;
00085 VParamList params2;
00086 VParamList::iterator pItr;
00087
00088 double prevParam;
00089
00090 m_path1->first();
00091
00092
00093 while( m_path1->next() )
00094 {
00095 params1.clear();
00096
00097 m_path2->first();
00098
00099
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
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
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
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
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
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
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