← Back to branch summary

~ubuntu-branches/ubuntu/precise/koffice/precise

« back to all changes in this revision

Viewing changes to kpresenter/KoPointArray.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jonathan Riddell
  • Date: 2006-04-20 21:38:53 UTC
  • mfrom: (1.1.3 upstream)
  • Revision ID: james.westby@ubuntu.com-20060420213853-j5lxluqvymxt2zny
Tags: 1:1.5.0-0ubuntu2
Ubuntu upload 

Show diffs side-by-side

added added

removed removed

Lines of Context:
kpresenter/KoPointArray.cpp
 
1
// -*- Mode: c++; c-basic-offset: 4; indent-tabs-mode: nil; tab-width: 4; -*-
 
2
/* This file is part of the KDE project
 
3
   Copyright (C) 2001 Laurent MONTEL <lmontel@mandrakesoft.com>
 
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., 51 Franklin Street, Fifth Floor,
 
18
 * Boston, MA 02110-1301, USA.
 
19
*/
 
20
 
 
21
#include "KoPointArray.h"
 
22
#include <KoRect.h>
 
23
#include <stdarg.h>
 
24
#include <KoZoomHandler.h>
 
25
 
 
26
void KoPointArray::translate( double dx, double dy )
 
27
{
 
28
    register KoPoint *p = data();
 
29
    register int i = size();
 
30
    KoPoint pt( dx, dy );
 
31
    while ( i-- ) {
 
32
        *p += pt;
 
33
        p++;
 
34
    }
 
35
}
 
36
 
 
37
void KoPointArray::point( uint index, double *x, double *y ) const
 
38
{
 
39
    KoPoint p = QMemArray<KoPoint>::at( index );
 
40
    if ( x )
 
41
        *x = (double)p.x();
 
42
    if ( y )
 
43
        *y = (double)p.y();
 
44
}
 
45
 
 
46
KoPoint KoPointArray::point( uint index ) const
 
47
{ // #### index out of bounds
 
48
    return QMemArray<KoPoint>::at( index );
 
49
}
 
50
 
 
51
void KoPointArray::setPoint( uint index, double x, double y )
 
52
{ // #### index out of bounds
 
53
    QMemArray<KoPoint>::at( index ) = KoPoint( x, y );
 
54
}
 
55
 
 
56
 
 
57
 
 
58
bool KoPointArray::putPoints( int index, int nPoints, double firstx, double firsty,
 
59
                              ... )
 
60
{
 
61
    va_list ap;
 
62
    if ( index + nPoints > (int)size() ) {  // extend array
 
63
        if ( !resize(index + nPoints) )
 
64
            return FALSE;
 
65
    }
 
66
    if ( nPoints <= 0 )
 
67
        return TRUE;
 
68
    setPoint( index, firstx, firsty );      // set first point
 
69
    int i = index + 1;
 
70
    double x, y;
 
71
    nPoints--;
 
72
    va_start( ap, firsty );
 
73
    while ( nPoints-- ) {
 
74
        x = va_arg( ap, double );
 
75
        y = va_arg( ap, double );
 
76
        setPoint( i++, x, y );
 
77
    }
 
78
    va_end( ap );
 
79
    return TRUE;
 
80
}
 
81
 
 
82
void split(const double *p, double *l, double *r)
 
83
{
 
84
    double tmpx;
 
85
    double tmpy;
 
86
 
 
87
    l[0] =  p[0];
 
88
    l[1] =  p[1];
 
89
    r[6] =  p[6];
 
90
    r[7] =  p[7];
 
91
 
 
92
    l[2] = (p[0]+ p[2])/2;
 
93
    l[3] = (p[1]+ p[3])/2;
 
94
    tmpx = (p[2]+ p[4])/2;
 
95
    tmpy = (p[3]+ p[5])/2;
 
96
    r[4] = (p[4]+ p[6])/2;
 
97
    r[5] = (p[5]+ p[7])/2;
 
98
 
 
99
    l[4] = (l[2]+ tmpx)/2;
 
100
    l[5] = (l[3]+ tmpy)/2;
 
101
    r[2] = (tmpx + r[4])/2;
 
102
    r[3] = (tmpy + r[5])/2;
 
103
 
 
104
    l[6] = (l[4]+ r[2])/2;
 
105
    l[7] = (l[5]+ r[3])/2;
 
106
    r[0] = l[6];
 
107
    r[1] = l[7];
 
108
}
 
109
 
 
110
// Based on:
 
111
//
 
112
//   A Fast 2D Point-On-Line Test
 
113
//   by Alan Paeth
 
114
//   from "Graphics Gems", Academic Press, 1990
 
115
static
 
116
int pnt_on_line( const int* p, const int* q, const int* t )
 
117
{
 
118
/*
 
119
 * given a line through P:(px,py) Q:(qx,qy) and T:(tx,ty)
 
120
 * return 0 if T is not on the line through      <--P--Q-->
 
121
 *        1 if T is on the open ray ending at P: <--P
 
122
 *        2 if T is on the closed interior along:   P--Q
 
123
 *        3 if T is on the open ray beginning at Q:    Q-->
 
124
 *
 
125
 * Example: consider the line P = (3,2), Q = (17,7). A plot
 
126
 * of the test points T(x,y) (with 0 mapped onto '.') yields:
 
127
 *
 
128
 *     8| . . . . . . . . . . . . . . . . . 3 3
 
129
 *  Y  7| . . . . . . . . . . . . . . 2 2 Q 3 3    Q = 2
 
130
 *     6| . . . . . . . . . . . 2 2 2 2 2 . . .
 
131
 *  a  5| . . . . . . . . 2 2 2 2 2 2 . . . . .
 
132
 *  x  4| . . . . . 2 2 2 2 2 2 . . . . . . . .
 
133
 *  i  3| . . . 2 2 2 2 2 . . . . . . . . . . .
 
134
 *  s  2| 1 1 P 2 2 . . . . . . . . . . . . . .    P = 2
 
135
 *     1| 1 1 . . . . . . . . . . . . . . . . .
 
136
 *      +--------------------------------------
 
137
 *        1 2 3 4 5 X-axis 10        15      19
 
138
 *
 
139
 * Point-Line distance is normalized with the Infinity Norm
 
140
 * avoiding square-root code and tightening the test vs the
 
141
 * Manhattan Norm. All math is done on the field of integers.
 
142
 * The latter replaces the initial ">= MAX(...)" test with
 
143
 * "> (ABS(qx-px) + ABS(qy-py))" loosening both inequality
 
144
 * and norm, yielding a broader target line for selection.
 
145
 * The tightest test is employed here for best discrimination
 
146
 * in merging collinear (to grid coordinates) vertex chains
 
147
 * into a larger, spanning vectors within the Lemming editor.
 
148
 */
 
149
 
 
150
    // if all points are coincident, return condition 2 (on line)
 
151
    if(q[0]==p[0] && q[1]==p[1] && q[0]==t[0] && q[1]==t[1]) {
 
152
        return 2;
 
153
    }
 
154
 
 
155
    if ( QABS((q[1]-p[1])*(t[0]-p[0])-(t[1]-p[1])*(q[0]-p[0])) >=
 
156
         (QMAX(QABS(q[0]-p[0]), QABS(q[1]-p[1])))) return 0;
 
157
 
 
158
    if (((q[0]<p[0])&&(p[0]<t[0])) || ((q[1]<p[1])&&(p[1]<t[1])))
 
159
        return 1 ;
 
160
    if (((t[0]<p[0])&&(p[0]<q[0])) || ((t[1]<p[1])&&(p[1]<q[1])))
 
161
        return 1 ;
 
162
    if (((p[0]<q[0])&&(q[0]<t[0])) || ((p[1]<q[1])&&(q[1]<t[1])))
 
163
        return 3 ;
 
164
    if (((t[0]<q[0])&&(q[0]<p[0])) || ((t[1]<q[1])&&(q[1]<p[1])))
 
165
        return 3 ;
 
166
 
 
167
    return 2 ;
 
168
}
 
169
 
 
170
static
 
171
void polygonizeQBezier( double* acc, int& accsize, const double ctrl[],
 
172
                        int maxsize )
 
173
{
 
174
    if ( accsize > maxsize / 2 )
 
175
    {
 
176
        // This never happens in practice.
 
177
 
 
178
        if ( accsize >= maxsize-4 )
 
179
            return;
 
180
        // Running out of space - approximate by a line.
 
181
        acc[accsize++] = ctrl[0];
 
182
        acc[accsize++] = ctrl[1];
 
183
        acc[accsize++] = ctrl[6];
 
184
        acc[accsize++] = ctrl[7];
 
185
        return;
 
186
    }
 
187
 
 
188
    //intersects:
 
189
    double l[8];
 
190
    double r[8];
 
191
    split( ctrl, l, r);
 
192
 
 
193
    // convert to integers for line condition check
 
194
    int c0[2]; c0[0] = int(ctrl[0]); c0[1] = int(ctrl[1]);
 
195
    int c1[2]; c1[0] = int(ctrl[2]); c1[1] = int(ctrl[3]);
 
196
    int c2[2]; c2[0] = int(ctrl[4]); c2[1] = int(ctrl[5]);
 
197
    int c3[2]; c3[0] = int(ctrl[6]); c3[1] = int(ctrl[7]);
 
198
 
 
199
    // #### Duplication needed?
 
200
    if ( QABS(c1[0]-c0[0]) <= 1 && QABS(c1[1]-c0[1]) <= 1
 
201
         && QABS(c2[0]-c0[0]) <= 1 && QABS(c2[1]-c0[1]) <= 1
 
202
         && QABS(c3[0]-c1[0]) <= 1 && QABS(c3[1]-c0[1]) <= 1 )
 
203
    {
 
204
        // Approximate by one line.
 
205
        // Dont need to write last pt as it is the same as first pt
 
206
        // on the next segment
 
207
        acc[accsize++] = l[0];
 
208
        acc[accsize++] = l[1];
 
209
        return;
 
210
    }
 
211
 
 
212
    if ( ( pnt_on_line( c0, c3, c1 ) == 2 && pnt_on_line( c0, c3, c2 ) == 2 )
 
213
         || ( QABS(c1[0]-c0[0]) <= 1 && QABS(c1[1]-c0[1]) <= 1
 
214
              && QABS(c2[0]-c0[0]) <= 1 && QABS(c2[1]-c0[1]) <= 1
 
215
              && QABS(c3[0]-c1[0]) <= 1 && QABS(c3[1]-c0[1]) <= 1 ) )
 
216
    {
 
217
        // Approximate by one line.
 
218
        // Dont need to write last pt as it is the same as first pt
 
219
        // on the next segment
 
220
        acc[accsize++] = l[0];
 
221
        acc[accsize++] = l[1];
 
222
        return;
 
223
    }
 
224
 
 
225
    // Too big and too curved - recusively subdivide.
 
226
    polygonizeQBezier( acc, accsize, l, maxsize );
 
227
    polygonizeQBezier( acc, accsize, r, maxsize );
 
228
}
 
229
 
 
230
 
 
231
KoRect KoPointArray::boundingRect() const
 
232
{
 
233
    if ( isEmpty() )
 
234
        return KoRect( 0, 0, 0, 0 );        // null rectangle
 
235
    register KoPoint *pd = data();
 
236
    double minx, maxx, miny, maxy;
 
237
    minx = maxx = pd->x();
 
238
    miny = maxy = pd->y();
 
239
    pd++;
 
240
    for ( int i=1; i<(int)size(); i++ ) {   // find min+max x and y
 
241
        if ( pd->x() < minx )
 
242
            minx = pd->x();
 
243
        else if ( pd->x() > maxx )
 
244
            maxx = pd->x();
 
245
        if ( pd->y() < miny )
 
246
            miny = pd->y();
 
247
        else if ( pd->y() > maxy )
 
248
            maxy = pd->y();
 
249
        pd++;
 
250
    }
 
251
    return KoRect( KoPoint(minx,miny), KoPoint(maxx,maxy) );
 
252
}
 
253
 
 
254
 
 
255
KoPointArray KoPointArray::cubicBezier() const
 
256
{
 
257
    if ( size() != 4 ) {
 
258
#if defined(QT_CHECK_RANGE)
 
259
        qWarning( "QPointArray::bezier: The array must have 4 control points" );
 
260
#endif
 
261
        KoPointArray pa;
 
262
        return pa;
 
263
    } else {
 
264
        KoRect r = boundingRect();
 
265
        int m = (int)(4+2*QMAX(r.width(),r.height()));
 
266
        double *p = new double[m];
 
267
        double ctrl[8];
 
268
        int i;
 
269
        for (i=0; i<4; i++) {
 
270
            ctrl[i*2] = at(i).x();
 
271
            ctrl[i*2+1] = at(i).y();
 
272
        }
 
273
        int len=0;
 
274
        polygonizeQBezier( p, len, ctrl, m );
 
275
        KoPointArray pa((len/2)+1); // one extra point for last point on line
 
276
        int j=0;
 
277
        for (i=0; j<len; i++) {
 
278
            double x = qRound(p[j++]);
 
279
            double y = qRound(p[j++]);
 
280
            pa[i] = KoPoint(x,y);
 
281
        }
 
282
        // add last pt on the line, which will be at the last control pt
 
283
        pa[(int)pa.size()-1] = at(3);
 
284
        delete[] p;
 
285
 
 
286
        return pa;
 
287
    }
 
288
}
 
289
 
 
290
QPointArray KoPointArray::zoomPointArray( const KoZoomHandler* zoomHandler ) const
 
291
{
 
292
    QPointArray tmpPoints(size());
 
293
    for ( uint i= 0; i<size();i++ ) {
 
294
        KoPoint p = at( i );
 
295
        tmpPoints.putPoints( i, 1, zoomHandler->zoomItX(p.x()),zoomHandler->zoomItY(p.y()) );
 
296
    }
 
297
    return tmpPoints;
 
298
}
 
299
 
 
300
QPointArray KoPointArray::zoomPointArray( const KoZoomHandler* zoomHandler, int penWidth ) const
 
301
{
 
302
    double fx;
 
303
    double fy;
 
304
    KoSize ext = boundingRect().size();
 
305
    int pw = zoomHandler->zoomItX( penWidth ) / 2;
 
306
 
 
307
    fx = (double)( zoomHandler->zoomItX(ext.width()) - 2 * pw ) / ext.width();
 
308
    fy = (double)( zoomHandler->zoomItY(ext.height()) - 2 * pw ) / ext.height();
 
309
 
 
310
    unsigned int index = 0;
 
311
    QPointArray tmpPoints;
 
312
    KoPointArray::ConstIterator it;
 
313
    for ( it = begin(); it != end(); ++it, ++index ) {
 
314
        int tmpX = qRound((*it).x() * fx + pw);
 
315
        int tmpY = qRound((*it).y() * fy + pw);
 
316
 
 
317
        tmpPoints.putPoints( index, 1, tmpX, tmpY );
 
318
    }
 
319
    return tmpPoints;
 
320
}