insilmaril@650: #include "geometry.h" insilmaril@650: insilmaril@656: #include insilmaril@662: #include insilmaril@662: #include "misc.h" insilmaril@656: insilmaril@662: using namespace std; insilmaril@650: insilmaril@650: QRectF addBBox(QRectF r1, QRectF r2) insilmaril@650: { insilmaril@650: // Find smallest QRectF containing given rectangles insilmaril@650: insilmaril@650: QRectF n; insilmaril@650: // Set left border insilmaril@650: if (r1.left() <= r2.left() ) insilmaril@650: n.setLeft(r1.left() ); insilmaril@650: else insilmaril@650: n.setLeft(r2.left() ); insilmaril@650: insilmaril@650: // Set top border insilmaril@650: if (r1.top() <= r2.top() ) insilmaril@650: n.setTop(r1.top() ); insilmaril@650: else insilmaril@650: n.setTop(r2.top() ); insilmaril@650: insilmaril@650: // Set right border insilmaril@650: if (r1.right() <= r2.right() ) insilmaril@650: n.setRight(r2.right() ); insilmaril@650: else insilmaril@650: n.setRight(r1.right() ); insilmaril@650: insilmaril@650: // Set bottom insilmaril@650: if (r1.bottom() <= r2.bottom() ) insilmaril@650: n.setBottom(r2.bottom() ); insilmaril@650: else insilmaril@650: n.setBottom(r1.bottom() ); insilmaril@650: return n; insilmaril@650: } insilmaril@650: insilmaril@650: bool inBox(const QPointF &p, const QRectF &box) insilmaril@650: { insilmaril@650: if (p.x() >= box.left() && p.x() <= box.right() insilmaril@650: && p.y() <= box.bottom() && p.y() >= box.top() ) insilmaril@650: return true; insilmaril@650: return false; insilmaril@650: } insilmaril@656: insilmaril@656: QPointF normalize (const QPointF &p) insilmaril@656: { insilmaril@662: if (p==QPointF(0,0)) return p; insilmaril@662: qreal l=sqrt ( p.x()*p.x() + p.y()*p.y() ); insilmaril@662: return QPointF (p.x()/l,p.y()/l); insilmaril@656: } insilmaril@656: insilmaril@656: // Dot product of two vectors insilmaril@656: qreal dotProduct (const QPointF &a, const QPointF &b) insilmaril@656: { insilmaril@656: return a.x()*b.x() + a.y()*b.y(); insilmaril@656: } insilmaril@656: insilmaril@656: insilmaril@656: /* Calculate the projection of a polygon on an axis insilmaril@656: and returns it as a [min, max] interval insilmaril@656: */ insilmaril@656: void ProjectPolygon(QPointF axis, QPolygonF polygon, qreal &min, qreal &max) insilmaril@656: { insilmaril@656: // To project a point on an axis use the dot product insilmaril@656: insilmaril@656: qreal d = dotProduct(axis,polygon.at(0)); insilmaril@656: min = d; insilmaril@656: max = d; insilmaril@656: for (int i = 0; i < polygon.size(); i++) { insilmaril@656: d= dotProduct (polygon.at(i),axis); insilmaril@656: if (d < min) insilmaril@656: min = d; insilmaril@656: else insilmaril@656: { insilmaril@656: if (d> max) max = d; insilmaril@656: } insilmaril@656: } insilmaril@656: } insilmaril@656: insilmaril@656: /* Calculate the signed distance between [minA, maxA] and [minB, maxB] insilmaril@656: The distance will be negative if the intervals overlap insilmaril@656: */ insilmaril@656: insilmaril@656: insilmaril@656: qreal intervalDistance(qreal minA, qreal maxA, qreal minB, qreal maxB) { insilmaril@656: if (minA < minB) { insilmaril@656: return minB - maxA; insilmaril@656: } else { insilmaril@656: return minA - maxB; insilmaril@656: } insilmaril@656: } insilmaril@656: /* insilmaril@656: Check if polygon A is going to collide with polygon B. insilmaril@656: The last parameter is the *relative* velocity insilmaril@656: of the polygons (i.e. velocityA - velocityB) insilmaril@656: insilmaril@656: */ insilmaril@656: PolygonCollisionResult PolygonCollision(QPolygonF polygonA, insilmaril@656: QPolygonF polygonB, QPointF velocity) { insilmaril@656: PolygonCollisionResult result; insilmaril@662: result.intersect = true; insilmaril@662: result.willIntersect = true; insilmaril@656: insilmaril@656: int edgeCountA = polygonA.size(); insilmaril@656: int edgeCountB = polygonB.size(); insilmaril@656: qreal minIntervalDistance = 1000000000; insilmaril@656: QPointF translationAxis; insilmaril@656: QPointF edge; insilmaril@656: insilmaril@662: cout << "\nA: "; insilmaril@662: for (int k=0; k 0) insilmaril@662: result.intersect = false; insilmaril@662: else insilmaril@662: result.intersect = true; insilmaril@656: insilmaril@656: // ===== 2. Now find if the polygons *will* intersect ===== insilmaril@656: insilmaril@656: insilmaril@656: // Project the velocity on the current axis insilmaril@656: insilmaril@656: qreal velocityProjection = dotProduct(axis,velocity); insilmaril@656: insilmaril@656: // Get the projection of polygon A during the movement insilmaril@656: insilmaril@662: if (velocityProjection < 0) insilmaril@656: minA += velocityProjection; insilmaril@662: else insilmaril@656: maxA += velocityProjection; insilmaril@662: insilmaril@656: insilmaril@656: // Do the same test as above for the new projection insilmaril@656: insilmaril@656: qreal d = intervalDistance(minA, maxA, minB, maxB); insilmaril@662: if (d > 0) result.willIntersect = false; insilmaril@662: /* insilmaril@662: */ insilmaril@662: cout <<" "; insilmaril@662: cout <<"minA="<