Java 2d polygon collision response

Question

I made a game that uses convex polygons. My plan is to have these polygons collide and bounce off according to their masses and velocities. But first I need to make sure they aren't overlapping. This code checks every edge of polygon A to see if any of Polygon B's vertices are overlapping on an axis perpendicular to the edge. The whole method returns the resulting Vector needed to fix Polygon A:

    /**Calculates adjustment vector for EntityPolygon A*/
public Vector calculateCollision(EntityPolygon A, EntityPolygon B) {

    //this is a large number so the first comparison of overlap is true
    double overlap = 10000;

            //this is the angle of the axis to apply the overlap vector
    double angle = 0;

            //I ran a for loop for every edge of the polygon
    for(int x = 0; x <= A.numPoint - 1; x++) {

                    //create variables
        Vector edge;
        Vector axis;
        double centerA;
        double centerB;
        double maxA;
        double maxB;
        double minA;
        double minB;

                    //this if statement finds this point and the next point
                    //to make a Vector of the edge
        if(x != A.numPoint - 1) {
            edge = new Vector(A.point[x], A.point[x + 1]);
        } else {
            edge = new Vector(A.point[x], A.point[0]);
        }

                    //this finds the axis perpendicular axis of the edge
        axis = edge.getRightNormal();

        //finds the location of both polygon's centers when projected onto
                    //the velocity(projectionOnVelocity() projects the point on the                                                           
                    //new axis)
        centerA = A.getLocation().getProjectionOnVelocity(axis);
        centerB = B.getLocation().getProjectionOnVelocity(axis);

                    //finds the location of polygons A and B on the axis by
                    //setting the min and max of their highest and lowest points
        maxA = findMax(A, axis);
        maxB = findMax(B, axis);
        minA = findMin(A, axis);
        minB = findMin(B,axis);

        //final comparison to find overlapping vector.
        if(centerA > centerB) {//if A is above B on the axis
            if(maxB > minA) {//if the max point on B is above min on A
                double m = maxB - minA;
                if(m < overlap) {
                    overlap = m;
                    angle = axis.angle;
                }
            } else {
                                    //(0,0) vector
                return Vector.getDefault();
            }
        } else if(centerB > centerA) {//if B is above A on axis
            if(maxA > minB) {//if the max point on A is above min on B
                double m = maxA - minB;
                if(m < overlap) {
                    overlap = m;
                    angle = axis.angle + Math.PI;
                }
            } else {
                                    //(0,0) vector
                return Vector.getDefault();
            }
        }
    }
            //if the overlap value has been set by the edges of Polygon A
    if(overlap != 10000) {
                    //returns the adjustment vector along overlap edge axis
        return new Vector(angle, overlap, true);
    } else {
                    (0,0) vector
        return Vector.getDefault();
    }
}

This code has a bug that causes problems in a situation where a very flat piece is above a square piece, the flat piece believes it goes much farther down than it really is. As a result, the flat piece and the square piece collide, pushing them to their current positions in the picture below

This is a picture of the actual game in the preliminary stages. The blue square to the right has been moved by the block barrier at the top before they even touch. This happens at the beginning of the program, when the square is at the very left side of the screen.

It looks as if your algorithm is just wrong. It would be easier to explain if you gave us some numbers for your example case. — Beta, Jul 25 '12 at 00:49

score 0 · Answer 1 · edited May 23 '17 at 12:12

I agree with Beta, your algorithm doesn't look right (mainly because I'm pretty sure polygon intersection cannot be that easy. Just for checking intersection of 2 shapes (without any intelligence), you'd have to check if any edge intersects with any edge of the other shape, but this is slow even with moderately simple shapes.

Rectangle intersection is quite easy to do, triangle intersection shouldn't be too difficult, if you can split your shape into one of those (or really any set of shapes that has a reasonably simple formula) it would make things much easier.

You can also check this question out.

Polygon intersection is a well-studied problem, just Google it and you should get quite a few options.

Java 2d polygon collision response

1 Answers1