Polygon2D.cpp

Go to the documentation of this file.

// Polygon2D
//
//


#include <cmath>

#include "Polygon2D.hpp"

#include "Box2D.hpp"
#include "Circle2D.hpp"
#include "Ellipse2D.hpp"
#include "Line2D.hpp"
#include <iterator>
#include <sstream>
#include <stdexcept>    // for throw

namespace datatypes
{

// ////////////////////////////////////////////////////////////

Polygon2D::Polygon2D()
{
}

Polygon2D::Polygon2D(const Point2D& p1)
{
        push_back(p1);
}

Polygon2D::Polygon2D(const Point2D& p1, const Point2D& p2)
{
        push_back(p1);
        push_back(p2);
}
Polygon2D::Polygon2D(const Point2D& p1, const Point2D& p2, const Point2D& p3)
{
        push_back(p1);
        push_back(p2);
        push_back(p3);
}

Polygon2D::Polygon2D(const Point2D& p1, const Point2D& p2, const Point2D& p3, const Point2D& p4)
{
        push_back(p1);
        push_back(p2);
        push_back(p3);
        push_back(p4);
}

/*
Polygon2D::Polygon2D(const Line2D& p)
{
        push_back(p.getP1());
        push_back(p.getP2());
}
*/

Polygon2D::Polygon2D(const base_class& other_vector)
        : base_class(other_vector)
{
}

/*
Polygon2D::Polygon2D(const std::string& polygonAsString)
{
        fromString(polygonAsString);
}
*/

Polygon2D& Polygon2D::append (const Polygon2D& other )
{
        base_class::insert(base_class::end(), other.begin(), other.end());
        return *this;
}

Polygon2D& Polygon2D::append(const Point2D& point)
{
        push_back(point);
        return *this;
}

Polygon2D& Polygon2D::append(floatingpoint_type x, floatingpoint_type y)
{
        push_back(Point2D(x, y));
        return *this;
}

double Polygon2D::getArea() const
{
        if (empty())
                return 0.0;

        double result(0.0);
        for (size_type i = 0; i < size() - 1; ++i)
        {
                result += at(i).getX() * at(i + 1).getY() - at(i + 1).getX() * at(i).getY();
        }

        // Automatically close polygon. This won't harm, if polygon is already closed.
        result += at(size() - 1).getX() * at(0).getY() - at(0).getX() * at(size() - 1).getY();

        // Calculate absolute value in order to work with counter-clockwise polygon description.
        return std::abs(0.5 * result);
}

Point2D Polygon2D::getCenterOfGravity() const
{
        Point2D centerOfGravity;

        if (empty())
        {
                return centerOfGravity;
        }

        for (Polygon2D::const_iterator edgeIter = begin(); edgeIter != end(); ++edgeIter)
        {
                centerOfGravity += *edgeIter;
        }

        centerOfGravity /= size();

        return centerOfGravity;
}

bool Polygon2D::isClosed() const
{
        return !empty() && (front() == back());
}

//
// static functions
//

Polygon2D Polygon2D::fromCircle( const Point2D& center, const floatingpoint_type radius, const UINT32 samplingPoints )
{
        const Circle2D circle(center, radius);
        return fromEllipse(circle, samplingPoints);
}

Polygon2D Polygon2D::fromEllipse( const Point2D& center, const floatingpoint_type a, const floatingpoint_type b, const floatingpoint_type angle, const UINT32 samplingPoints )
{
        const Ellipse2D ellipse(center, Point2D(a, b), angle);
        return fromEllipse(ellipse, samplingPoints);
}

Polygon2D Polygon2D::fromEllipse(const Ellipse2D& ellipse, const UINT32 samplingPoints)
{
        Polygon2D result = fromArc(ellipse, 0, 2.0 * M_PI, samplingPoints);

        // Since we know the result should be a closed circle, we can
        // force the final point to be identical to the first one here.
        if (result.size() > 1)
                result.back() = result.front();

        return result;
}

Polygon2D Polygon2D::fromArc(const Ellipse2D& ellipse,
                                                         const floatingpoint_type startAngle, const floatingpoint_type endAngle,
                                                         const UINT32 samplingPoints, const bool clockwise)
{
        floatingpoint_type end = endAngle;

        // Modify the end angle so that we get the expected direction
        if (clockwise == true)
        {
                // clockwise direction (descending angle values from start to end)
                while (startAngle < end)
                {
                        end -= 2.0 * PI;
                }
        }
        else
        {
                // counter-clockwise direction (ascending angle values from start to end)
                while (end < startAngle)
                {
                        end += 2.0 * PI;
                }
        }

        return fromArc(ellipse, startAngle, end, samplingPoints);
}

Polygon2D Polygon2D::fromArc(const Ellipse2D& ellipse,
                                                         const floatingpoint_type startAngle, const floatingpoint_type endAngle,
                                                         const UINT32 samplingPoints)
{
        Polygon2D polygon;

        // Check if we have at least 2 sampling points
        if (samplingPoints < 2)
        {
                // Not enough points! Return an empty output.
                return polygon;
        }

        if (fabs(endAngle - startAngle) > double(2.0 * M_PI + 1e-3)) // allow 10^-3 epsilon
        {
                throw std::invalid_argument("Polygon2D::fromArc: Angle difference is too large! Is " + ::toString(fabs(endAngle - startAngle), 2) + " but must be at most 2*pi.");
        }

        const floatingpoint_type sinAngle(std::sin(ellipse.getRotation()));
        const floatingpoint_type cosAngle(std::cos(ellipse.getRotation()));
        const floatingpoint_type step = (endAngle - startAngle) / floatingpoint_type(samplingPoints - 1);

        floatingpoint_type t = startAngle;
        for (UINT32 p = 0 ; p < samplingPoints; p++)
        {
                // Last point? Then force the angle exactly on the endAngle
                if (p == (samplingPoints - 1))
                {
                        t = endAngle;
                }

                Point2D point;
                point.setX(ellipse.getRadius().getX() * std::cos(t) * cosAngle - ellipse.getRadius().getY() * std::sin(t) * sinAngle);
                point.setY(ellipse.getRadius().getX() * std::cos(t) * sinAngle + ellipse.getRadius().getY() * std::sin(t) * cosAngle);
                point += ellipse.getCenter();
                polygon.push_back(point);
                t += step;
        }

        return polygon;
}

const char* Polygon2D::getSeparatorCharacters()
{
        return "()[],; \t\"'";
}

Polygon2D Polygon2D::rhombus(const Point2D& center, const floatingpoint_type radius)
{
        Polygon2D contour;
        contour.push_back(Point2D(center.getX() - radius, center.getY()));
        contour.push_back(Point2D(center.getX(), center.getY() - radius));
        contour.push_back(Point2D(center.getX() + radius, center.getY()));
        contour.push_back(Point2D(center.getX(), center.getY() + radius));
        contour.push_back(Point2D(center.getX() - radius, center.getY()));

        return contour;
}

Polygon2D Polygon2D::createRectangle(const Point2D& lowerLeft, const Point2D& upperRight)
{
        return Polygon2D()
                   .append(lowerLeft)
                   .append(Point2D(lowerLeft.getX(), upperRight.getY()))
                   .append(upperRight)
                   .append(Point2D(upperRight.getX(), lowerLeft.getY()));
}

/*
void Polygon2D::fromString(const std::string& polyString)
{
        clear();

        typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
        tokenizer listOfTokens(polyString, boost::char_separator<char>(getSeparatorCharacters()));
        for (tokenizer::const_iterator iter = listOfTokens.begin();
                 iter != listOfTokens.end(); ++iter)
        {
                floatingpoint_type x = boost::lexical_cast<floatingpoint_type>(*iter);
                ++iter;
                if (iter == listOfTokens.end())
                        throw std::runtime_error("When parsing a Polygon2D string, the last point only has a x component.");
                floatingpoint_type y = boost::lexical_cast<floatingpoint_type>(*iter);
                this->push_back(Point2D(x, y));
        }
}
*/

Box2D Polygon2D::getBoundingBox() const
{
        if (empty())
        {
                return Box2D();
        }

        Polygon2D::const_iterator iter = begin();
        floatingpoint_type minX = iter->getX();
        floatingpoint_type minY = iter->getY();
        floatingpoint_type maxX = minX;
        floatingpoint_type maxY = minY;

        ++iter;
        for ( ; iter != end(); ++iter)
        {
                const floatingpoint_type x = iter->getX();
                const floatingpoint_type y = iter->getY();
                if (x < minX) minX = x;
                if (x > maxX) maxX = x;
                if (y < minY) minY = y;
                if (y > maxY) maxY = y;
        }
        return Box2D(0.5 * (maxX + minX),
                                 0.5 * (maxY + minY),
                                 maxX - minX,
                                 maxY - minY);
}

std::pair<Polygon2D::floatingpoint_type, Polygon2D::floatingpoint_type> Polygon2D::getBoundingAngles() const
{
        if (empty())
                return std::make_pair(0, 0);

        // Need to check whether the origin is inside the polygon. BUT: If
        // the origin is directly on the boundary, containsPoint() may or
        // may not return true. For this reason we must watch out for the
        // case of points on the negative x axis below (if this test
        // returned false here).
        if (containsPoint(Point2D(0, 0)))
        {
                // Origin is inside. Then return the full interval.
                return std::make_pair(-PI, PI);
        }

        // The usual case: The polygon does not contain the origin. Then we
        // look for the min and max angles of the edges.

        Polygon2D::const_iterator iter = begin();
        floatingpoint_type minangle = iter->angle();
        floatingpoint_type maxangle = minangle;

        bool gotPointOnNegativeX = false;
        for ( ; iter != end(); ++iter)
        {
                if (fuzzyCompare(iter->getY(), 0.0)
                        && (iter->getX() < 0.0))
                {
                        // Special case for points on the negative x axis: We do
                        // not know (yet) whether we should record this as +pi or
                        // -pi. We will decide on this afterwards.
                        gotPointOnNegativeX = true;
                }
                else
                {
                        const floatingpoint_type pointangle = iter->angle();

                        if (pointangle < minangle)
                                minangle = pointangle;

                        if (pointangle > maxangle)
                                maxangle = pointangle;
                }
        }

        // Did we also have at least one point on the negative X axis?
        // Either add this as -pi or +pi, or set both angles to -pi/pi
        // because we are not sure.
        if (gotPointOnNegativeX)
        {
                if (std::max(minangle, maxangle) <= 0.0f)
                        minangle = -M_PI;
                else if (std::min(minangle, maxangle) >= 0.0f)
                        maxangle = M_PI;
                else
                {
                        minangle = -M_PI;
                        maxangle = M_PI;
                }
        }

        return std::make_pair(minangle, maxangle);
}

bool Polygon2D::containsPoint(const Point2D& point) const
{
        // Point-in-polygon test using ray-casting algorithm
        //
        // C-Code was borrowed from:
        // http://www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html
        //
        // Be careful: Don't fiddle with the code below unless you know
        // exactly what you're doing!
        //
        // Algorithm: From the test point a semi-finite ray is run through
        // the polygon. While doing so the number of edge crossings are
        // counted. If the number of crossings is even, the test point is
        // located outside of the polygon. If the number is odd, the point
        // is inside. (Jordan curve theorem)
        //
        // Also see: http://en.wikipedia.org/wiki/Point_in_polygon

        if (empty())
        {
                return false;
        }

        bool isInside(false);
        const Polygon2D& p = *this; // alias for shorter writing

        UINT32 i = 0;
        UINT32 j = (UINT32)(size() - 1);
        for (i = 0; i < size(); j = i++)
        {
                if (
                        ( (p[i].getY() > point.getY()) != (p[j].getY() > point.getY()) )
                        &&
                        ( point.getX() < ( (p[j].getX() - p[i].getX())
                                                           * (point.getY() - p[i].getY())
                                                           / (p[j].getY() - p[i].getY())
                                                           + p[i].getX() ) )
                )
                {
                        isInside = !isInside;
                }
        }

        return isInside;
}

void projectOntoAxis(const Point2D& axis, const Polygon2D& polygon,
                                         Polygon2D::floatingpoint_type& min, Polygon2D::floatingpoint_type& max)
{
        min = max = (axis * polygon[0]);

        for (Polygon2D::const_iterator edge = polygon.begin(); edge != polygon.end(); ++edge)
        {
                const Polygon2D::floatingpoint_type dotProduct(axis * (*edge));
                min = std::min(min, dotProduct);
                max = std::max(max, dotProduct);
        }
}

Polygon2D::floatingpoint_type intervalDistance(const Polygon2D::floatingpoint_type minA, const Polygon2D::floatingpoint_type maxA,
                const Polygon2D::floatingpoint_type minB, const Polygon2D::floatingpoint_type maxB)
{
        if (minA < minB)
        {
                return minB - maxA;
        }
        else
        {
                return minA - maxB;
        }
}

bool Polygon2D::isColliding(const Polygon2D& p2) const
{
        Polygon2D both(*this);
        both.reserve(both.size() + p2.size());
        both.insert(both.end(), p2.begin(), p2.end());

        for (Polygon2D::const_iterator edge = both.begin(); edge != both.end(); ++edge)
        {
                Point2D axis(-edge->getY(), edge->getX());
                axis.normalize();

                floatingpoint_type minA, minB, maxA, maxB;
                projectOntoAxis(axis, *this, minA, maxA);
                projectOntoAxis(axis, p2, minB, maxB);

                if (intervalDistance(minA, maxA, minB, maxB) > 0)
                {
                        return false;
                }
        }

        return true;
}


Polygon2D::base_class Polygon2D::isIntersecting(const Line2D& other) const
{
        base_class result;
        if (size() < 2 || other.isZero())
        {
                return result;
        }
        for (size_t k = 1; k < size(); ++k)
        {
                Point2D isect;
                Line2D currentline(operator[](k - 1), operator[](k));
                if (currentline.isIntersecting(other, &isect)
                        == Line2D::LineIntersecting)
                        result.push_back(isect);
        }
        return result;
}

Point2D::value_type Polygon2D::distanceToPoint(const Point2D& point) const
{
        if (size() < 2)
                return empty() ? 0 : point.dist(front());

        assert(size() >= 2);
        Point2D::value_type result = point.dist(front());
        for (size_t k = 1; k < size(); ++k)
        {
                Line2D line(operator[](k - 1), operator[](k));
                Point2D::value_type dist = line.distanceFromLineSegment(point);
                if (dist < result)
                        result = dist;
        }
        return result;
}

Polygon2D Polygon2D::getSimplified() const
{
        if (size() < 3)
                return *this;
        Polygon2D result;
        result.reserve(size());

        // First point is always in the result
        result.push_back(front());

        for (size_type k = 1; k < size() - 1; ++k)
        {
                const Point2D& previous = result.back();
                const Point2D& current = operator[](k);
                const Point2D& next = operator[](k + 1);
                Line2D line(previous, next);
                // Only add the current point to the result if it doesn't lie
                // directly on the connection line between the previous output
                // point and the next one.
                if (!line.containsPoint(current))
                        result.push_back(current);
        }

        // Last point is always in the result
        result.push_back(back());

        return result;
}

// ////////////////////////////////////////////////////////////


std::string Polygon2D::toString() const
{
        std::string text = "[ ";
        if (empty() == false)
        {
                for (size_type k = 0; k < size(); k++)
                {
                        const Point2D& current = operator[](k);
                        text += current.toString() + " ";
                }
        }
        text += "]";
        return text;
}

}       // namespace datatypes