src/libavoid/geomtypes.cpp

e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan/*
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * vim: ts=4 sw=4 et tw=0 wm=0
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * libavoid - Fast, Incremental, Object-avoiding Line Router
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Copyright (C) 2004-2009  Monash University
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * This library is free software; you can redistribute it and/or
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * modify it under the terms of the GNU Lesser General Public
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * License as published by the Free Software Foundation; either
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * version 2.1 of the License, or (at your option) any later version.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * See the file LICENSE.LGPL distributed with the library.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Licensees holding a valid commercial license may use this file in
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * accordance with the commercial license agreement provided with the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * library.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * This library is distributed in the hope that it will be useful,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * but WITHOUT ANY WARRANTY; without even the implied warranty of
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan *
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan * Author(s):   Michael Wybrow <mjwybrow@users.sourceforge.net>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan*/
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include <cmath>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include <cfloat>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include <cstdlib>
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include "libavoid/geomtypes.h"
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include "libavoid/shape.h"
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include "libavoid/router.h"
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#include "libavoid/assertions.h"
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracannamespace Avoid
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPoint::Point() :
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    id(0),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    vn(kUnassignedVertexNumber)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPoint::Point(const double xv, const double yv) :
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    x(xv),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    y(yv),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    id(0),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    vn(kUnassignedVertexNumber)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Point::operator==(const Point& rhs) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if ((x == rhs.x) && (y == rhs.y))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return false;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Point::operator!=(const Point& rhs) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if ((x != rhs.x) || (y != rhs.y))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return true;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return false;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// Just defined to allow std::set<Point>.  Not particularly meaningful!
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Point::operator<(const Point& rhs) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (x == rhs.x)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return (y < rhs.y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return (x < rhs.x);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracandouble& Point::operator[](const unsigned int dimension)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT((dimension == 0) || (dimension == 1));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ((dimension == 0) ? x : y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanconst double& Point::operator[](const unsigned int dimension) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT((dimension == 0) || (dimension == 1));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ((dimension == 0) ? x : y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanReferencingPolygon::ReferencingPolygon(const Polygon& poly, const Router *router)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : PolygonInterface(),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan      _id(poly._id),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan      ps(poly.size())
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT(router != NULL);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t i = 0; i < poly.size(); ++i)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        const Polygon *polyPtr = NULL;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        for (ShapeRefList::const_iterator sh = router->shapeRefs.begin();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                sh != router->shapeRefs.end(); ++sh)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            if ((*sh)->id() == poly.ps[i].id)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                const Polygon& poly = (*sh)->polygon();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                polyPtr = &poly;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                break;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        COLA_ASSERT(polyPtr != NULL);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        ps[i] = std::make_pair(polyPtr, poly.ps[i].vn);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanReferencingPolygon::ReferencingPolygon()
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : PolygonInterface()
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    clear();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid ReferencingPolygon::clear(void)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps.clear();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool ReferencingPolygon::empty(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ps.empty();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracansize_t ReferencingPolygon::size(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ps.size();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanint ReferencingPolygon::id(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return _id;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanconst Point& ReferencingPolygon::at(size_t index) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT(index < size());
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    const Polygon& poly = *(ps[index].first);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    unsigned short poly_index = ps[index].second;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT(poly_index < poly.size());
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return poly.ps[poly_index];
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid PolygonInterface::getBoundingRect(double *minX, double *minY,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double *maxX, double *maxY) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double progressiveMinX = DBL_MAX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double progressiveMinY = DBL_MAX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double progressiveMaxX = -DBL_MAX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double progressiveMaxY = -DBL_MAX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t i = 0; i < size(); ++i)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        progressiveMinX = std::min(progressiveMinX, at(i).x);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        progressiveMinY = std::min(progressiveMinY, at(i).y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        progressiveMaxX = std::max(progressiveMaxX, at(i).x);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        progressiveMaxY = std::max(progressiveMaxY, at(i).y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (minX)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        *minX = progressiveMinX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (maxX)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        *maxX = progressiveMaxX;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (minY)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        *minY = progressiveMinY;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (maxY)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        *maxY = progressiveMaxY;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPolygon::Polygon()
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : PolygonInterface()
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    clear();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPolygon::Polygon(const int pn)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : PolygonInterface(),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan      ps(pn)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPolygon::Polygon(const PolygonInterface& poly)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : PolygonInterface(),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan      _id(poly.id()),
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan      ps(poly.size())
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t i = 0; i < poly.size(); ++i)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        ps[i] = poly.at(i);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Polygon::clear(void)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps.clear();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ts.clear();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanbool Polygon::empty(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ps.empty();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracansize_t Polygon::size(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ps.size();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanint Polygon::id(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return _id;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanconst Point& Polygon::at(size_t index) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    COLA_ASSERT(index < size());
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return ps[index];
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const unsigned int SHORTEN_NONE  = 0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const unsigned int SHORTEN_START = 1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const unsigned int SHORTEN_END   = 2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic const unsigned int SHORTEN_BOTH  = SHORTEN_START | SHORTEN_END;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// shorten_line():
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     Given the two endpoints of a line segment, this function adjusts the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     endpoints of the line to shorten the line by shorten_length at either
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     or both ends.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanstatic void shorten_line(double& x1, double& y1, double& x2, double& y2,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        const unsigned int mode, const double shorten_length)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (mode == SHORTEN_NONE)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double rise = y1 - y2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double run = x1 - x2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double disty = fabs(rise);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double distx = fabs(run);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    // Handle case where shorten length is greater than the length of the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    // line segment.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if ((mode == SHORTEN_BOTH) &&
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            (((distx > disty) && ((shorten_length * 2) > distx)) ||
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan             ((disty >= distx) && ((shorten_length * 2) > disty))))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        x1 = x2 = x1 - (run / 2);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        y1 = y2 = y1 - (rise / 2);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    else if ((mode == SHORTEN_START) &&
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            (((distx > disty) && (shorten_length > distx)) ||
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan             ((disty >= distx) && (shorten_length > disty))))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        x1 = x2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        y1 = y2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    else if ((mode == SHORTEN_END) &&
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            (((distx > disty) && (shorten_length > distx)) ||
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan             ((disty >= distx) && (shorten_length > disty))))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        x2 = x1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        y2 = y1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    // Handle orthogonal line segments.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (x1 == x2)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        // Vertical
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        int sign = (y1 < y2) ? 1: -1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (mode & SHORTEN_START)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y1 += (sign * shorten_length);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (mode & SHORTEN_END)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y2 -= (sign * shorten_length);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    else if (y1 == y2)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        // Horizontal
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        int sign = (x1 < x2) ? 1: -1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (mode & SHORTEN_START)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x1 += (sign * shorten_length);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (mode & SHORTEN_END)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x2 -= (sign * shorten_length);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    int xpos = (x1 < x2) ? -1 : 1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    int ypos = (y1 < y2) ? -1 : 1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double tangent = rise / run;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (mode & SHORTEN_END)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (disty > distx)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y2 += shorten_length * ypos;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x2 += shorten_length * ypos * (1 / tangent);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        else if (disty < distx)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y2 += shorten_length * xpos * tangent;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x2 += shorten_length * xpos;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (mode & SHORTEN_START)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (disty > distx)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y1 -= shorten_length * ypos;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x1 -= shorten_length * ypos * (1 / tangent);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        else if (disty < distx)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            y1 -= shorten_length * xpos * tangent;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            x1 -= shorten_length * xpos;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracanvoid Polygon::translate(const double xDist, const double yDist)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t i = 0; i < size(); ++i)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        ps[i].x += xDist;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        ps[i].y += yDist;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPolygon Polygon::simplify(void) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    Polygon simplified = *this;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    std::vector<Point>::iterator it = simplified.ps.begin();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (it != simplified.ps.end()) ++it;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    // Combine collinear line segments into single segments:
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t j = 2; j < simplified.size(); )
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (vecDir(simplified.ps[j - 2], simplified.ps[j - 1],
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                simplified.ps[j]) == 0)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            // These three points make up two collinear segments, so just
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            // compine them into a single segment.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            it = simplified.ps.erase(it);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        else
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            ++j;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            ++it;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return simplified;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan#define mid(a, b) ((a < b) ? a + ((b - a) / 2) : b + ((a - b) / 2))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan// curvedPolyline():
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     Returns a curved approximation of this multi-segment PolyLine, with
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     the corners replaced by smooth Bezier curves.  curve_amount describes
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     how large to make the curves.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     The ts value for each point in the returned Polygon describes the
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     drawing operation: 'M' (move) marks the first point, a line segment
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     is marked with an 'L' and three 'C's (along with the previous point)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//     describe the control points of a Bezier curve.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan//
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanPolygon Polygon::curvedPolyline(const double curve_amount,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        const bool closed) const
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    Polygon simplified = this->simplify();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    Polygon curved;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    size_t num_of_points = size();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (num_of_points <= 2)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        // There is only a single segment, do nothing.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved = *this;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ts.push_back('M');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ts.push_back('L');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        return curved;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    // Build the curved polyline:
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    curved._id = _id;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double last_x = 0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double last_y = 0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    if (closed)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double x1 = simplified.ps[0].x;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double y1 = simplified.ps[0].y;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double x2 = simplified.ps[1].x;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double y2 = simplified.ps[1].y;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        shorten_line(x1, y1, x2, y2, SHORTEN_START, curve_amount);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ps.push_back(Point(x1, y1));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ts.push_back('M');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    else
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ps.push_back(ps[0]);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ts.push_back('M');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    size_t simpSize = simplified.size();
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    size_t finish = (closed) ? simpSize + 2 : simpSize;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    for (size_t j = 1; j < finish; ++j)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double x1 = simplified.ps[(simpSize + j - 1) % simpSize].x;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double y1 = simplified.ps[(simpSize + j - 1) % simpSize].y;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double x2 = simplified.ps[j % simpSize].x;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double y2 = simplified.ps[j % simpSize].y;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double old_x = x1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        double old_y = y1;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        unsigned int mode = SHORTEN_BOTH;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (!closed)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            if (j == 1)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                mode = SHORTEN_END;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            else if (j == (size() - 1))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan                mode = SHORTEN_START;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        shorten_line(x1, y1, x2, y2, mode, curve_amount);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (j > 1)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ts.insert(curved.ts.end(), 3, 'C');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ps.push_back(Point(mid(last_x, old_x), mid(last_y, old_y)));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ps.push_back(Point(mid(x1, old_x), mid(y1, old_y)));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ps.push_back(Point(x1, y1));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        if (closed && (j == (finish - 1)))
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        {
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            // Close the path.
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ts.push_back('Z');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            curved.ps.push_back(Point(x1, y1));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan            break;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ts.push_back('L');
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        curved.ps.push_back(Point(x2, y2));
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        last_x = x2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        last_y = y2;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    }
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    return curved;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanRectangle::Rectangle(const Point& topLeft, const Point& bottomRight)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    : Polygon(4)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double xMin = std::min(topLeft.x, bottomRight.x);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double xMax = std::max(topLeft.x, bottomRight.x);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double yMin = std::min(topLeft.y, bottomRight.y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double yMax = std::max(topLeft.y, bottomRight.y);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[0] = Point(xMax, yMin);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[1] = Point(xMax, yMax);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[2] = Point(xMin, yMax);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[3] = Point(xMin, yMin);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. CracanRectangle::Rectangle(const Point& centre, const double width,
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan        const double height)
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan{
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double halfWidth  = width / 2.0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double halfHeight = height / 2.0;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double xMin = centre.x - halfWidth;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double xMax = centre.x + halfWidth;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double yMin = centre.y - halfHeight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    double yMax = centre.y + halfHeight;
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[0] = Point(xMax, yMin);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[1] = Point(xMax, yMax);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[2] = Point(xMin, yMax);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan    ps[3] = Point(xMin, yMin);
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan}
e1f6e2d90070eb6836dc90c06147883de877f608Arcadie M. Cracan