← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/gui/painting/qpolygonclipper_p.h

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/gui/painting/qpolygonclipper_p.h
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the painting module of the Qt Toolkit.
 
6
**
 
7
** This file may be distributed under the terms of the Q Public License
 
8
** as defined by Trolltech AS of Norway and appearing in the file
 
9
** LICENSE.QPL included in the packaging of this file.
 
10
**
 
11
** This file may be distributed and/or modified under the terms of the
 
12
** GNU General Public License version 2 as published by the Free Software
 
13
** Foundation and appearing in the file LICENSE.GPL included in the
 
14
** packaging of this file.
 
15
**
 
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
17
**   information about Qt Commercial License Agreements.
 
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
20
**
 
21
** Contact info@trolltech.com if any conditions of this licensing are
 
22
** not clear to you.
 
23
**
 
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
26
**
 
27
**/
 
28
 
 
29
#ifndef QPOLYGONCLIPPER_P_H
 
30
#define QPOLYGONCLIPPER_P_H
 
31
 
 
32
//
 
33
//  W A R N I N G
 
34
//  -------------
 
35
//
 
36
// This file is not part of the Qt API.  It exists for the convenience
 
37
// of other Qt classes.  This header file may change from version to
 
38
// version without notice, or even be removed.
 
39
//
 
40
// We mean it.
 
41
//
 
42
 
 
43
#include "qdatabuffer_p.h"
 
44
 
 
45
/* based on sutherland-hodgman line-by-line clipping, as described in
 
46
   Computer Graphics and Principles */
 
47
template <typename InType, typename OutType, typename CastType> class QPolygonClipper
 
48
{
 
49
public:
 
50
    QPolygonClipper()
 
51
    {
 
52
        x1 = y1 = x2 = y2 = 0;
 
53
    }
 
54
 
 
55
    ~QPolygonClipper()
 
56
    {
 
57
    }
 
58
 
 
59
    void setBoundingRect(const QRect bounds)
 
60
    {
 
61
        x1 = bounds.x();
 
62
        x2 = bounds.x() + bounds.width();
 
63
        y1 = bounds.y();
 
64
        y2 = bounds.y() + bounds.height();
 
65
    }
 
66
 
 
67
    QRect boundingRect()
 
68
    {
 
69
        return QRect(QPoint(x1, y1), QPoint(x2, y2));
 
70
    }
 
71
 
 
72
    inline OutType intersectLeft(const OutType &p1, const OutType &p2)
 
73
    {
 
74
        OutType t;
 
75
        double dy = (p1.y - p2.y) / double(p1.x - p2.x);
 
76
        t.x = x1;
 
77
        t.y = static_cast<CastType>(p2.y + (x1 - p2.x) * dy);
 
78
        return t;
 
79
    }
 
80
 
 
81
 
 
82
    inline OutType intersectRight(const OutType &p1, const OutType &p2)
 
83
    {
 
84
        OutType t;
 
85
        double dy = (p1.y - p2.y) / double(p1.x - p2.x);
 
86
        t.x = x2;
 
87
        t.y = static_cast<CastType>(p2.y + (x2 - p2.x) * dy);
 
88
        return t;
 
89
    }
 
90
 
 
91
 
 
92
    inline OutType intersectTop(const OutType &p1, const OutType &p2)
 
93
    {
 
94
        OutType t;
 
95
        double dx = (p1.x - p2.x) / double(p1.y - p2.y);
 
96
        t.x = static_cast<CastType>(p2.x + (y1 - p2.y) * dx);
 
97
        t.y = y1;
 
98
        return t;
 
99
    }
 
100
 
 
101
 
 
102
    inline OutType intersectBottom(const OutType &p1, const OutType &p2)
 
103
    {
 
104
        OutType t;
 
105
        double dx = (p1.x - p2.x) / double(p1.y - p2.y);
 
106
        t.x = static_cast<CastType>(p2.x + (y2 - p2.y) * dx);
 
107
        t.y = y2;
 
108
        return t;
 
109
    }
 
110
 
 
111
 
 
112
    void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount,
 
113
                     bool closePolygon = true)
 
114
    {
 
115
        Q_ASSERT(outPoints);
 
116
        Q_ASSERT(outCount);
 
117
 
 
118
        if (inCount < 2) {
 
119
            *outCount = 0;
 
120
            return;
 
121
        }
 
122
 
 
123
        buffer1.reset();
 
124
        buffer2.reset();
 
125
 
 
126
        QDataBuffer<OutType> *source = &buffer1;
 
127
        QDataBuffer<OutType> *clipped = &buffer2;
 
128
 
 
129
        // Gather some info since we are iterating through the points anyway..
 
130
        bool doLeft = false, doRight = false, doTop = false, doBottom = false;
 
131
        OutType ot;
 
132
        for (int i=0; i<inCount; ++i) {
 
133
            ot = inPoints[i];
 
134
            clipped->add(ot);
 
135
 
 
136
            if (ot.x < x1)
 
137
                doLeft = true;
 
138
            else if (ot.x > x2)
 
139
                doRight = true;
 
140
            if (ot.y < y1)
 
141
                doTop = true;
 
142
            else if (ot.y > y2)
 
143
                doBottom = true;
 
144
        }
 
145
 
 
146
        if (doLeft && clipped->size() > 1) {
 
147
            QDataBuffer<OutType> *tmp = source;
 
148
            source = clipped;
 
149
            clipped = tmp;
 
150
            clipped->reset();
 
151
            int lastPos, start;
 
152
            if (closePolygon) {
 
153
                lastPos = source->size() - 1;
 
154
                start = 0;
 
155
            } else {
 
156
                lastPos = 0;
 
157
                start = 1;
 
158
                if (source->at(0).x >= x1)
 
159
                    clipped->add(source->at(0));
 
160
            }
 
161
            for (int i=start; i<inCount; ++i) {
 
162
                const OutType &cpt = source->at(i);
 
163
                const OutType &ppt = source->at(lastPos);
 
164
 
 
165
                if (cpt.x >= x1) {
 
166
                    if (ppt.x >= x1) {
 
167
                        clipped->add(cpt);
 
168
                    } else {
 
169
                        clipped->add(intersectLeft(cpt, ppt));
 
170
                        clipped->add(cpt);
 
171
                    }
 
172
                } else if (ppt.x >= x1) {
 
173
                    clipped->add(intersectLeft(cpt, ppt));
 
174
                }
 
175
                lastPos = i;
 
176
            }
 
177
        }
 
178
 
 
179
        if (doRight && clipped->size() > 1) {
 
180
            QDataBuffer<OutType> *tmp = source;
 
181
            source = clipped;
 
182
            clipped = tmp;
 
183
            clipped->reset();
 
184
            int lastPos, start;
 
185
            if (closePolygon) {
 
186
                lastPos = source->size() - 1;
 
187
                start = 0;
 
188
            } else {
 
189
                lastPos = 0;
 
190
                start = 1;
 
191
                if (source->at(0).x <= x2)
 
192
                    clipped->add(source->at(0));
 
193
            }
 
194
            for (int i=start; i<source->size(); ++i) {
 
195
                const OutType &cpt = source->at(i);
 
196
                const OutType &ppt = source->at(lastPos);
 
197
 
 
198
                if (cpt.x <= x2) {
 
199
                    if (ppt.x <= x2) {
 
200
                        clipped->add(cpt);
 
201
                    } else {
 
202
                        clipped->add(intersectRight(cpt, ppt));
 
203
                        clipped->add(cpt);
 
204
                    }
 
205
                } else if (ppt.x <= x2) {
 
206
                    clipped->add(intersectRight(cpt, ppt));
 
207
                }
 
208
 
 
209
                lastPos = i;
 
210
            }
 
211
 
 
212
        }
 
213
 
 
214
        if (doTop && clipped->size() > 1) {
 
215
            QDataBuffer<OutType> *tmp = source;
 
216
            source = clipped;
 
217
            clipped = tmp;
 
218
            clipped->reset();
 
219
            int lastPos, start;
 
220
            if (closePolygon) {
 
221
                lastPos = source->size() - 1;
 
222
                start = 0;
 
223
            } else {
 
224
                lastPos = 0;
 
225
                start = 1;
 
226
                if (source->at(0).y >= y1)
 
227
                    clipped->add(source->at(0));
 
228
            }
 
229
            for (int i=start; i<source->size(); ++i) {
 
230
                const OutType &cpt = source->at(i);
 
231
                const OutType &ppt = source->at(lastPos);
 
232
 
 
233
                if (cpt.y >= y1) {
 
234
                    if (ppt.y >= y1) {
 
235
                        clipped->add(cpt);
 
236
                    } else {
 
237
                        clipped->add(intersectTop(cpt, ppt));
 
238
                        clipped->add(cpt);
 
239
                    }
 
240
                } else if (ppt.y >= y1) {
 
241
                    clipped->add(intersectTop(cpt, ppt));
 
242
                }
 
243
 
 
244
                lastPos = i;
 
245
            }
 
246
        }
 
247
 
 
248
        if (doBottom && clipped->size() > 1) {
 
249
            QDataBuffer<OutType> *tmp = source;
 
250
            source = clipped;
 
251
            clipped = tmp;
 
252
            clipped->reset();
 
253
            int lastPos, start;
 
254
            if (closePolygon) {
 
255
                lastPos = source->size() - 1;
 
256
                start = 0;
 
257
            } else {
 
258
                lastPos = 0;
 
259
                start = 1;
 
260
                if (source->at(0).y <= y2)
 
261
                    clipped->add(source->at(0));
 
262
            }
 
263
            for (int i=start; i<source->size(); ++i) {
 
264
                const OutType &cpt = source->at(i);
 
265
                const OutType &ppt = source->at(lastPos);
 
266
 
 
267
                if (cpt.y <= y2) {
 
268
                    if (ppt.y <= y2) {
 
269
                        clipped->add(cpt);
 
270
                    } else {
 
271
                        clipped->add(intersectBottom(cpt, ppt));
 
272
                        clipped->add(cpt);
 
273
                    }
 
274
                } else if (ppt.y <= y2) {
 
275
                    clipped->add(intersectBottom(cpt, ppt));
 
276
                }
 
277
                lastPos = i;
 
278
            }
 
279
        }
 
280
 
 
281
        if (closePolygon && clipped->size() > 0) {
 
282
            // close clipped polygon
 
283
            if (clipped->at(0).x != clipped->at(clipped->size()-1).x ||
 
284
                clipped->at(0).y != clipped->at(clipped->size()-1).y)
 
285
                clipped->add(clipped->at(0));
 
286
        }
 
287
        *outCount = clipped->size();
 
288
        *outPoints = clipped->data();
 
289
    }
 
290
 
 
291
private:
 
292
    int x1, x2, y1, y2;
 
293
    QDataBuffer<OutType> buffer1;
 
294
    QDataBuffer<OutType> buffer2;
 
295
};
 
296
 
 
297
#endif // QPOLYGONCLIPPER_P_H