# HG changeset patch # User insilmaril # Date 1200498319 0 # Node ID 53ef954e90b6a08d1b6a7cb6b1450e2398546964 # Parent d4b49c6c60699127487fbdcb59fe3e0da6b4e379 Fixed missing MapCenter diff -r d4b49c6c6069 -r 53ef954e90b6 geometry.cpp --- a/geometry.cpp Wed Jan 16 15:45:19 2008 +0000 +++ b/geometry.cpp Wed Jan 16 15:45:19 2008 +0000 @@ -1,5 +1,7 @@ #include "geometry.h" +#include + QRectF addBBox(QRectF r1, QRectF r2) { @@ -39,3 +41,180 @@ return true; return false; } + +QPointF normalize (const QPointF &p) +{ + qreal n=sqrt ( p.x()*p.x() + p.y()*p.y() ); + return QPointF (p.x()/n,p.y()/n); +} + +// Dot product of two vectors +qreal dotProduct (const QPointF &a, const QPointF &b) +{ + return a.x()*b.x() + a.y()*b.y(); +} + +// Structure that stores the results of the PolygonCollision function +class PolygonCollisionResult { +public: + // Are the polygons going to intersect forward in time? + bool WillIntersect; + + // Are the polygons currently intersecting? + bool Intersect; + + // The translation to apply to the first polygon to push the polygons apart. + QPointF MinimumTranslationVector; +}; + + +/* Calculate the projection of a polygon on an axis + and returns it as a [min, max] interval +*/ +void ProjectPolygon(QPointF axis, QPolygonF polygon, qreal &min, qreal &max) +{ + // To project a point on an axis use the dot product + + qreal d = dotProduct(axis,polygon.at(0)); + min = d; + max = d; + for (int i = 0; i < polygon.size(); i++) { + d= dotProduct (polygon.at(i),axis); + if (d < min) + min = d; + else + { + if (d> max) max = d; + } + } +} + +/* Calculate the signed distance between [minA, maxA] and [minB, maxB] + The distance will be negative if the intervals overlap +*/ + + +qreal intervalDistance(qreal minA, qreal maxA, qreal minB, qreal maxB) { + if (minA < minB) { + return minB - maxA; + } else { + return minA - maxB; + } +} +/* + Check if polygon A is going to collide with polygon B. + The last parameter is the *relative* velocity + of the polygons (i.e. velocityA - velocityB) + +*/ +PolygonCollisionResult PolygonCollision(QPolygonF polygonA, + QPolygonF polygonB, QPointF velocity) { + PolygonCollisionResult result; + result.Intersect = true; + result.WillIntersect = true; + + int edgeCountA = polygonA.size(); + int edgeCountB = polygonB.size(); + qreal minIntervalDistance = 1000000000; + QPointF translationAxis; + QPointF edge; + + // Loop through all the edges of both polygons + + for (int i=0; i < edgeCountA + edgeCountB; i++) + { + if (i< edgeCountA) + edge = polygonA.at(i); + else + edge = polygonB.at(i - edgeCountA); + + // ===== 1. Find if the polygons are currently intersecting ===== + + + // Find the axis perpendicular to the current edge + + QPointF axis (-edge.y(), edge.x()); + normalize(axis); + + // Find the projection of the polygon on the current axis + + qreal minA = 0; qreal minB = 0; qreal maxA = 0; qreal maxB = 0; + ProjectPolygon(axis, polygonA, minA, maxA); + ProjectPolygon(axis, polygonB, minB, maxB); + + // Check if the polygon projections are currentlty intersecting + + if (intervalDistance(minA, maxA, minB, maxB) > 0)\ + result.Intersect = false; + + // ===== 2. Now find if the polygons *will* intersect ===== + + + // Project the velocity on the current axis + + qreal velocityProjection = dotProduct(axis,velocity); + + // Get the projection of polygon A during the movement + + if (velocityProjection < 0) { + minA += velocityProjection; + } else { + maxA += velocityProjection; + } + + // Do the same test as above for the new projection + + qreal d = intervalDistance(minA, maxA, minB, maxB); + if (d > 0) result.WillIntersect = false; + + // If the polygons are not intersecting and won't intersect, exit the loop + + if (!result.Intersect && !result.WillIntersect) break; + + // Check if the current interval distance is the minimum one. If so store + // the interval distance and the current distance. + // This will be used to calculate the minimum translation vector + + if (d<0) d=-d; + if (d < minIntervalDistance) { + minIntervalDistance = d; + translationAxis = axis; + + //QPointF t = polygonA.Center - polygonB.Center; + QPointF t = polygonA.at(0) - polygonB.at(0); + if (dotProduct(t,translationAxis) < 0) + translationAxis = -translationAxis; + } + } + + // The minimum translation vector + // can be used to push the polygons appart. + + if (result.WillIntersect) + result.MinimumTranslationVector = + translationAxis * minIntervalDistance; + + return result; +} + +/* The function can be used this way: + QPointF polygonATranslation = new QPointF(); +*/ + + +/* +PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity); + +if (r.WillIntersect) + // Move the polygon by its velocity, then move + // the polygons appart using the Minimum Translation Vector + polygonATranslation = velocity + r.MinimumTranslationVector; +else + // Just move the polygon by its velocity + polygonATranslation = velocity; + +polygonA.Offset(polygonATranslation); + +*/ + + diff -r d4b49c6c6069 -r 53ef954e90b6 geometry.h --- a/geometry.h Wed Jan 16 15:45:19 2008 +0000 +++ b/geometry.h Wed Jan 16 15:45:19 2008 +0000 @@ -1,10 +1,13 @@ #ifndef GEOMETRY_H #define GEOMETRY_H +#include #include +#include QRectF addBBox(QRectF r1, QRectF r2); bool inBox(const QPointF &p, const QRectF &box); +QPointF normalize (const QPointF &p); #endif