← Back to branch summary

~ubuntu-branches/ubuntu/edgy/koffice/edgy-updates

« back to all changes in this revision

Viewing changes to karbon/commands/vbooleancmd.cc

  • Committer: Bazaar Package Importer
  • Author(s): Ben Burton
  • Date: 2004-05-09 11:33:00 UTC
  • mto: This revision was merged to the branch mainline in revision 3.
  • Revision ID: james.westby@ubuntu.com-20040509113300-xi5t1z4yxe7n03x7
Tags: upstream-1.3.1
Import upstream version 1.3.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
karbon/commands/vbooleancmd.cc
 
1
/* This file is part of the KDE project
 
2
   Copyright (C) 2001, The Karbon Developers
 
3
   Copyright (C) 2002, The Karbon Developers
 
4
 
 
5
   This library is free software; you can redistribute it and/or
 
6
   modify it under the terms of the GNU Library General Public
 
7
   License as published by the Free Software Foundation; either
 
8
   version 2 of the License, or (at your option) any later version.
 
9
 
 
10
   This library is distributed in the hope that it will be useful,
 
11
   but WITHOUT ANY WARRANTY; without even the implied warranty of
 
12
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
13
   Library General Public License for more details.
 
14
 
 
15
   You should have received a copy of the GNU Library General Public License
 
16
   along with this library; see the file COPYING.LIB.  If not, write to
 
17
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 
18
   Boston, MA 02111-1307, USA.
 
19
*/
 
20
 
 
21
 
 
22
#include <qptrlist.h>
 
23
#include <qvaluelist.h>
 
24
 
 
25
#include <klocale.h>
 
26
 
 
27
#include "vbooleancmd.h"
 
28
#include "vpath.h"
 
29
#include "vsegment.h"
 
30
#include "vselection.h"
 
31
#include "vdocument.h"
 
32
 
 
33
VBooleanCmd::VBooleanCmd( VDocument *doc, VBooleanType type )
 
34
        : VCommand( doc, i18n( "Boolean Operation" ) )
 
35
{
 
36
        m_selection = document()->selection()->clone();
 
37
        m_type = type;
 
38
}
 
39
 
 
40
VBooleanCmd::~VBooleanCmd()
 
41
{
 
42
        delete( m_selection );
 
43
}
 
44
 
 
45
void
 
46
VBooleanCmd::execute()
 
47
{
 
48
        VObjectListIterator itr( m_selection->objects() );
 
49
        for ( ; itr.current() ; ++itr )
 
50
        {
 
51
// TODO: pair wise visiting.
 
52
        }
 
53
 
 
54
//      document()->append(  );
 
55
        document()->selection()->clear();
 
56
}
 
57
 
 
58
void
 
59
VBooleanCmd::unexecute()
 
60
{
 
61
}
 
62
 
 
63
bool
 
64
VBooleanCmd::visit( VObject& object1, VObject& object2 )
 
65
{
 
66
        m_path1 = 0L;
 
67
        m_path2 = 0L;
 
68
        object1.accept( *this );
 
69
        object2.accept( *this );
 
70
 
 
71
        return success();
 
72
}
 
73
 
 
74
void
 
75
VBooleanCmd::visitVSubpath( VSubpath& path )
 
76
{
 
77
        if( m_path1 == 0L )
 
78
                m_path1 = &path;
 
79
        else if( m_path2 == 0L )
 
80
        {
 
81
                m_path2 = &path;
 
82
 
 
83
                // intersection parameters (t):
 
84
                VParamList params1;
 
85
                VParamList params2;
 
86
                VParamList::iterator pItr;
 
87
 
 
88
                double prevParam;
 
89
 
 
90
                m_path1->first();
 
91
 
 
92
                // ommit "begin" segment:
 
93
                while( m_path1->next() )
 
94
                {
 
95
                        params1.clear();
 
96
 
 
97
                        m_path2->first();
 
98
 
 
99
                        // ommit "begin" segment:
 
100
                        while( m_path2->next() )
 
101
                        {
 
102
                                params2.clear();
 
103
                        
 
104
                                recursiveSubdivision(
 
105
                                        *m_path1->current(), 0.0, 1.0,
 
106
                                        *m_path2->current(), 0.0, 1.0,
 
107
                                        params1, params2 );
 
108
 
 
109
                                qHeapSort( params2 );
 
110
 
 
111
                                prevParam = 0.0;
 
112
 
 
113
                                // walk down all intersection params and insert knots:
 
114
                                for( pItr = params2.begin(); pItr != params2.end(); ++pItr )
 
115
                                {
 
116
                                        m_path2->insert(
 
117
                                                m_path2->current()->splitAt(
 
118
                                                        ( *pItr - prevParam )/( 1.0 - prevParam ) ) );
 
119
 
 
120
                                        m_path2->next();
 
121
                                        prevParam = *pItr;
 
122
                                }
 
123
                        }
 
124
 
 
125
                        qHeapSort( params1 );
 
126
 
 
127
                        prevParam = 0.0;
 
128
 
 
129
                        // walk down all intersection params and insert knots:
 
130
                        for( pItr = params1.begin(); pItr != params1.end(); ++pItr )
 
131
                        {
 
132
                                m_path1->insert(
 
133
                                        m_path1->current()->splitAt(
 
134
                                                ( *pItr - prevParam )/( 1.0 - prevParam ) ) );
 
135
 
 
136
                                m_path1->next();
 
137
                                prevParam = *pItr;
 
138
                        }
 
139
                }
 
140
        }
 
141
}
 
142
 
 
143
void
 
144
VBooleanCmd::recursiveSubdivision(
 
145
        const VSegment& segment1, double t0_1, double t1_1,
 
146
        const VSegment& segment2, double t0_2, double t1_2,
 
147
        VParamList& params1, VParamList& params2 )
 
148
{
 
149
        if(
 
150
                !segment1.boundingBox().intersects(
 
151
                        segment2.boundingBox() ) )
 
152
        {
 
153
                return;
 
154
        }
 
155
 
 
156
        if( segment1.isFlat() )
 
157
        {
 
158
                // calculate intersection of line segments:
 
159
                if( segment2.isFlat() )
 
160
                {
 
161
                        KoPoint v1  = segment1.knot() - segment1.prev()->knot();
 
162
                        KoPoint v2  = segment2.knot() - segment2.prev()->knot();
 
163
 
 
164
                        double det = v2.x() * v1.y() - v2.y() * v1.x();
 
165
 
 
166
                        if( 1.0 + det == 1.0 )
 
167
                                return;
 
168
                        else
 
169
                        {
 
170
                                KoPoint v = segment2.prev()->knot() - segment1.prev()->knot();
 
171
                                const double one_det = 1.0 / det;
 
172
 
 
173
                                double t1 = one_det * ( v2.x() * v.y() - v2.y() * v.x() );
 
174
                                double t2 = one_det * ( v1.x() * v.y() - v1.y() * v.x() );
 
175
 
 
176
                                if ( t1 < 0.0 || t1 > 1.0 || t2 < 0.0 || t2 > 1.0 )
 
177
                                        return;
 
178
 
 
179
                                params1.append( t0_1 + t1 * ( t1_1 - t0_1 ) );
 
180
                                params2.append( t0_2 + t2 * ( t1_2 - t0_2 ) );
 
181
                        }
 
182
                }
 
183
                else
 
184
                {
 
185
                        // "copy segment" and split it at midpoint:
 
186
                        VSubpath path2( segment2 );
 
187
                        path2.insert( path2.current()->splitAt( 0.5 ) );
 
188
 
 
189
                        double mid2 = 0.5 * ( t0_2 + t1_2 );
 
190
 
 
191
                        recursiveSubdivision(
 
192
                                *path2.current(), t0_2, mid2,
 
193
                                segment1,         t0_1, t1_1, params2, params1 );
 
194
                        recursiveSubdivision(
 
195
                                *path2.next(),    mid2, t1_2,
 
196
                                segment1,         t0_1, t1_1, params2, params1 );
 
197
                }
 
198
        }
 
199
        else
 
200
        {
 
201
                // "copy segment" and split it at midpoint:
 
202
                VSubpath path1( segment1 );
 
203
                path1.insert( path1.current()->splitAt( 0.5 ) );
 
204
 
 
205
                double mid1 = 0.5 * ( t0_1 + t1_1 );
 
206
 
 
207
                if( segment2.isFlat() )
 
208
                {
 
209
                        recursiveSubdivision(
 
210
                                *path1.current(), t0_1, mid1,
 
211
                                segment2,         t0_2, t1_2, params1, params2 );
 
212
                        recursiveSubdivision(
 
213
                                *path1.next(),    mid1, t1_1,
 
214
                                segment2,         t0_2, t1_2, params1, params2 );
 
215
                }
 
216
                else
 
217
                {
 
218
                        // "copy segment" and split it at midpoint:
 
219
                        VSubpath path2( segment2 );
 
220
                        path2.insert( path2.current()->splitAt( 0.5 ) );
 
221
 
 
222
                        double mid2 = 0.5 * ( t0_2 + t1_2 );
 
223
 
 
224
                        recursiveSubdivision(
 
225
                                *path1.current(), t0_1, mid1,
 
226
                                *path2.current(), t0_2, mid2, params1, params2 );
 
227
                        recursiveSubdivision(
 
228
                                *path1.next(),    mid1, t1_1,
 
229
                                *path2.current(), t0_2, mid2, params1, params2 );
 
230
 
 
231
                        recursiveSubdivision(
 
232
                                *path1.prev(),    t0_1, mid1,
 
233
                                *path2.next(),    mid2, t1_2, params1, params2 );
 
234
                        recursiveSubdivision(
 
235
                                *path1.next(),    mid1, t1_1,
 
236
                                *path2.current(), mid2, t1_2, params1, params2 );
 
237
                }
 
238
        }
 
239
}
 
240