# 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 <math.h>
+
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 <QPointF>
#include <QRectF>
+#include <QPolygonF>
QRectF addBBox(QRectF r1, QRectF r2);
bool inBox(const QPointF &p, const QRectF &box);
+QPointF normalize (const QPointF &p);
#endif