insilmaril@650: #include "geometry.h"
insilmaril@650: 
insilmaril@656: #include <math.h>
insilmaril@656: 
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@656: 	qreal n=sqrt ( p.x()*p.x() + p.y()*p.y() );
insilmaril@656: 	return QPointF (p.x()/n,p.y()/n);
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: // Structure that stores the results of the PolygonCollision function
insilmaril@656: class PolygonCollisionResult {
insilmaril@656: public:
insilmaril@656:     // Are the polygons going to intersect forward in time?
insilmaril@656:     bool WillIntersect;
insilmaril@656: 
insilmaril@656:     // Are the polygons currently intersecting?
insilmaril@656:     bool Intersect;
insilmaril@656: 
insilmaril@656:     // The translation to apply to the first polygon to push the polygons apart.
insilmaril@656:     QPointF MinimumTranslationVector;
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@656:     result.Intersect = true;
insilmaril@656:     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@656:     // Loop through all the edges of both polygons
insilmaril@656: 
insilmaril@656:     for (int i=0; i < edgeCountA + edgeCountB; i++) 
insilmaril@656: 	{
insilmaril@656:         if (i< edgeCountA) 
insilmaril@656:             edge = polygonA.at(i);
insilmaril@656:         else 
insilmaril@656:             edge = polygonB.at(i - edgeCountA);
insilmaril@656: 
insilmaril@656:         // ===== 1. Find if the polygons are currently intersecting =====
insilmaril@656: 
insilmaril@656: 
insilmaril@656:         // Find the axis perpendicular to the current edge
insilmaril@656: 
insilmaril@656:         QPointF axis (-edge.y(), edge.x());
insilmaril@656:         normalize(axis);
insilmaril@656: 
insilmaril@656:         // Find the projection of the polygon on the current axis
insilmaril@656: 
insilmaril@656:         qreal minA = 0; qreal minB = 0; qreal maxA = 0; qreal maxB = 0;
insilmaril@656:         ProjectPolygon(axis, polygonA, minA, maxA);
insilmaril@656:         ProjectPolygon(axis, polygonB, minB, maxB);
insilmaril@656: 
insilmaril@656:         // Check if the polygon projections are currentlty intersecting
insilmaril@656: 
insilmaril@656:         if (intervalDistance(minA, maxA, minB, maxB) > 0)\
insilmaril@656:             result.Intersect = false;
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@656:         if (velocityProjection < 0) {
insilmaril@656:             minA += velocityProjection;
insilmaril@656:         } else {
insilmaril@656:             maxA += velocityProjection;
insilmaril@656:         }
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@656:         if (d > 0) result.WillIntersect = false;
insilmaril@656: 
insilmaril@656:         // If the polygons are not intersecting and won't intersect, exit the loop
insilmaril@656: 
insilmaril@656:         if (!result.Intersect && !result.WillIntersect) break;
insilmaril@656: 
insilmaril@656:         // Check if the current interval distance is the minimum one. If so store
insilmaril@656:         // the interval distance and the current distance.
insilmaril@656:         // This will be used to calculate the minimum translation vector
insilmaril@656: 
insilmaril@656:         if (d<0) d=-d;
insilmaril@656:         if (d < minIntervalDistance) {
insilmaril@656:             minIntervalDistance = d;
insilmaril@656:             translationAxis = axis;
insilmaril@656: 
insilmaril@656:             //QPointF t = polygonA.Center - polygonB.Center;
insilmaril@656:             QPointF t = polygonA.at(0) - polygonB.at(0);
insilmaril@656:             if (dotProduct(t,translationAxis) < 0)
insilmaril@656:                 translationAxis = -translationAxis;
insilmaril@656:         }
insilmaril@656:     }
insilmaril@656: 
insilmaril@656:     // The minimum translation vector
insilmaril@656:     // can be used to push the polygons appart.
insilmaril@656: 
insilmaril@656:     if (result.WillIntersect)
insilmaril@656:         result.MinimumTranslationVector = 
insilmaril@656:                translationAxis * minIntervalDistance;
insilmaril@656:     
insilmaril@656:     return result;
insilmaril@656: }
insilmaril@656: 
insilmaril@656: /* The function can be used this way: 
insilmaril@656:    QPointF polygonATranslation = new QPointF();
insilmaril@656: */   
insilmaril@656: 
insilmaril@656: 
insilmaril@656: /*
insilmaril@656: PolygonCollisionResult r = PolygonCollision(polygonA, polygonB, velocity);
insilmaril@656: 
insilmaril@656: if (r.WillIntersect) 
insilmaril@656:   // Move the polygon by its velocity, then move
insilmaril@656:   // the polygons appart using the Minimum Translation Vector
insilmaril@656:   polygonATranslation = velocity + r.MinimumTranslationVector;
insilmaril@656: else 
insilmaril@656:   // Just move the polygon by its velocity
insilmaril@656:   polygonATranslation = velocity;
insilmaril@656: 
insilmaril@656: polygonA.Offset(polygonATranslation);
insilmaril@656: 
insilmaril@656: */
insilmaril@656: 
insilmaril@656: