kpresenter

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