path: root/sigmodr/widgets/mapeditor/WorldMapPlacement.cpp

/*
 * Copyright 2009 Ben Boeckel <MathStuf@gmail.com>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along
 * with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

// Header include
#include "WorldMapPlacement.h"

// Qt includes
#include <QtCore/QtAlgorithms>
#include <QtCore/QBitArray>
#include <QtCore/QMap>
#include <QtCore/QPair>
#include <QtCore/QQueue>
#include <QtCore/QSet>

// Standard includes
#include <climits>
#include <cmath>

using namespace Sigmodr::Widgets;

enum Corner
{
    Invalid = -1,
    TopLeft = 0,
    TopRight = 1,
    BottomRight = 2,
    BottomLeft = 3
};
enum Resolution
{
    Include = 1,
    Delete = 2
};
Q_DECLARE_FLAGS(Resolutions, Resolution)
Q_DECLARE_OPERATORS_FOR_FLAGS(Resolutions)
typedef QPair<Resolutions, QPoint> NextTarget;
typedef QMap<QPoint, NextTarget> CollisionInfo;

static bool operator<(const QPoint& point1, const QPoint& point2)
{
    if (point1.y() == point2.y())
        return point1.x() < point2.x();
    return point1.y() < point2.y();
}

static bool operator<(const QRect& rect1, const QRect& rect2)
{
    return rect1.topLeft() < rect2.topLeft();
}

static bool touches(const QPolygon& polygon1, const QPolygon& polygon2)
{
    foreach (const QPoint& point, polygon1)
    {
        if (polygon2.containsPoint(point, Qt::OddEvenFill))
            return true;
        if (polygon2.containsPoint(point - QPoint(1, 1), Qt::OddEvenFill))
            return true;
    }
    foreach (const QPoint& point, polygon2)
    {
        if (polygon1.containsPoint(point, Qt::OddEvenFill))
            return true;
        if (polygon1.containsPoint(point - QPoint(1, 1), Qt::OddEvenFill))
            return true;
    }
    return false;
}

static Corner concaveTurnDirection(const QPoint& previous, const QPoint& current, const QPoint& next)
{
    if ((current.x() < previous.x()) && (current.y() < next.y()))
        return TopLeft;
    if ((current.y() < previous.y()) && (next.x() < current.x()))
        return TopRight;
    if ((previous.x() < current.x()) && (next.y() < current.y()))
        return BottomRight;
    if ((previous.y() < current.y()) && (current.x() < next.x()))
        return BottomLeft;
    return Invalid;
}

static Corner convexTurnDirection(const QPoint& previous, const QPoint& current, const QPoint& next)
{
    if ((current.y() < previous.y()) && (current.x() < next.x()))
        return BottomRight;
    if ((previous.x() < current.x()) && (current.y() < next.y()))
        return BottomLeft;
    if ((previous.y() < current.y()) && (next.x() < current.x()))
        return TopLeft;
    if ((current.x() < previous.x()) && (next.y() < current.y()))
        return TopRight;
    return Invalid;
}

template<typename T> static bool between(const T& middle, const T& end1, const T& end2)
{
    return (qMin(end1, end2) < middle) && (middle < qMax(end1, end2));
}

static CollisionInfo findCollisions(const QPolygon& polygon1, const QPolygon& polygon2)
{
    CollisionInfo data;
    QPoint prevPoint1 = polygon1[polygon1.size() - 2];
    QPoint point1 = polygon1.last();
    foreach (const QPoint& nextPoint1, polygon1)
    {
        QPoint prevPoint2 = polygon2.last();
        foreach (const QPoint& point2, polygon2)
        {
            if (point1 == prevPoint2)
            {
                QPoint nextPoint1 = polygon1[(polygon1.indexOf(point1) + 1) % polygon1.size()];
                Resolutions flags = 0;
                if (concaveTurnDirection(prevPoint1, point1, nextPoint1) != Invalid)
                    flags |= Delete;
                if (((point2.x() == prevPoint2.x()) && (prevPoint2.x() == nextPoint1.x())) || ((point2.y() == prevPoint2.y()) && (prevPoint2.y() == nextPoint1.y())))
                    flags |= Include;
                data[point1] = NextTarget(flags, point1);
                break;
            }
            else if ((((point2.x() == point1.x()) && between(point1.y(), prevPoint2.y(), point2.y())) || ((point2.y() == point1.y()) && between(point1.x(), prevPoint2.x(), point2.x()))))
            {
                data[point1] = NextTarget(Include, point2);
                break;
            }
            else if ((((point1.x() == prevPoint2.x()) && between(prevPoint2.y(), prevPoint1.y(), point1.y())) || ((point1.y() == prevPoint2.y()) && between(point1.x(), prevPoint1.x(), point1.x()))))
            {
                data[point1] = NextTarget(Include, polygon2[(polygon2.indexOf(prevPoint2) + polygon2.size() - 2) % polygon2.size()]);
                break;
            }
            prevPoint2 = point2;
        }
        point1 = nextPoint1;
        prevPoint1 = point1;
    }
    return data;
}

static QPoint findOuterPoint(const QPolygon& polygon)
{
    QPoint curPoint(INT_MAX, INT_MAX);
    foreach (const QPoint& point, polygon)
    {
        if (point < curPoint)
            curPoint = point;
    }
    return curPoint;
}

static QList<QPolygon> mergePolygons(QPolygon polygon1, QPolygon polygon2)
{
    QList<QPolygon> polygons;
    CollisionInfo cData1 = findCollisions(polygon1, polygon2);
    CollisionInfo cData2 = findCollisions(polygon2, polygon1);
    while (polygon1.size() || polygon2.size())
    {
        QPolygon polygon;
        QPolygon* curPolygon;
        QPolygon* otherPolygon;
        CollisionInfo* curData;
        CollisionInfo* otherData;
        const QPoint point1 = findOuterPoint(polygon1);
        const QPoint point2 = findOuterPoint(polygon2);
        QPoint curPoint;
        if (point1 < point2)
        {
            curPoint = point1;
            curPolygon = &polygon1;
            curData = &cData1;
            otherPolygon = &polygon2;
            otherData = &cData2;
        }
        else
        {
            curPoint = point2;
            curPolygon = &polygon2;
            curData = &cData2;
            otherPolygon = &polygon1;
            otherData = &cData1;
        }
        int curPos = curPolygon->indexOf(curPoint);
        while (true)
        {
            if (curData->contains(curPoint))
            {
                QPolygon* tempPolygon = curPolygon;
                curPolygon = otherPolygon;
                otherPolygon = tempPolygon;
                if (curData->value(curPoint).first & Delete)
                    otherPolygon->remove(curPos);
                else if (curData->value(curPoint).first & Include)
                    polygon.append(curPoint);
                curPos = curPolygon->indexOf(curData->value(curPoint).second);
                if (curData->value(curPoint).first & Delete)
                {
                    curPolygon->remove(curPos);
                    curPos %= curPolygon->size();
                }
                else if (!(curData->value(curPoint).first & Include))
                    curPos = (curPos + 1) % curPolygon->size();
                curData->remove(curPoint);
                curPoint = curPolygon->at(curPos);
                CollisionInfo* tempData = curData;
                curData = otherData;
                otherData = tempData;
            }
            if (!polygon.isEmpty() && (curPoint == polygon.first()))
                break;
            polygon.append(curPoint);
            curPos = (curPos + 1) % curPolygon->size();
            curPoint = curPolygon->at(curPos);
        }
        if (4 <= polygon.size())
            polygons.append(polygon);
        foreach (const QPoint& point, polygon)
        {
            const int pos1 = polygon1.indexOf(point);
            const int pos2 = polygon2.indexOf(point);
            if (0 <= pos1)
                polygon1.remove(pos1);
            if (0 <= pos2)
                polygon2.remove(pos2);
        }
        if ((polygon1.size() + polygon2.size()) < 4)
            break;
    }
    return polygons;
}

static const QRect& closer(const QRect& rect1, const QRect& rect2, const QPoint& point)
{
    if (rect1.isNull())
        return rect2;
    if (rect2.isNull())
        return rect1;
    const QPoint rect1Point = rect1.center() - point;
    const QPoint rect2Point = rect2.center() - point;
    const int rect1Dist = pow(rect1Point.x(), 2) + pow(rect1Point.y(), 2);
    const int rect2Dist = pow(rect2Point.x(), 2) + pow(rect2Point.y(), 2);
    return (rect1Dist < rect2Dist) ? rect1 : rect2;
}

static QPolygon collides(const QRectF& rect, const QList<QPolygon>& polygons)
{
    const QRect cRect = rect.toRect();
    foreach (const QPolygon& polygon, polygons)
    {
        QPolygon collides = polygon.intersected(cRect);
        if (!collides.isEmpty())
            return collides;
    }
    return QPolygon();
}

bool WorldMapPlacement::m_cacheGood = false;
QSize WorldMapPlacement::m_size;
QList<QPolygon> WorldMapPlacement::m_polygons;

WorldMapPlacement::WorldMapPlacement(const QSize& size)
{
    if (m_size != size)
    {
        m_cacheGood = false;
        m_size = size;
    }
}

void WorldMapPlacement::addRect(const QRectF& rect)
{
    if (m_cacheGood)
        return;
    QQueue<QRectF> queue;
    queue.enqueue(rect);
    while (queue.size())
    {
        QRectF newRect = queue.dequeue();
        bool collides = false;
        foreach (const QRectF& rect, m_rects)
        {
            if (rect.intersects(newRect))
            {
                collides = true;
                break;
            }
        }
        if (collides)
            continue;
        foreach (const QRectF& rect, m_rects)
        {
            if ((rect.left() < newRect.right()) && (newRect.left() < rect.right()))
            {
                const int left = qMax(rect.left(), newRect.left());
                const int right = qMin(rect.right(), newRect.right());
                if (newRect.bottom() < rect.top())
                {
                    if ((rect.top() - newRect.bottom()) < m_size.height())
                        queue.enqueue(QRectF(QPointF(left, newRect.bottom()), QPointF(right, rect.top())));
                }
                else if (rect.bottom() < newRect.top())
                {
                    if ((newRect.top() - rect.bottom()) < m_size.height())
                        queue.enqueue(QRectF(QPointF(left, rect.bottom()), QPointF(right, newRect.top())));
                }
            }
            else if ((rect.top() < newRect.bottom()) && (newRect.top() < rect.bottom()))
            {
                const int top = qMax(rect.top(), newRect.top());
                const int bottom = qMin(rect.bottom(), newRect.bottom());
                if (rect.right() < newRect.left())
                {
                    if ((newRect.left() - rect.right()) < m_size.width())
                        queue.enqueue(QRectF(QPointF(rect.right(), top), QPointF(newRect.left(), bottom)));
                }
                else if (newRect.right() < rect.left())
                {
                    if ((rect.left() - newRect.right()) < m_size.width())
                        queue.enqueue(QRectF(QPointF(newRect.right(), top), QPointF(rect.left(), bottom)));
                }
            }
        }
        m_rects.append(newRect.toRect());
    }
}

QPoint WorldMapPlacement::find(const QPoint& point)
{
    if (!m_cacheGood)
        finalize();
    QRect best;
    foreach (const QPolygon& polygon, m_polygons)
    {
        for (int i = 0; i < polygon.size(); ++i)
        {
            const QPoint last = polygon[(i + polygon.size() - 1) % polygon.size()];
            const QPoint cur = polygon[i];
            const QPoint next = polygon[(i + 1) % polygon.size()];
            QRectF rect(QPoint(), m_size);
            if (between(point.x(), cur.x(), last.x()))
            {
                rect.moveCenter(QPointF(point.x(), cur.y() + ((((point.y() < cur.y()) ? 1 : -1) * m_size.height()) / 2.)));
                QRectF collidingRect = collides(rect, m_polygons).boundingRect();
                if (collidingRect.isNull())
                    best = closer(best, rect.toRect(), point);
                else
                {
                    const qreal top = collidingRect.top();
                    const qreal bottom = collidingRect.bottom();
                    rect.moveBottom(top);
                    collidingRect = collides(rect, m_polygons).boundingRect();
                    if (collidingRect.isNull())
                        best = closer(best, rect.toRect(), point);
                    rect.moveTop(bottom);
                    collidingRect = collides(rect, m_polygons).boundingRect();
                    if (collidingRect.isNull())
                        best = closer(best, rect.toRect(), point);
                }
            }
            else if (between(point.y(), cur.y(), last.y()))
            {
                rect.moveCenter(QPointF(cur.x() + ((((point.x() < cur.x()) ? 1 : -1) * m_size.width()) / 2.), point.y()));
                QRectF collidingRect = collides(rect, m_polygons).boundingRect();
                if (collidingRect.isNull())
                    best = closer(best, rect.toRect(), point);
                else
                {
                    const qreal left = collidingRect.left();
                    const qreal right = collidingRect.right();
                    rect.moveRight(left);
                    collidingRect = collides(rect, m_polygons).boundingRect();
                    if (collidingRect.isNull())
                        best = closer(best, rect.toRect(), point);
                    rect.moveLeft(right);
                    collidingRect = collides(rect, m_polygons).boundingRect();
                    if (collidingRect.isNull())
                        best = closer(best, rect.toRect(), point);
                }
            }
            const Corner corner = qMax(concaveTurnDirection(last, cur, next), convexTurnDirection(last, cur, next));
            switch (corner)
            {
                case TopLeft:
                    rect.moveTopLeft(cur);
                    break;
                case TopRight:
                    rect.moveTopRight(cur);
                    break;
                case BottomRight:
                    rect.moveBottomRight(cur);
                    break;
                case BottomLeft:
                    rect.moveBottomLeft(cur);
                    break;
                default:
                    break;
            }
            if (collides(rect, m_polygons).isEmpty())
                best = closer(best, rect.toRect(), point);
        }
    }
    return best.topLeft();
}

void WorldMapPlacement::invalidateCache()
{
    m_cacheGood = false;
    m_polygons.clear();
}

void WorldMapPlacement::finalize()
{
    if (m_cacheGood)
        return;
    qSort(m_rects);
    QList<QBitArray> conns;
    for (int i = 0; i < m_rects.size(); ++i)
    {
        QBitArray arr(m_rects.size());
        arr.setBit(i);
        conns.append(arr);
    }
    for (int i = 0; i < m_rects.size(); ++i)
    {
        for (int j = 0; j < m_rects.size(); ++j)
        {
            if (touches(m_rects[i], m_rects[j]))
            {
                for (int k = 0; k < m_rects.size(); ++k)
                {
                    if (conns[i][k])
                    {
                        conns[k] |= conns[j];
                        conns[j] |= conns[k];
                    }
                    if (conns[j][k])
                    {
                        conns[k] |= conns[i];
                        conns[i] |= conns[k];
                    }
                }
            }
        }
    }
    QSet<QBitArray> uniqConns = QSet<QBitArray>::fromList(conns);
    foreach (const QBitArray& array, uniqConns)
    {
        QPolygon polygon;
        for (int i = 0; i < m_rects.size(); ++i)
        {
            if (array[i])
            {
                if (polygon.isEmpty())
                    polygon = m_rects[i];
                else
                {
                    QList<QPolygon> polygons = mergePolygons(polygon, m_rects[i]);
                    polygon = polygons.takeFirst();
                    m_polygons += polygons;
                }
            }
        }
        m_polygons.append(polygon);
    }
    m_cacheGood = true;
}