/****************************************************************************

**

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtGui module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#ifndef QPOLYGONCLIPPER_P_H

#define QPOLYGONCLIPPER_P_H

//

//  W A R N I N G

//  -------------

//

// This file is not part of the Qt API.  It exists for the convenience

// of other Qt classes.  This header file may change from version to

// version without notice, or even be removed.

//

// We mean it.

//

#include "private/qdatabuffer_p.h"

QT_BEGIN_NAMESPACE

/* based on sutherland-hodgman line-by-line clipping, as described in

   Computer Graphics and Principles */

template <typename InType, typename OutType, typename CastType> class QPolygonClipper

{

public:

    QPolygonClipper()

    {

        x1 = y1 = x2 = y2 = 0;

    }

    ~QPolygonClipper()

    {

    }

    void setBoundingRect(const QRect bounds)

    {

        x1 = bounds.x();

        x2 = bounds.x() + bounds.width();

        y1 = bounds.y();

        y2 = bounds.y() + bounds.height();

    }

    QRect boundingRect()

    {

        return QRect(QPoint(x1, y1), QPoint(x2, y2));

    }

    inline OutType intersectLeft(const OutType &p1, const OutType &p2)

    {

        OutType t;

        qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x);

        t.x = x1;

        t.y = static_cast<CastType>(p2.y + (x1 - p2.x) * dy);

        return t;

    }

    inline OutType intersectRight(const OutType &p1, const OutType &p2)

    {

        OutType t;

        qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x);

        t.x = x2;

        t.y = static_cast<CastType>(p2.y + (x2 - p2.x) * dy);

        return t;

    }

    inline OutType intersectTop(const OutType &p1, const OutType &p2)

    {

        OutType t;

        qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y);

        t.x = static_cast<CastType>(p2.x + (y1 - p2.y) * dx);

        t.y = y1;

        return t;

    }

    inline OutType intersectBottom(const OutType &p1, const OutType &p2)

    {

        OutType t;

        qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y);

        t.x = static_cast<CastType>(p2.x + (y2 - p2.y) * dx);

        t.y = y2;

        return t;

    }

    void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount,

                     bool closePolygon = true)

    {

        Q_ASSERT(outPoints);

        Q_ASSERT(outCount);

        if (inCount < 2) {

            *outCount = 0;

            return;

        }

        buffer1.reset();

        buffer2.reset();

        QDataBuffer<OutType> *source = &buffer1;

        QDataBuffer<OutType> *clipped = &buffer2;

        // Gather some info since we are iterating through the points anyway..

        bool doLeft = false, doRight = false, doTop = false, doBottom = false;

        OutType ot;

        for (int i=0; i<inCount; ++i) {

            ot = inPoints[i];

            clipped->add(ot);

            if (ot.x < x1)

                doLeft = true;

            else if (ot.x > x2)

                doRight = true;

            if (ot.y < y1)

                doTop = true;

            else if (ot.y > y2)

                doBottom = true;

        }

        if (doLeft && clipped->size() > 1) {

            QDataBuffer<OutType> *tmp = source;

            source = clipped;

            clipped = tmp;

            clipped->reset();

            int lastPos, start;

            if (closePolygon) {

                lastPos = source->size() - 1;

                start = 0;

            } else {

                lastPos = 0;

                start = 1;

                if (source->at(0).x >= x1)

                    clipped->add(source->at(0));

            }

            for (int i=start; i<inCount; ++i) {

                const OutType &cpt = source->at(i);

                const OutType &ppt = source->at(lastPos);

                if (cpt.x >= x1) {

                    if (ppt.x >= x1) {

                        clipped->add(cpt);

                    } else {

                        clipped->add(intersectLeft(cpt, ppt));

                        clipped->add(cpt);

                    }

                } else if (ppt.x >= x1) {

                    clipped->add(intersectLeft(cpt, ppt));

                }

                lastPos = i;

            }

        }

        if (doRight && clipped->size() > 1) {

            QDataBuffer<OutType> *tmp = source;

            source = clipped;

            clipped = tmp;

            clipped->reset();

            int lastPos, start;

            if (closePolygon) {

                lastPos = source->size() - 1;

                start = 0;

            } else {

                lastPos = 0;

                start = 1;

                if (source->at(0).x <= x2)

                    clipped->add(source->at(0));

            }

            for (int i=start; i<source->size(); ++i) {

                const OutType &cpt = source->at(i);

                const OutType &ppt = source->at(lastPos);

                if (cpt.x <= x2) {

                    if (ppt.x <= x2) {

                        clipped->add(cpt);

                    } else {

                        clipped->add(intersectRight(cpt, ppt));

                        clipped->add(cpt);

                    }

                } else if (ppt.x <= x2) {

                    clipped->add(intersectRight(cpt, ppt));

                }

                lastPos = i;

            }

        }

        if (doTop && clipped->size() > 1) {

            QDataBuffer<OutType> *tmp = source;

            source = clipped;

            clipped = tmp;

            clipped->reset();

            int lastPos, start;

            if (closePolygon) {

                lastPos = source->size() - 1;

                start = 0;

            } else {

                lastPos = 0;

                start = 1;

                if (source->at(0).y >= y1)

                    clipped->add(source->at(0));

            }

            for (int i=start; i<source->size(); ++i) {

                const OutType &cpt = source->at(i);

                const OutType &ppt = source->at(lastPos);

                if (cpt.y >= y1) {

                    if (ppt.y >= y1) {

                        clipped->add(cpt);

                    } else {

                        clipped->add(intersectTop(cpt, ppt));

                        clipped->add(cpt);

                    }

                } else if (ppt.y >= y1) {

                    clipped->add(intersectTop(cpt, ppt));

                }

                lastPos = i;

            }

        }

        if (doBottom && clipped->size() > 1) {

            QDataBuffer<OutType> *tmp = source;

            source = clipped;

            clipped = tmp;

            clipped->reset();

            int lastPos, start;

            if (closePolygon) {

                lastPos = source->size() - 1;

                start = 0;

            } else {

                lastPos = 0;

                start = 1;

                if (source->at(0).y <= y2)

                    clipped->add(source->at(0));

            }

            for (int i=start; i<source->size(); ++i) {

                const OutType &cpt = source->at(i);

                const OutType &ppt = source->at(lastPos);

                if (cpt.y <= y2) {

                    if (ppt.y <= y2) {

                        clipped->add(cpt);

                    } else {

                        clipped->add(intersectBottom(cpt, ppt));

                        clipped->add(cpt);

                    }

                } else if (ppt.y <= y2) {

                    clipped->add(intersectBottom(cpt, ppt));

                }

                lastPos = i;

            }

        }

        if (closePolygon && clipped->size() > 0) {

            // close clipped polygon

            if (clipped->at(0).x != clipped->at(clipped->size()-1).x ||

                clipped->at(0).y != clipped->at(clipped->size()-1).y) {

                OutType ot = clipped->at(0);

                clipped->add(ot);

            }

        }

        *outCount = clipped->size();

        *outPoints = clipped->data();

    }

private:

    int x1, x2, y1, y2;

    QDataBuffer<OutType> buffer1;

    QDataBuffer<OutType> buffer2;

};

QT_END_NAMESPACE

#endif // QPOLYGONCLIPPER_P_H