boundary.cpp

Go to the documentation of this file.

#include <boundary.h>


using namespace frechet;
using namespace reach;
using namespace data;

BoundarySegment::BoundarySegment(const Interval &ival, Orientation anori, Direction adir, Type t, void* owner)
    : LinkedListElement<BoundarySegment>(),
      Interval(ival),
      PointerInterval(),
      ori(anori), dir(adir),
      type(t)
{
    temp.clone=nullptr;
#ifdef QT_DEBUG
    temp.owner=owner;
#endif
}

PointerInterval::PointerInterval() : PointerInterval(nullptr,nullptr) { }

PointerInterval::PointerInterval(Pointer a, Pointer b) : l(a), h(b)
{
    Q_ASSERT(!a && !b || a && b && (a->dir==b->dir));
}

bool PointerInterval::operator!() const {
    return !l || !h;
}

PointerInterval &PointerInterval::operator=(const Pointer &p) {
    l = h = p;
    return *this;
}

PointerInterval &PointerInterval::swap(bool doit) {
    if (doit) std::swap(l,h);
    return *this;
}

PointerInterval PointerInterval::swapped() const {
    return {h,l};
}


Pointer frechet::reach::min(const Pointer a, const Pointer b)
{
    if(!a) return b;
    if(!b) return a;

    if ((a->lower() < b->lower()) || (a->upper() < b->upper()))
        return a;
    else
        return b;
}

Pointer frechet::reach::min(const PointerInterval& a)
{
    return min(a.l, a.h);
}

Pointer frechet::reach::min(const PointerInterval& a, const PointerInterval& b)
{
    return frechet::reach::min(frechet::reach::min(a),frechet::reach::min(b));
}

Pointer frechet::reach::max(Pointer a, Pointer b)
{
    if(!a) return b;
    if(!b) return a;

    if ((a->lower() > b->lower()) || (a->upper() > b->upper()))
        return a;
    else
        return b;
}

Pointer frechet::reach::max(const PointerInterval& a)
{
    return frechet::reach::max(a.l,a.h);
}

Pointer frechet::reach::max(const PointerInterval& a, const PointerInterval& b)
{
    return frechet::reach::max(frechet::reach::max(a),frechet::reach::max(b));
}

PointerInterval frechet::reach::PointerInterval::normalized() const
{
    if (!*this) return *this;

    Q_ASSERT(l->ori==h->ori);

    if (l->ori==VERTICAL)
        return { frechet::reach::min(*this), frechet::reach::max(*this) };  //  vertical UP
    else
        return { frechet::reach::max(*this), frechet::reach::min(*this) }; //  horizontal REVERSED
}

PointerInterval frechet::reach::PointerInterval::operator+ (const PointerInterval& b) const
{
    if(!*this) return b.normalized();
    if(!b) return this->normalized();

    Q_ASSERT(l->ori==h->ori);
    Q_ASSERT(b.l->ori==b.h->ori);

    Q_ASSERT(l->dir==b.l->dir);

    if (l->ori == b.l->ori) {
        if (l->ori==VERTICAL)
            return { frechet::reach::min(*this,b), frechet::reach::max(*this,b) };    //  vertical + vertical
        else
            return { frechet::reach::max(*this,b),frechet::reach:: min(*this,b) };    // horizonzal + horizontal
    }
    else
    {
        Q_ASSERT(l->ori != b.l->ori);
        if (l->dir==CLOCKWISE)
        {
            //  clockwise: horizontal + vertical
            if (l->ori==HORIZONTAL)
                return { frechet::reach::max(*this), frechet::reach::max(b) };
            else
                return { frechet::reach::max(b), frechet::reach::max(*this) };
        }
        else
        {
            //  counter-clockwise: vertical + horizontal
            if (l->ori==VERTICAL)
                return { frechet::reach::min(*this), frechet::reach::min(b) };
            else
                return { frechet::reach::min(b), frechet::reach::min(*this) };
        }
    }
}

frechet::reach::PointerInterval::operator bool() const {
    return l && h;
}

int frechet::reach::compare_interval(Pointer p, Pointer q)
{    
    if (p==q) return 0;

    Q_ASSERT(p->dir==q->dir);
    int c1,c2;

    //  dir==SECOND (right-top) --> VERTICAL < HORIZONTAL
    //  dir==FIRST (bottom-left) --> VERTICAL > HORIZONTAL

    switch(p->ori) {
    case HORIZONTAL:
        switch(q->ori) {
        case HORIZONTAL:
            c1 = numeric::compare(p->lower(),q->lower());
            c2 = numeric::compare(p->upper(),q->upper());
            return - (c1 ? c1 : c2);
        case VERTICAL:
            return (p->dir==FIRST) ? -1 : +1;   //  HORIZONTAL < VERTICAL
        }
        break;

    case VERTICAL:
        switch(q->ori) {
        case HORIZONTAL:
            return (p->dir==FIRST) ? +1 : -1;   //  VERTICAL > HORIZONTAL
        case VERTICAL:
            c1 = numeric::compare(p->lower(),q->lower());
            c2 = numeric::compare(p->upper(),q->upper());
            return c1 ? c1 : c2;
        }
        break;
    }
    Q_ASSERT(false);
}



int frechet::reach::compare_interval(const PointerInterval& i)
{
    return compare_interval(i.l,i.h);
}

bool frechet::reach::empty_interval(Pointer a, Pointer b)
{
    Q_ASSERT(a && b);
    return compare_interval(a,b) > 0;
}

bool frechet::reach::empty_interval(const PointerInterval& i)
{
    return empty_interval(i.l,i.h);
}

bool frechet::reach::empty_see_through_interval(Pointer p)
{
    Q_ASSERT(p->type==SEE_THROUGH);
    Q_ASSERT(!p->l || !p->h);
    if (p->l)
        return (p->dir==FIRST) ? (compare_pointers(p,p->l) > 0) : (compare_pointers(p,p->l) < 0);
    else
        return (p->dir==FIRST) ? (compare_pointers(p,p->h) > 0) : (compare_pointers(p,p->h) < 0);
}

int frechet::reach::compare_pointers(Pointer p, Pointer q)
{
    if (p==q) return 0;

    Q_ASSERT(p->dir != q->dir);
    int c1,c2;

    switch(p->ori) {
    case HORIZONTAL:
        switch(q->ori) {
        case HORIZONTAL:
            c1 = numeric::compare(p->lower(),q->lower());
            c2 = numeric::compare(p->upper(),q->upper());
            return c1 ? c1 : c2;
        case VERTICAL:
            return (p->dir==FIRST) ? -1 : +1;
        }
        break;

    case VERTICAL:
        switch(q->ori) {
        case HORIZONTAL:
            return (p->dir==FIRST) ? -1 : +1;
        case VERTICAL:
            c1 = numeric::compare(p->lower(),q->lower());
            c2 = numeric::compare(p->upper(),q->upper());
            return c1 ? c1 : c2;
        }
        break;
    }
    Q_ASSERT(false);
}


bool PointerInterval::contains(Pointer p) const
{
    if (p==l || p==h) return true;

    return (compare_interval(p,l) >= 0) && (compare_interval(p,h) <= 0);
}

void PointerInterval::clear()
{
    l = h = nullptr;
}

static std::string DIRECTION[2][2] = {
    { "B", "T" }, { "L","R" }
};

const std::string direction(Pointer p) {
    return DIRECTION[p->ori][p->dir];
}

static std::string TYPE[3] = {
    "n","r","s"
};

std::ostream& frechet::reach::operator<<(std::ostream &out, const BoundaryList &list)
{
    if (list.empty()) {
        out << "[]";
        return out;
    }

    Pointer p=list.first();
    out << "[" << direction(p) << ": ";

    int i=0; int imax=10;
    for( ; p && i < imax; p=p->next(), ++i)
    {
        if (i > 0) out << ",";
        out << "("<< TYPE[p->type];
        if (i==0) out<<" "<<p->lower();
        out << ".."<< p->upper();

        if (p->l) out << " l="<<direction(p->l)<<".."<<p->l->upper();
        if (p->h) out << " h="<<direction(p->h)<<".."<<p->h->upper();
        out << ")";
    }
    if (i >= imax && list.size() > imax)
        out << "...(" << (list.size()-imax)<<")";
    out << "]";
    return out;
}