freespace.h

Go to the documentation of this file.

#ifndef FREESPACE_H
#define FREESPACE_H

#include <types.h>
#include <interval.h>
#include <components.h>
#include <array2d.h>
#include <numeric.h>

#include <QLineF>

#include <cmath>

#include <boost/smart_ptr.hpp>

namespace frechet { namespace fs {
class Cell {
public:
    data::Interval L,B;

public:

    data::IntervalPair bounds;

public:
    /*
     * Free-Space segments of a cell
     * */
    double&     a()         { return L.lower(); }
    double&     b()         { return L.upper(); }
    double&     c()         { return B.lower(); }
    double&     d()         { return B.upper(); }

    double      a() const   { return L.lower(); }
    double      b() const   { return L.upper(); }
    double      c() const   { return B.lower(); }
    double      d() const   { return B.upper(); }

    const data::Interval& LB(bool l) { return l ? L:B; }
};

//  TODO type_traits: Interval, IntervalPair, and Cell are trivially-copyable

class FreeSpace {

public:
    const Curve &P; 
    const Curve &Q; 
    const int n; 
    const int m; 

    typedef boost::shared_ptr<FreeSpace> ptr;

    static const QRectF UNIT_RECT;
    static const double DET_MINIMUM;
private:

    data::Array2D<Cell> cells;
    Components _components;

public:
    FreeSpace(const Curve& ap, const Curve& aq);
    FreeSpace(const FreeSpace& that);

    Components& components() { return _components; }

    size_t component(int i, int j)
    {
        if (cellEmptyBounds(i,j))
            return Components::NO_COMPONENT;
        else
            return _components.representative(i,j);
    }
    void calculateFreeSpace(double epsilon);
    void calculateBounds(double epsilon);

    /*
     *  Free-Space Cells
     * */
    Cell& cell(int x, int y) {
        Q_ASSERT(x>=0 && x < n);
        Q_ASSERT(y>=0 && y < m);
        return cells.at(x,y);
    }
    const Cell& cell(int x, int y) const {
        Q_ASSERT(x>=0 && x < n);
        Q_ASSERT(y>=0 && y < m);
        return cells.at(x,y);
    }
    bool cellEmptyIntervals(int i, int j) const;
    bool cellEmptyBounds(int i, int j) const;

    bool cellFull(int i, int j) const;

    bool isParallel(int i, int j) const {
        return determinant(i,j) == 0.0;
    }

    bool isAlmostParallel(int i, int j) const {
        return abs(determinant(i,j)) < DET_MINIMUM;
    }

    bool wrapRight() const { return P.isClosed(); }
    bool wrapTop() const { return Q.isClosed(); }

    QRectF segmentBounds(int i, int j);

    std::list<data::Interval> collectFreeVerticalIntervals(int i) const;

public:
    //void calculateGridOffsets();
    template<typename Float>
    static void calculateFreeSpaceSegment(const Point& p, const Point& q, const Point& r,
                                   double epsilon,
                                   data::Interval& result);
    static void fixBorderCase(data::Interval* N, data::Interval* E, data::Interval* S, data::Interval* W);

private:
    double determinant(int i, int j) const;

    template<typename Float>
    void calculateEllipseBoundaries(
            const Point& p1, const Point& p2,
            const Point& q1, const Point& q2,
            double epsilon,
            double lambda[2]);
};

} }  //  namespace frechet

#include <freespace_impl.h>

#endif // FREESPACE_H