freespaceview.cpp

Go to the documentation of this file.

#include <freespaceview.h>
#include <structure.h>
#include <poly/algorithm.h>

#include <QGraphicsPolygonItem>
#include <QSettings>
#include <QApplication>

#include <frechetviewapplication.h>
#include <frechet/view/freespaceview.h>

using namespace frechet;
using namespace data;
using namespace view;
using namespace app;

//const QPen FreeSpaceView::GRID_PEN(Qt::black, 0.5, Qt::SolidLine, Qt::SquareCap, Qt::RoundJoin);
//const QPen FreeSpaceView::AREA_PEN(Qt::red, 0.5, Qt::SolidLine, Qt::SquareCap, Qt::RoundJoin);
//const QPen FreeSpaceView::BOUNDS_PEN(Qt::green, 0.5, Qt::DotLine, Qt::SquareCap, Qt::RoundJoin);

const QBrush FreeSpaceView::AREA_BRUSH1(QColor(Qt::blue).darker());
const QBrush FreeSpaceView::AREA_BRUSH2(Qt::blue);

const double FreeSpaceView::TF_MAX_ARG = 1e6;
const double CellView::MAX_DIAMETER = 1e5;

const QColor FreeSpaceView::LIGHT_GRAY (230,230,230);
const QColor FreeSpaceView::AREA_COLOR (228,37,72);

FreeSpaceView::FreeSpaceView(QWidget *parent)
    :   BaseView(parent,"Free-Space Diagram",false),        
        _showBounds(false),
        componentPalette(),
        pathView(nullptr), select(nullptr),
        cells(nullptr)
{
    GRID_PEN[SOLID] = QPen(Qt::black, 0.5, Qt::SolidLine, Qt::SquareCap, Qt::RoundJoin);
    GRID_PEN[THIN] = QPen(Qt::black, 0.2, Qt::SolidLine, Qt::SquareCap, Qt::RoundJoin);
    GRID_PEN[DOTTED] = QPen(Qt::black, 0.5, Qt::DotLine, Qt::SquareCap, Qt::RoundJoin);

    AREA_PEN = QPen(Qt::red, 0.5, Qt::SolidLine, Qt::SquareCap, Qt::RoundJoin);
    BOUNDS_PEN = QPen(Qt::green, 0.5, Qt::DotLine, Qt::SquareCap, Qt::RoundJoin);
    PATH_PEN = QPen(Qt::yellow, 2.0, Qt::SolidLine, Qt::RoundCap, Qt::RoundJoin);
    //  mirror horizontally; Origin is at the lower right.
    flipVertical(true);
    view()->setMouseTracking(true);
    view()->viewport()->setMouseTracking(true);
}

FreeSpaceView::~FreeSpaceView()
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    for(int i=0; i < freeSpace->n-1; ++i)
        for(int j=0; j < freeSpace->m-1; ++j)
            delete cells->at(i,j);
}

void FreeSpaceView::populateScene()
{
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
//    frechet::reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();
//    frechet::k::kAlgorithm::ptr kalgorithm = FrechetViewApplication::instance()->getKAlgorithm();

    cells = CellView::MatrixPtr(
                new CellView::Matrix (
                    std::max(freeSpace->n-1,0),
                    std::max(freeSpace->m-1,0)));


    scene->clear();
    graphicsView->setViewportUpdateMode(QGraphicsView::NoViewportUpdate);
    componentPalette.clear();

    //  set pen width relative to scene size
    QRectF r = grid->sceneRect();
    double pen_width = std::min(2.0, std::max(r.width(),r.height()) * 0.001);

    GRID_PEN[SOLID].setWidthF(pen_width);
    GRID_PEN[THIN].setWidthF(pen_width*0.4);
    GRID_PEN[DOTTED].setWidthF(pen_width);

    BOUNDS_PEN.setWidthF(2*pen_width);
    AREA_PEN.setWidthF(pen_width);
    PATH_PEN.setWidthF(4*pen_width);
    //PEN_SELECT.setWidthF(8*pen_width);

    //  paint the grid
    for(int i=0; i < freeSpace->n; ++i)
        addGridLine( grid->verticalGridLine(i), grid->hor().lineStyle(i) );

    for(int j=0; j < freeSpace->m; ++j)
        addGridLine( grid->horizontalGridLine(j), grid->vert().lineStyle(j) );

    for(int i=0; i < freeSpace->n-1; ++i)
        for(int j=0; j < freeSpace->m-1; ++j)
        {
            cells->at(i,j) = NULL;
            //  created on demand
        }
    //  IntervalViews
    intervalView[0] = new IntervalView(grid,IntervalView::HORIZONTAL,&componentPalette, 3*pen_width);
    intervalView[1] = new IntervalView(grid,IntervalView::VERTICAL,&componentPalette, 3*pen_width);

    //  total bounds
    if ((freeSpace->n > 0) && (freeSpace->m > 0))
    {        
        //  leave room for IntervalViews TODO be more precise?
//        r.adjust(
//                -10 * intervalView[0]->ROW_HEIGHT,
//                -10 * intervalView[0]->ROW_HEIGHT, 0,0);
        scene->setSceneRect(r);
        graphicsView->setSceneRect(r);
    }

    scene->addItem(intervalView[0]);
    scene->addItem(intervalView[1]);

    pathView = new QGraphicsItemGroup();
    //pathView->setPen(PATH_PEN);
    scene->addItem(pathView);

    select = new QGraphicsPathItem();
    select->setVisible(false);
    select->setZValue(+3);
    select->setPen(PEN_SELECT);
    setPenWidth(select,8*pen_width);
    scene->addItem(select);

    graphicsView->setViewportUpdateMode(QGraphicsView::SmartViewportUpdate);
}

void FreeSpaceView::dropUnusedItems()
{
    for(int i=0; i < cells->n; ++i)
        for(int j=0; j < cells->m; ++j)
        {
            CellView*& cv = cells->at(i,j);
            if (cv && !cv->dropUnusedItems()) {
                scene->removeItem(cv);
                delete cv;
                cv = NULL;
            }
        }
}


CellView* FreeSpaceView::getCellView(int i, int j)
{
    CellView* cv = cells->at(i,j);
    if (! cv) {
        cv = new CellView(this,i,j);
        scene->addItem(cv);
        cells->at(i,j) = cv;
    }
    return cv;
}


void FreeSpaceView::calculateFreeSpace(double eps)
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    if (!freeSpace) return; //  before initialisation

    frechet::k::kAlgorithm::ptr kalgorithm = FrechetViewApplication::instance()->getKAlgorithm();
    frechet::reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();
    frechet::poly::Algorithm::ptr poly = FrechetViewApplication::instance()->getPolyAlgorithm();

    //  TODO move to Application !?
    QApplication::setOverrideCursor(Qt::WaitCursor);

    freeSpace->calculateFreeSpace(eps);
    /*  Note: cell bounds are only needed for k-Frechet.
     *  For curve alogithms, bounds are not relevant.
     *  But they make for nicer visualisation.
     */
    freeSpace->calculateBounds(eps);

    path_ok = false;    // show path only for. ...
    switch(FrechetViewApplication::instance()->currentAlgorithm())
    {
    case FrechetViewApplication::ALGORITHM_K_FRECHET:
    {
        freeSpace->components().calculateComponents(*freeSpace);
        //  automatically calculate k-Frechet Greedy
        //  cancel BG job
        FrechetViewApplication::instance()->cancelBackgroundJob();
        kalgorithm->runGreedy();
    }   break;

    case FrechetViewApplication::ALGORITHM_CURVE:
    {   //  components are not relevant
        freeSpace->components().clear();

        path_ok = (bool)poly->decideCurve(freeSpace,fspath,NAN,false); //  TOOD update status ? or not ?
        emit curveFinished(path_ok);
    }   break;

    case FrechetViewApplication::ALGORITHM_POLYGON:
    {   //  components are not relevant
        freeSpace->components().clear();

        switch (poly->status()) {
        case frechet::poly::Algorithm::P_CONVEX:
        case frechet::poly::Algorithm::Q_CONVEX:
                path_ok = (bool)poly->decideCurve(freeSpace,fspath,NAN,false); //  TOOD update status ? or not ?
                emit curveFinished(path_ok);
                break;
        default:
        case frechet::poly::Algorithm::SET_UP:
        case frechet::poly::Algorithm::RUNNING:
        case frechet::poly::Algorithm::YES:
        case frechet::poly::Algorithm::NO:
                path_ok = false;// path is only available later, not now
                //fspath->clearReachability();
                //fspath->clear();
                break;
        }
    }   break;
    }

    updateView(eps);

    QApplication::restoreOverrideCursor();
}

void FreeSpaceView::updateView(double eps)
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    graphicsView->setViewportUpdateMode(QGraphicsView::NoViewportUpdate);
//    graphicsView->setInteractive(false);

    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    frechet::reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();

    int countEmpty=0, countEllipse=0, countPoly=0;
    QLineF bounds[4];

    for(int i=0; i < freeSpace->n-1; ++i)
        for(int j=0; j < freeSpace->m-1; ++j)
        {
            CellView* cl = cells->at(i,j);
            if (cl || ! freeSpace->cellEmptyBounds(i,j))
            {
                cl = getCellView(i,j);  //  created on demand

                size_t comp = freeSpace->component(i,j);
                if (FrechetViewApplication::instance()->currentAlgorithm(
                            FrechetViewApplication::ALGORITHM_K_FRECHET))
                {
                    if (_showBounds)
                        createBoundsRect(i,j,bounds);
                    cl->update(eps, _showBounds, bounds);

                    if (comp != Components::NO_COMPONENT)
                        cl->setColor(componentPalette[comp]);

                    //  double check components
                    Q_ASSERT((i==0) || !freeSpace->cell(i,j).L || (comp==freeSpace->component(i-1,j)));
                    Q_ASSERT((j==0) || !freeSpace->cell(i,j).B || (comp==freeSpace->component(i,j-1)));
                }
                else
                {                    
                    if (_showBounds)
                        createReachabilityRect(i,j,bounds);
                    cl->update(eps, _showBounds, bounds);
                    //  components are not relevant
                    cl->setColor(AREA_COLOR, PATH_PEN.color());
                }

                switch(cl->what & CellView::MASK)
                {
                case CellView::NOTHING: countEmpty++; break;
                case CellView::POLY:    countPoly++; break;
                case CellView::ELLIPSE: countEllipse++; break;
                }            }
            else {
                countEmpty++;
            }
        }

    showPath(path_ok);

    //qDebug() << "empty="<<countEmpty<<" ellipse="<<countEllipse<<" poly="<<countPoly<<"\n";

    /*  Update Intervals
     * */
    updateIntervals();

    graphicsView->setViewportUpdateMode(QGraphicsView::SmartViewportUpdate);
//    graphicsView->setInteractive(true);
}

void FreeSpaceView::showPath(bool show)
{
    if (!show) {
        pathView->setVisible(false);
        segmentSelected(nullptr);   //  also informs other views
        updateBounds();
        return;
    }

    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    frechet::reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();

    /*
     *  show feasible path (that was calculated above)
     * */
    QList<QGraphicsItem*> children = pathView->childItems();
    GraphicsHoverLineItem* item;
    int k=0;
    for(int i=0; i < 2; ++i) {
        Curve c = fspath->getPath(i);
        c = grid->mapCurve(c);
        //  TODO delegate mapping to FSPath; needs specialisation for PolyPath

        for(int j=0; j+1 < c.size(); ++j) {
            QLineF line(c[j],c[j+1]);
            if (k < children.size()) {
                item = (GraphicsHoverLineItem*)children[k++];
                item->setLine(line);
                item->setVisible(true);
            }
            else {
                item = new GraphicsHoverLineItem(line,
                                        GraphicsHoverLineItem::FS,-1,-1,
                                        pathView);
                item->setPen(PATH_PEN);
                k++;
            }
            Q_ASSERT(item->loc==GraphicsHoverLineItem::FS);
            item->update(i,j);
        }
    }
    for( ; k < children.size(); ++k)
        children[k]->setVisible(false);

    pathView->setVisible(true);
    pathView->setZValue(+1);    //  to front

    updateBounds();
}

void FreeSpaceView::updateBounds()
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();

    graphicsView->setViewportUpdateMode(QGraphicsView::NoViewportUpdate);
    QLineF bounds[4];

    /*  Update Free Space
     * */
    for(int i=0; i < freeSpace->n-1; ++i)
        for(int j=0; j < freeSpace->m-1; ++j)
        {
            CellView* cl = cells->at(i,j);
            if (cl || ! freeSpace->cellEmptyBounds(i,j))
            {
                cl = getCellView(i,j);

                if (FrechetViewApplication::instance()->currentAlgorithm()
                        ==FrechetViewApplication::ALGORITHM_K_FRECHET)
                {
                    //  eps < 0 indicates that only _showBounds needs to be updated
                    if (_showBounds)
                        createBoundsRect(i,j,bounds);
                    cl->update(-1.0, _showBounds, bounds);

                    size_t comp = freeSpace->component(i,j);
                    if (comp!=Components::NO_COMPONENT)
                        cl->setColor(componentPalette[comp]);
                }
                else
                {
                    //  eps < 0 indicates that only _showBounds needs to be updated
                    if (_showBounds)
                        createReachabilityRect(i,j,bounds);
                    cl->update(-1.0, _showBounds, bounds);
                    cl->setColor(AREA_COLOR, PATH_PEN.color());
                }
            }
        }

    updateIntervals();

    graphicsView->setViewportUpdateMode(QGraphicsView::SmartViewportUpdate);
}

void FreeSpaceView::updateIntervals()
{
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    frechet::k::kAlgorithm::ptr kalgorithm = FrechetViewApplication::instance()->getKAlgorithm();

    QRectF old_scene = scene->sceneRect();
    QRectF r = grid->sceneRect();

    if (_showBounds &&
            FrechetViewApplication::instance()->currentAlgorithm(
                FrechetViewApplication::ALGORITHM_K_FRECHET))
    {
        //  k-Frechet Intervals
        intervalView[0]->clear();
        intervalView[1]->clear();

        intervalView[0]->addAll(kalgorithm->horizontalIntervals());
        intervalView[1]->addAll(kalgorithm->verticalIntervals());

        r.adjust(   -intervalView[0]->extent(),
                    -intervalView[1]->extent(), 0,0);

        intervalView[0]->setVisible(true);
        intervalView[1]->setVisible(true);
    }
    else
    {
        intervalView[0]->setVisible(false);
        intervalView[1]->setVisible(false);
    }

    //  adjust scene rect
    if (r!=old_scene) {
        scene->setSceneRect(r);
        graphicsView->setSceneRect(r);
        setupMatrix();
    }
}

void FreeSpaceView::showResult(const BitSet* resultSet)
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();

    for(int i=0; i < freeSpace->n-1; ++i)
        for(int j=0; j < freeSpace->m-1; ++j)
        {
            CellView* cl = cells->at(i,j);
            if (cl || ! freeSpace->cellEmptyBounds(i,j))
            {
                cl = getCellView(i,j);

                size_t comp = freeSpace->component(i,j);
                if (FrechetViewApplication::instance()->currentAlgorithm(
                    FrechetViewApplication::ALGORITHM_K_FRECHET))
                {
                    if (comp!=Components::NO_COMPONENT)
                    {
                        if (!resultSet || resultSet->contains(comp))
                            cl->setColor(componentPalette[comp]);
                        else
                            cl->setColor(LIGHT_GRAY);
                    }
                }
                else { //  components are not relevant
                    cl->setColor(AREA_COLOR, PATH_PEN.color());
                }
            }
        }

    intervalView[0]->showResult(resultSet);
    intervalView[1]->showResult(resultSet);
}

QTransform FreeSpaceView::createEllipseTransform(int i, int j)
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();

    Point s1 = freeSpace->P[i];
    Point s2 = freeSpace->P[i+1];

    Point t1 = freeSpace->Q[j];
    Point t2 = freeSpace->Q[j+1];

    Point p0 = intersection(s1,s2, t1,t2);
    Point dir1 = normalized(s2-s1);
    Point dir2 = normalized(t2-t1);

    double origx = grid->hor().map(i) - Point::dotProduct(s1-p0,dir1);
    double origy = grid->vert().map(j) - Point::dotProduct(t1-p0,dir2);
    //  = center of ellipse
    double ang = Point::dotProduct(dir1,dir2);
    double mu = 1.0/sqrt(2*(1-ang));
    double mv = 1.0/sqrt(2*(1+ang));

    return QTransform( mu, mu, -mv, mv, origx, origy );
}

bool FreeSpaceView::validTransform(const QTransform& tf)
{
    return validTransformArg(tf.m11())
            && validTransformArg(tf.m12())
            //&& validTransformArg(tf.m13())
            && validTransformArg(tf.m21())
            && validTransformArg(tf.m22())
            //&& validTransformArg(tf.m23())
            && validTransformArg(tf.m31())
            && validTransformArg(tf.m32());
            //&& validTransformArg(tf.m33());
}

bool FreeSpaceView::validTransformArg(double x)
{
    return !std::isnan(x)
            && std::isfinite(x)
            && (abs(x) < FreeSpaceView::TF_MAX_ARG);
}

void FreeSpaceView::addGridLine(QLineF line, LineStyle style)
{
    if (style != NONE) {
        Q_ASSERT(style==SOLID || style==THIN || style==DOTTED);
        scene->addLine( line, GRID_PEN[style] );
    }
}

void FreeSpaceView::showBounds(bool on)
{
    if (on != _showBounds) {
        _showBounds = on;
        updateBounds();
    }
}

void FreeSpaceView::showGreedyResult()
{
    frechet::k::kAlgorithm::ptr kalgorithm = FrechetViewApplication::instance()->getKAlgorithm();
    showResult(&kalgorithm->greedyResult().result);
}

void FreeSpaceView::showOptimalResult()
{
    frechet::k::kAlgorithm::ptr kalgorithm = FrechetViewApplication::instance()->getKAlgorithm();
    showResult(&kalgorithm->optimalResult().result);
}

void FreeSpaceView::hideResult()
{
    showResult(NULL);
}

void FreeSpaceView::segmentSelected(GraphicsHoverLineItem *item)
{
    if (!pathView->isVisible())
        item = selected_item = nullptr;

    if (item) {
        doHiliteSegment(item->loc,item->a,item->b);
        emit hiliteSegment(item->loc, item->a,item->b);
    }
    else {
        doHiliteSegment(GraphicsHoverLineItem::None,-1,-1);
        emit hiliteSegment(GraphicsHoverLineItem::None, -1,-1);
    }
}

void FreeSpaceView::onHiliteSegment(int aloc, int a, int b)
{
    doHiliteSegment((GraphicsHoverLineItem::Location)aloc, a, b);
}

void FreeSpaceView::doHiliteSegment(GraphicsHoverLineItem::Location loc, int a, int b)
{
    const reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();

    if (!fspath || fspath->empty() || !pathView->isVisible())
        loc = GraphicsHoverLineItem::None;

    Curve mapped[2];
    QPainterPath path;
    switch(loc)
    {
    case GraphicsHoverLineItem::P:
        fspath->mapFromP(poly::Segment(a,b),mapped);
        break;

    case GraphicsHoverLineItem::Q:
        fspath->mapFromQ(poly::Segment(a,b),mapped);
        break;

    case GraphicsHoverLineItem::Pdiag: {
        //  TODO
        //  here, things get complicated. We should replace part of the FS diagram
        //  with a Shortest-Path Free-Space diagram.
        //  in the mean time, we display just the endpoints of the diagonal
        Point q1 = fspath->mapFromP(a);
        Point q2 = fspath->mapFromP(b);
        double penw = select->pen().widthF();
        addPoint(path, grid->mapPoint(q1), penw);
        addPoint(path, grid->mapPoint(q2), penw);
    }   break;

    case GraphicsHoverLineItem::Qdiag: {
        //  TODO
        //  here, things get complicated. We should replace part of the FS diagram
        //  with a Shortest-Path Free-Space diagram.
        //  in the mean time, we display just the endpoints of the diagonal
        Point p1 = fspath->mapFromQ(a);
        Point p2 = fspath->mapFromQ(b);
        double penw = select->pen().widthF();
        addPoint(path, grid->mapPoint(p1), penw);
        addPoint(path, grid->mapPoint(p2), penw);
    }   break;

    case GraphicsHoverLineItem::FS: {
        Curve c = fspath->getPath(a);
        mapped[0].push_back(c[b]);
        mapped[0].push_back(c[b+1]);
        Q_ASSERT((c[b].x() != c[b+1].x()) && (c[b].y() != c[b+1].y()));
    }   break;

    case GraphicsHoverLineItem::None:
        //  clear selection
        break;

    default:
        Q_ASSERT(false);
    }

    if (loc != GraphicsHoverLineItem::None) {
        addPolygon(path, grid->mapCurve(mapped[0]));
        addPolygon(path, grid->mapCurve(mapped[1]));
        select->setPath(path);
    }

    select->setVisible(loc != GraphicsHoverLineItem::None);
}

void FreeSpaceView::hilitePoint(QPointF p)
{
    QPainterPath path;
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    double penw = select->pen().widthF();
    addPoint(path, grid->mapPoint(p), penw);
    select->setPath(path);
    select->setVisible(true);
}

void FreeSpaceView::saveSettings(QSettings& settings, QString group)
{
    settings.beginGroup(group);
    settings.setValue("show.bounds",_showBounds);
    settings.endGroup();

    BaseView::saveSettings(settings,group);
}

void FreeSpaceView::restoreSettings(QSettings& settings, QString group)
{
    settings.beginGroup(group);
    _showBounds = settings.value("show.bounds",false).toBool();
    settings.endGroup();

    BaseView::restoreSettings(settings,group);
}


static const double OPACITY = 0.8;

CellView::CellView(FreeSpaceView* aparent, int ai, int aj)
    : QGraphicsItemGroup(),
      parent(aparent),
      i(ai), j(aj),
      cellBounds(), clipShape(),
      _poly(NULL),
      _ellipse(NULL), useEllipse(true), //  unless..
      _bounds(),
      what(NOTHING)
{
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();
    cellBounds = grid->cellBounds(i,j);
    clipShape.addRect(cellBounds);
    _bounds[0]=_bounds[1]=_bounds[2]=_bounds[3]=NULL;
}

CellView::~CellView()
{
    //  delete lines[] ?
}

//  on-demand methods


QGraphicsPolygonItem* CellView::getPoly() {
    if (! _poly) {
        _poly = new QGraphicsPolygonItem(this);        
        _poly->setPen(Qt::NoPen);
        _poly->setBrush(FreeSpaceView::AREA_BRUSH2);
        _poly->setOpacity(OPACITY);
        //removeFromGroup(poly);  //  might be added later
    }
    return _poly;
}

QGraphicsEllipseItem* CellView::getEllipse(){
    if(! _ellipse && useEllipse) {
        QTransform tf = parent->createEllipseTransform(i,j);
        //  The transformation becomes invalid, or impracticable,
        //  when the line segments are (almost) parallel.
        //  In this case, we draw a polygon insteadd.
        useEllipse = parent->validTransform(tf);
        if (useEllipse) {
            _ellipse = new QGraphicsEllipseItem(this);
            _ellipse->setPen(Qt::NoPen);
            _ellipse->setBrush(FreeSpaceView::AREA_BRUSH2);
            _ellipse->setOpacity(OPACITY);
            _ellipse->setTransform(tf,false);
            //removeFromGroup(ellipse);  //  might be added, later
        }
    }
    return _ellipse;
}

QGraphicsLineItem* CellView::getBounds(int i)
{
    if (! _bounds[i]){
        _bounds[i] = new QGraphicsLineItem(this);
        _bounds[i]->setPen(parent->BOUNDS_PEN);
        //_bounds[i]->setBrush(Qt::NoBrush);
        _bounds[i]->setOpacity(OPACITY);
        _bounds[i]->setZValue(1.0);
        //removeFromGroup(rect);  //  might be added later
    }
    return _bounds[i];
}


void CellView::setBounds(QLineF bounds[4])
{
    for(int i=0; i < 4; ++i)
        if (bounds[i].isNull()) {
            if (_bounds[i]) {
                _bounds[i]->setVisible(false);
                _bounds[i]->setLine(bounds[i]);
            }
        }
        else {
            addToGroup(getBounds(i));
            getBounds(i)->setVisible(true);
            getBounds(i)->setLine(bounds[i]);
        }
}

void CellView::setColor(QColor areaColor, QColor boundsColor)
{
    if (what==NOTHING)
        return;

    if (what & ELLIPSE)
        setBrushColor(getEllipse(),areaColor);

    if (what & POLY) {
        setBrushColor(getPoly(),areaColor);
        setPenColor(getPoly(),areaColor);
    }

    if (what & BOUNDS) {
        setBoundsPenColor(_bounds,4, boundsColor.isValid() ? boundsColor : areaColor);
    }
}

void CellView::setPenColor(QAbstractGraphicsShapeItem* item, QColor col)
{
    QPen pen = item->pen();
    if ((pen.style()!=Qt::NoPen) && (pen.color() != col)) {
        pen.setColor(col);
        item->setPen(pen);
    }
}

void CellView::setBoundsPenColor(QGraphicsLineItem** items, int len, QColor col)
{
    for(int i=0; i < len; ++i)
        if (items[i]) {
            QPen pen = items[i]->pen();
            if ((pen.style()!=Qt::NoPen) && (pen.color() != col)) {
                pen.setColor(col);
                items[i]->setPen(pen);
            }
        }
}

void CellView::setBrushColor(QAbstractGraphicsShapeItem* item, QColor col)
{
    QBrush brush = item->brush();
    if ((brush.style() != Qt::NoBrush) && (brush.color() != col)) {
        brush.setColor(col);
        item->setBrush(brush);
    }
}

void CellView::setPenStyle(QAbstractGraphicsShapeItem* item, Qt::PenStyle style)
{
    QPen pen = item->pen();
    if (pen.style() != style) {
        pen.setStyle(style);
        item->setPen(pen);
    }
}

void CellView::setPenStyleWidth(QAbstractGraphicsShapeItem* item, Qt::PenStyle style, float width)
{
    QPen pen = item->pen();
    if (pen.style() != style) {
        pen.setStyle(style);
        item->setPen(pen);
    }
    if (pen.widthF() != width) {
        pen.setWidthF(width);
        item->setPen(pen);
    }
}

void CellView::dodraw(What w)
{
    if ((w & BOUNDS) != (what & BOUNDS))
    {
        if (what & BOUNDS) {
            for (int i=0; i < 4; ++i)
                if (_bounds[i]) {
                    removeFromGroup(_bounds[i]);
                    scene()->removeItem(_bounds[i]);
                    _bounds[i]->setVisible(false);
                }
        }
        else {
            for(int i=0; i < 4; ++i) {
                if (_bounds[i] && ! _bounds[i]->line().isNull()) {
                    addToGroup(_bounds[i]);
                    _bounds[i]->setVisible(true);
                }
            }
        }
    }

    if ((w & MASK) != (what & MASK))
    {
        switch(what & MASK)
        {
        case POLY:
            if (_poly) {
                removeFromGroup(_poly);
                scene()->removeItem(_poly);
                _poly->setVisible(false);
            }
            break;
        case ELLIPSE:
            if (_ellipse) {
                removeFromGroup(_ellipse);
                scene()->removeItem(_ellipse);
                _ellipse->setVisible(false);
            }
            setFlag(GraphicsItemFlag::ItemClipsToShape,false);
            setFlag(GraphicsItemFlag::ItemClipsChildrenToShape,false);
            break;
        }

        switch(w & MASK)
        {
        case POLY:
            addToGroup(getPoly());
            _poly->setVisible(true);
            break;
        case ELLIPSE:
            addToGroup(getEllipse());
            setFlag(GraphicsItemFlag::ItemClipsToShape,true);
            setFlag(GraphicsItemFlag::ItemClipsChildrenToShape,true);
            _ellipse->setVisible(true);
            break;
        }
    }

    //  draw either poly or ellipse; never both
    Q_ASSERT(! (_poly && _poly->isVisible() && _ellipse && _ellipse->isVisible()));
    what = w;
}

void CellView::dropUnusedItem(QGraphicsItem** item)
{
    if (*item && !(*item)->isVisible()) {
        delete *item;
        item = NULL;
    }
}

bool CellView::dropUnusedItems()
{
    bool any_bounds=false;  //  unless...
    for(int i=0; i < 4; ++i) {
        dropUnusedItem((QGraphicsItem**)&_bounds[i]);
        if (_bounds[i]) any_bounds=true;
    }

    dropUnusedItem((QGraphicsItem**)&_poly);
    dropUnusedItem((QGraphicsItem**)&_ellipse);
    return any_bounds || _poly || _ellipse;
}

void CellView::update(double eps,
                      bool showBounds,
                      QLineF bounds[4])
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();

    //  TODO heuristic:
    //      if ( | [s1,s2] p0 | > 1000 * (bounds.width()+bounds.heigth())
    //          drawPoly=true
    if (freeSpace->cellEmptyBounds(i,j))
    {
        dodraw(NOTHING);
        return;
    }

    //  Boundary rectangle
    if (showBounds)
        setBounds(bounds);

    if (freeSpace->cellFull(i,j))
    {   //  draw filled rect
        if (getPoly()->polygon() != QPolygonF(cellBounds))
            getPoly()->setPolygon(cellBounds);
        setPenStyle(getPoly(), Qt::NoPen);
        dodraw(showBounds ? POLY_AND_BOUNDS : POLY);
        return;
    }

    if (getEllipse())
    {   //  draw ellipse
        // (unless it becomes too large)
        if (eps >= 0.0)
            getEllipse()->setRect(-eps,-eps,2*eps,2*eps);
        //  else:
        //      eps < 0 indicates that eps has not changed

        //  Transform already set. Not need to update.
        dodraw(showBounds ? ELLIPSE_AND_BOUNDS : ELLIPSE);
        return;
    }
    //  else:
    //  draw (almost) parallel lines
    bool thin;
    Curve p = createPolygon(i,j, &thin);
    //poly->setPen(showSegments ? FreeSpaceView::GRID_PEN : Qt::NoPen);
    if (getPoly()->polygon()!=p)
        getPoly()->setPolygon(p);
    //  if the polygon is thin (only a line); use pen !

    setPenStyleWidth(getPoly(),
                     thin ? parent->AREA_PEN.style() : Qt::NoPen,
                     parent->AREA_PEN.widthF());

    dodraw(showBounds ? POLY_AND_BOUNDS : POLY);
}


void FreeSpaceView::createBoundsRect(int i, int j, QLineF result[4])
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    QRectF r = freeSpace->segmentBounds(i,j);

    if (r.left() > 0.0 && !std::isnan(r.height()))
        result[0] = boundsLine(r.bottomLeft(),r.topLeft(), i,j);
    else
        result[0] = QLineF();

    if (r.right() < 1.0 && !std::isnan(r.height()))
        result[1] = boundsLine(r.bottomRight(),r.topRight(), i,j);
    else
        result[1] = QLineF();

    if (r.top() > 0.0 && !std::isnan(r.width()))
        result[2] = boundsLine(r.topLeft(),r.topRight(), i,j);
    else
        result[2] = QLineF();

    if (r.bottom() < 1.0 && !std::isnan(r.width()))
        result[3] = boundsLine(r.bottomLeft(),r.bottomRight(), i,j);
    else
        result[3] = QLineF();
}

void FreeSpaceView::createReachabilityRect(int i, int j, QLineF result[4])
{
    frechet::reach::FSPath::ptr fspath = FrechetViewApplication::instance()->getFSPath();

    const Interval& L = fspath->left(i,j);
    const Interval& B = fspath->bottom(i,j);
    const Interval& R = fspath->left(i+1,j);
    const Interval& T = fspath->bottom(i,j+1);

    //  left
    if (L)
        result[0] = boundsLine(
                    QPointF(0.0, L.lower()),
                    QPointF(0.0, L.upper()), i,j);
    else
        result[0] = QLineF();

    //  bottom
    if (B)
        result[1] = boundsLine(
                    QPointF(B.lower(), 0.0),
                    QPointF(B.upper(), 0.0), i,j);
    else
        result[1] = QLineF();

    //  right
//  if ((i+1)==(freeSpace->n-1)) {
        if (R.valid())
            result[2] = boundsLine(
                        QPointF(1.0,R.lower()),
                        QPointF(1.0,R.upper()), i,j);
        else
            result[2] = QLineF();

    //  upper
//    if ((j+1)==(freeSpace->m-1)) {
    if (T)
        result[3] = boundsLine(
                    QPointF(T.lower(),1.0),
                    QPointF(T.upper(),1.0), i,j);
    else
        result[3] = QLineF();

    //  Note: currently, upper and right bounds are drawn TWICE
    //  to counter clipping. Better: extend the clipping bounds slightly(?)
}

QLineF FreeSpaceView::boundsLine(QPointF a, QPointF b, int i, int j)
{
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();

    QLineF line (a,b);
    line.translate(i,j);
    return grid->mapLine(line);
}

void FreeSpaceView::onAlgorithmChanged(int) {
    if (pathView) showPath(false);
}

QPolygonF CellView::createPolygon(int i, int j,
                              bool* thin)
{
    FreeSpace::ptr freeSpace = FrechetViewApplication::instance()->getFreeSpace();
    Grid::ptr grid = FrechetViewApplication::instance()->getGrid();

    //  Polygon
    const Interval& L = freeSpace->cell(i,j).L;
    const Interval& R = freeSpace->cell(i+1,j).L;

    const Interval& B = freeSpace->cell(i,j).B;
    const Interval& T = freeSpace->cell(i,j+1).B;

    *thin = true;   //  unless...
    QPolygonF result;
    if (L)     {
        result.append(grid->mapPoint(Point(i,j+L.lower())));
        result.append(grid->mapPoint(Point(i,j+L.upper())));
        if(L.lower() < L.upper()) *thin=false;
        //  TODO small threshold?
    }
    if (T) {
        result.append(grid->mapPoint(Point(i+T.lower(),j+1)));
        result.append(grid->mapPoint(Point(i+T.upper(),j+1)));
        if(T.lower() < T.upper()) *thin=false;
    }
    if (R)    {
        result.append(grid->mapPoint(Point(i+1,j+R.upper())));
        result.append(grid->mapPoint(Point(i+1,j+R.lower())));
        if(R.lower() < R.upper()) *thin=false;
    }
    if (B)   {
        result.append(grid->mapPoint(Point(i+B.upper(),j)));
        result.append(grid->mapPoint(Point(i+B.lower(),j)));
        if(B.lower() < B.upper()) *thin=false;
    }
    return result;
}