kwqregion.cpp

手机浏览器源码程序,功能强大

/*
 * Copyright (C) 2003 Apple Computer, Inc.  All rights reserved.
 * Portions Copyright (c) 2005 Nokia Corporation, Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIQRect, INDIQRect, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "KWQRegion.h"

#include <limits.h>


/*
The following code is based on an algorithm presented in "Algorithms" by Robert Sedgewick,
Addison-Wesley, 1988, 2nd ed. ISBN 0201066734 */

bool pointInPolygon(QPointArray rgpts, QPoint ptTest) ;

bool pointInPolyRect(QPointArray rgpts, QPoint ptTest,

                QRect *prbound) ;

bool intersects(QPoint p1, QPoint p2, QPoint p3, QPoint p4) ;

int  CCW(QPoint p0, QPoint p1, QPoint p2) ;

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

* FUNCTION:   pointInPolygon
*
* PURPOSE
* This routine determines if the point passed is in the polygon. It uses

* the classical polygon hit-testing algorithm: a horizontal ray starting

* at the point is extended infinitely rightwards and the number of
* polygon edges that intersect the ray are counted. If the number is odd,

* the point is inside the polygon.
*
* RETURN VALUE
* (bool) TRUE if the point is inside the polygon, FALSE if not.
*************************************************************************/

bool pointInPolygon(QPointArray rgpts, QPoint ptTest)

{
    int wnumpts = rgpts.count();
    if (!wnumpts)
        return false;
    QRect r;
    int   i ;
    QPoint  pt1, pt2 ;
    int   wnumintsct = 0 ;

    if (!pointInPolyRect(rgpts,ptTest,&r))
        return FALSE ;

    pt1 = ptTest ;
    pt2 = QPoint(r.right() + 50, ptTest.y()) ;

    // Now go through each of the lines in the polygon and see if it
    // intersects
    for (i = 0 ; i < wnumpts-1 ; i++) {
        if (intersects(pt1, pt2, rgpts[i], rgpts[i+1]))
            wnumintsct++ ;
    }

    // And the last line
    if (intersects(pt1, pt2, rgpts[wnumpts-1], rgpts[0]))
        wnumintsct++ ;

    return (wnumintsct&1) ;
}

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

* FUNCTION:   pointInPolyRect
*
* PURPOSE
* This routine determines if a point is within the smallest rectangle
* that encloses a polygon.
*
* RETURN VALUE
* (bool) TRUE or FALSE depending on whether the point is in the rect or

* not.
*************************************************************************/

bool  pointInPolyRect(QPointArray rgpts, QPoint ptTest,

                 QRect *res)

{
    int wnumpts = rgpts.count();
    if (!wnumpts)
        return false;

    QRect r ;
    int   xmin, xmax, ymin, ymax ;
    QPoint *ppt ;
    int  i ;

    xmin = ymin = INT_MAX ;
    xmax = ymax = -INT_MAX ;

    for (i=0; i < wnumpts ; i++) {
        ppt = &rgpts[i];
        if (ppt->x() < xmin)
           xmin = ppt->x() ;
        if (ppt->x() > xmax)
           xmax = ppt->x() ;
        if (ppt->y() < ymin)
           ymin = ppt->y() ;
        if (ppt->y() > ymax)
           ymax = ppt->y() ;
    }
    r = QRect(xmin, ymin, xmax-xmin, ymax-ymin);

    if (res)
        *res = r;

    return r.contains(ptTest.x(),ptTest.y());
}

/*************************************************************************
* FUNCTION:   intersects
*
* PURPOSE
* Given two line segments, determine if they intersect.
*
* RETURN VALUE
* TRUE if they intersect, FALSE if not.
*************************************************************************/

bool intersects(QPoint p1, QPoint p2, QPoint p3, QPoint p4)
{
    return ((( CCW(p1, p2, p3) * CCW(p1, p2, p4)) <= 0)
        && (( CCW(p3, p4, p1) * CCW(p3, p4, p2)  <= 0) )) ;
}

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

* FUNCTION:   CCW (CounterClockWise)
*
* PURPOSE
* Determines, given three points, if when travelling from the first to
* the second to the third, we travel in a counterclockwise direction.
*
* RETURN VALUE
* (int) 1 if the movement is in a counterclockwise direction, -1 if
* not.
*************************************************************************/

int CCW(QPoint p0, QPoint p1, QPoint p2)

{
    int dx1, dx2 ;
    int dy1, dy2 ;

    dx1 = p1.x() - p0.x() ; dx2 = p2.x() - p0.x() ;
    dy1 = p1.y() - p0.y() ; dy2 = p2.y() - p0.y() ;

    /* This is basically a slope comparison: we don't do divisions because

    * of divide by zero possibilities with pure horizontal and pure
    * vertical lines.
    */
    return ((dx1 * dy2 > dy1 * dx2) ? 1 : -1) ;
}


QRegion::QRegion(const QRect &rect)
{
    r=rect;
    regionType=Rectangle;
}

QRegion::QRegion(int x, int y, int w, int h, RegionType t)
{
    r = QRect(x,y,w,h);
    regionType = t;
}

QRegion::QRegion(const QPointArray &arr)
{
    regionType = Polygon;
    points = arr;
}

QRegion::~QRegion()
{
}

QRegion::QRegion(const QRegion &other)
{
    r=other.r;
    regionType=other.regionType;
    points = other.points;
}

QRegion &QRegion::operator=(const QRegion &other)
{
    if (&other == this)
	    return *this;
    r=other.r;
    regionType=other.regionType;
    points = other.points;
    return *this;
}

bool QRegion::contains(const QPoint &point) const
{
    if (regionType == Rectangle)
	    return const_cast<QRegion*>(this)->r.contains(point.x(),point.y());
    else if (regionType == Polygon) {
        return pointInPolygon(points,point);
    } else {
        /**
          in order for point(x,y) to stay in the ellipse,
          it has to fulfill the ellipse equation:
          sqr(dx)/sqr(a) + sqr(dy)/sqr(b) <= 1
          where 'a' is half the long axis of the ellipse, and 'b' is half the short axis
          x = a * cos(t) and y = b * sin(t)
          (see "http://www.3dsoftware.com/Math/PlaneCurves/EllipseAlgebra" for details)
        **/

        int r2x = (r.width() * r.width()) / 4;      // sqr(a)
        int r2y = (r.height() * r.height()) / 4;    // sqr(b)

        if (!r2x || !r2y)  /*avoid division by zero*/
            return false;

        int cx = (r.x() + r.width()/2);             // center of ellipse, x
        int cy = (r.y() + r.height()/2);            // center of ellipse, y
        int dx = point.x() - cx;                    // dx
        int dy = point.y() - cy;                    // dy
        return (dx*dx*r2y + dy*dy*r2x <= r2x*r2y);
    }

}



void QRegion::translate(int deltaX, int deltaY)
{
    if (regionType == Polygon) {
        for (int i = 0 ; i < points.count() ; i++) {
            points[i] = QPoint(points[i].x()+deltaX,points[i].y()+deltaY);
        }
    } else {
        r.setX(r.x()+deltaX);
        r.setY(r.y()+deltaY);
    }
}

QRect QRegion::boundingRect() const
{
    if (regionType == Polygon)
        {
        QRect res;
        pointInPolyRect(points,QPoint(),&res);
        return res;
        }
    else
        return r;
}