if (any point falls outside the border){collision has occurred}

// All objects which can collide have a collision package.
// Asteroids, ship, bullets. The structure seems like slight
// overkill for bullets but it keeps the code generic,
// and the use of vertexListLength means there isn't any
// actual speed overhead. Also if we wanted line, triangle or
// even spinning bullets the code wouldn't need to change.

public class CollisionPackage {

    // All the members are public to avoid multiple calls
    // to getters and setters.

    // The facing angle allows us to calculate the
    // current world coordinates of each vertex using
    // the model-space coordinates in vertexList.
    public float facingAngle;

    // The model-space coordinates
    public PointF[] vertexList;

    /* 
    The number of vertices in vertexList
    is kept in this next int because it is pre-calculated
    and we can use it in our loops instead of
    continually calling vertexList.length.
   */
    public int vertexListLength;

    // Where is the centre of the object?
    public PointF worldLocation;

    /* 
    This next float will be used to detect if the circle shaped
    hitboxes collide. It represents the furthest point
    from the centre of any given object.
    Each object will set this slightly differently.
    The ship will use height/2 an asteroid will use 25
    To allow for a max length rotated coordinate.
   */
    public float radius;

    // A couple of points to store results and avoid creating new
    // objects during intensive collision detection
    public PointF currentPoint = new PointF();
    public PointF currentPoint2 = new PointF();

public CollisionPackage(PointF[] vertexList, PointF worldLocation, 
  float radius, float facingAngle){ 

        vertexListLength = vertexList.length;
        this.vertexList = new PointF[vertexListLength];
        // Make a copy of the array

        for (int i = 0; i < vertexListLength; i++) {
            this.vertexList[i] = new PointF();
            this.vertexList[i].x = vertexList[i].x;
            this.vertexList[i].y = vertexList[i].y;
        }

        this.worldLocation = new PointF();
        this.worldLocation = worldLocation;

        this.radius = radius;

        this.facingAngle = facingAngle;

    }

}

CollisionPackage cp;

// Initialize the collision package
// (the object space vertex list, x any world location
// the largest possible radius, facingAngle)

// First, build a one element array
PointF point = new PointF(0,0);
PointF[] points = new PointF[1];
points[0] = point;

// 1.0f is an approximate representation 
//of the size of a bullet
cp = new CollisionPackage(points, getWorldLocation(),
1.0f, getFacingAngle());

        move(fps);

 // Update the collision package
 cp.facingAngle = getFacingAngle();
 cp.worldLocation = getWorldLocation();

CollisionPackage cp;

// Next, a 2d representation using PointF of
// the vertices. Used to build shipVertices
// and to pass to the CollisionPackage constructor
PointF[] points;

setVertices(shipVertices);

// Initialize the collision package
// (the object space vertex list, x any world location
// the largest possible radius, facingAngle)

points = new PointF[6];
points[0] = new PointF(- halfW, - halfL);

points[2] = new PointF(halfW, - halfL);
points[4] = new PointF(0, 0 + halfL);

// To make collision detection more accurate we will define some
// more points on the midpoints of all our sides.
// It is possible that the point of an asteroid will pass through
// the side of the ship and we do not test for this!
// We only test for the point of a ship 
// passing through the side of an asteroid!!
// This is computationally cheaper than running both tests.
// Although not as accurate we will see it is very close.
// We can think of this visually as 
// adding extra sensors on the sides of our ship
// Here we use an equation to find the midpoint 
// of a line which you can find an explanation of
// on most good high school math web sites.

points[1] = new PointF(points[0].x + 
 points[2].x/2,(points[0].y + points[2].y)/2);

points[3] = new PointF((points[2].x + points[4].x)/2,
 (points[2].y + points[4].y)/2);

points[5] = new PointF((points[4].x + points[0].x)/2,
 (points[4].y + points[0].y)/2);

cp = new CollisionPackage(points, getWorldLocation(), 
 length/2, getFacingAngle());

}// End SpaceShip constructor

move(fps);

 // Update the collision package
 cp.facingAngle = getFacingAngle();
 cp.worldLocation = getWorldLocation();

}// End SpaceShip update()

CollisionPackage cp;

// Define a random asteroid shape
// Then call the parent setVertices()
generatePoints();

// Initialize the collision package
// (the object space vertex list, x any world location
// the largest possible radius, facingAngle)
cp = new CollisionPackage
 (points, getWorldLocation(), 25, getFacingAngle());

public void bounce(){

  // Reverse the travelling angle
    if(getTravellingAngle() >= 180){
      setTravellingAngle(getTravellingAngle()-180);
     }else{
      setTravellingAngle(getTravellingAngle() + 180);
    }

    // Reverse velocity because occasionally they get stuck
    setWorldLocation((getWorldLocation().x + -getxVelocity()/3), (getWorldLocation().y + -getyVelocity()/3));

    // Speed up by 10%
    setSpeed(getSpeed() * 1.1f);

    // Not too fast though
    if(getSpeed() > getMaxSpeed()){
      setSpeed(getMaxSpeed());

}

move(fps);

// Update the collision package
cp.facingAngle = getFacingAngle();
cp.worldLocation = getWorldLocation();

}

// left below 0
points[5] = new PointF();
i = -(r.nextInt(14)+11);
points[5].x =  i;
i = -(r.nextInt(12)+1);

points[5].y = i;

// We add on an extra point that we won't use in asteroidVertices[].
// The point is the same as the first. 
// This is because the last vertex
// links back to the first to create a line. 
// This line will need to be
// used in calculations when we do our collision detection.

// Here is the extra vertex- same as the first.
points[6] = new PointF();
points[6].x = points[0].x;
points[6].x = points[0].x;

// Now use these points to draw our asteroid
float[] asteroidVertices = new float[]{
// First point to second point
points[0].x, points[0].y, 0,
points[1].x, points[1].y, 0,

private static PointF rotatedPoint = new PointF();

public static boolean detect(CollisionPackage cp1, 
    CollisionPackage cp2) {

    boolean collided = false;

   // Check circle collision between the two objects

   // Get the distance of the two objects from
   // the centre of the circles on the x axis
   float distanceX = (cp1.worldLocation.x)
        - (cp2.worldLocation.x);

   // Get the distance of the two objects from
   // the centre of the circles on the y axis
   float distanceY = (cp1.worldLocation.y)
        - (cp2.worldLocation.y);

        // Calculate the distance between the center of each circle
        double distance = Math.sqrt
            (distanceX * distanceX + distanceY * distanceY);

        // Finally see if the two circles overlap
        // If they do it is worth doing the more intensive
        // and accurate check.
        if (distance < cp1.radius + cp2.radius) {

         // Log.e("Circle collision:","true");
         // todo  Eventually we will add the 
         // more accurate code here
         // todo and delete the line below.

            collided = true;
        }

        return collided;
    }

// Check if anything hits the border
public static boolean contain(float mapWidth, float mapHeight,                                              
  CollisionPackage cp) {

   boolean possibleCollision = false;

    // Check if any corner of a virtual rectangle
    // around the centre of the object is out of bounds.
    // Rectangle is best because we are testing 
    // against straight sides (the border)
    // If it is we have a possible collision.

    if (cp.worldLocation.x - cp.radius < 0) {
            possibleCollision = true;
        } else if (cp.worldLocation.x + cp.radius > mapWidth) {
            possibleCollision = true;
        } else if (cp.worldLocation.y - cp.radius < 0) {
            possibleCollision = true;
        } else if (cp.worldLocation.y + cp.radius > mapHeight) {
            possibleCollision = true;
        }

        if (possibleCollision) {
            // todo For now we return true
            return true;
        }

        return false; // No collision
}

public void lifeLost(){
        // Reset the ship to the center
        gm.ship.setWorldLocation(gm.mapWidth/2, gm.mapHeight/2);
        // Play a sound
        sm.playSound("shipexplode");

        // Deduct a life
        gm.numLives = gm.numLives -1;

        if(gm.numLives == 0){
            gm.levelNumber = 1;
            gm.numLives = 3;
            createObjects();
            gm.switchPlayingStatus();
            sm.playSound("gameover");
        }
    }

public void destroyAsteroid(int asteroidIndex){

  gm.asteroids[asteroidIndex].setActive(false);
     // Play a sound
     sm.playSound("explode");
     // Reduce the number of active asteroids
     gm.numAsteroidsRemaining --;

     // Has the player cleared them all?
     if(gm.numAsteroidsRemaining == 0){
     // Play a victory sound

     // Increment the level number
     gm.levelNumber ++ ;

     // Extra life
     gm.numLives ++ ;

     sm.playSound("nextlevel");
     // Respawn everything
     // With more asteroids
     createObjects();

}
}
}// End class

// End of all updates!!

// All objects are in their new locations
// Start collision detection

// Check if the ship needs containing
if (CD.contain(gm.mapWidth, gm.mapHeight, gm.ship.cp)) {

  lifeLost();

}

// Check if an asteroid needs containing
for (int i = 0; i < gm.numAsteroids; i++) {
  if (gm.asteroids[i].isActive()) {
       if (CD.contain(gm.mapWidth, gm.mapHeight, 
       gm.asteroids[i].cp)) {

          // Bounce the asteroid back into the game
          gm.asteroids[i].bounce();

          // Play a sound
          sm.playSound("blip");

       }
    }

}

// Check if bullet needs containing
// But first see if the bullet is out of sight
// If it is reset it to make game harder
for (int i = 0; i < gm.numBullets; i++) {

    // Is the bullet in flight?
    if (gm.bullets[i].isInFlight()) {

   // Comment the next block to make the game easier!!!
   // It will allow the bullets to go all the way from
   // ship to border without being reset. 
   // These lines reset the bullet when
   // shortly after they leave the players view.
   // This forces the player to go 'hunting' for the
   // asteroids instead of spinning round spamming the
   // fire button...
   // This code would be better with a viewport.clip() method
   // like in project 2 but seems a bit excessive just for these
   // few 15ish lines of code.

   // Start comment out to make easier
   handyPointF = gm.bullets[i].getWorldLocation();
   handyPointF2 = gm.ship.getWorldLocation();

   if(handyPointF.x > handyPointF2.x + gm.metresToShowX / 2){
        // Reset the bullet
        gm.bullets[i].resetBullet(gm.ship.getWorldLocation());

    }else
        if(handyPointF.x < handyPointF2.x - gm.metresToShowX / 2){
            // Reset the bullet
            gm.bullets[i].resetBullet(gm.ship.getWorldLocation());

        }else
        if(handyPointF.y > handyPointF2.y + gm.metresToShowY/ 2){
            // Reset the bullet
            gm.bullets[i].resetBullet(gm.ship.getWorldLocation());
       }else
        if(handyPointF.y < handyPointF2.y - gm.metresToShowY / 2){
            // Reset the bullet
            gm.bullets[i].resetBullet(gm.ship.getWorldLocation());
                }
            // End comment out to make easier

            // Does bullet need containing?
            if (CD.contain(gm.mapWidth, gm.mapHeight,      
                gm.bullets[i].cp)) {

                 // Reset the bullet
                 gm.bullets[i].resetBullet
                    (gm.ship.getWorldLocation());
                 // Play a sound
                 sm.playSound("ricochet");
          }

     }

}

// Now we see if anything has hit an asteroid

// Check collisions between asteroids and bullets
// Loop through each bullet and asteroid in turn

for (int bulletNum = 0; bulletNum < gm.numBullets; bulletNum++) {
    for (int asteroidNum = 0; asteroidNum < gm.numAsteroids;                            
        asteroidNum++) {

        // Check that the current bullet is in flight
        // and the current asteroid is 
        // active before proceeding
        if (gm.bullets[bulletNum].isInFlight() &&                                           
            gm.asteroids[asteroidNum].isActive())

            // Perform the collision checks by 
            // passing in the collision packages

            // A Bullet only has one vertex. 
            // Our collision detection works on vertex pairs

          if (CD.detect(gm.bullets[bulletNum].cp,                                           
              gm.asteroids[asteroidNum].cp)) {

                // If we get a hit...
                destroyAsteroid(asteroidNum);

                // Reset the bullet
                gm.bullets[bulletNum].resetBullet
                    (gm.ship.getWorldLocation());
           }

    }
}

// Check collisions between asteroids and ship
// Loop through each asteroid in turn

for (int asteroidNum = 0; asteroidNum < gm.numAsteroids;                            
     asteroidNum++) {

    // Is the current asteroid active before proceeding
    if (gm.asteroids[asteroidNum].isActive()) {

        // Perform the collision checks by
        // passing in the collision packages
        if (CD.detect(gm.ship.cp, gm.asteroids[asteroidNum].cp)) {

        // hit!
        destroyAsteroid(asteroidNum);
        lifeLost();
       }
    }
}

if (possibleCollision) {

 double radianAngle = ((cp.facingAngle/180)*Math.PI);
 double cosAngle = Math.cos(radianAngle);
 double sinAngle = Math.sin(radianAngle);

    //Rotate each and every vertex then check for a collision
    // If just one is then we have a collision.
    // Once we have a collision no need to check further
    for (int i = 0 ; i < cp.vertexListLength; i++){
        // First update the regular un-rotated model space coordinates
        // relative to the current world location (centre of object)
        float worldUnrotatedX = 
                cp.worldLocation.x + cp.vertexList[i].x;

        float worldUnrotatedY =  
                cp.worldLocation.y + cp.vertexList[i].y;

        // Now rotate the newly updated point, stored in currentPoint
        // around the centre point of the object (worldLocation)
        cp.currentPoint.x = cp.worldLocation.x + (int)                                   
            ((worldUnrotatedX - cp.worldLocation.x)
            * cosAngle - (worldUnrotatedY - cp.worldLocation.y)
            * sinAngle);

        cp.currentPoint.y = cp.worldLocation.y + (int)                                   
            ((worldUnrotatedX - cp.worldLocation.x)
            * sinAngle+(worldUnrotatedY - cp.worldLocation.y)
            * cosAngle);

     // Check the rotated vertex for a collision
     if (cp.currentPoint.x < 0) {

       return true;
     } else if (cp.currentPoint.x > mapWidth) {

       return true;
     } else if (cp.currentPoint.y < 0) {

       return true;
     } else if (cp.currentPoint.y > mapHeight) {

       return true;
   }

}

     if (distance < cp1.radius + cp2.radius) {

            double radianAngle1 = ((cp1.facingAngle / 180) * Math.PI);
            double cosAngle1 = Math.cos(radianAngle1);
            double sinAngle1 = Math.sin(radianAngle1);

            double radianAngle2 = ((cp2.facingAngle / 180) * Math.PI);
            double cosAngle2 = Math.cos(radianAngle2);
            double sinAngle2 = Math.sin(radianAngle2);

            int numCrosses = 0;    // The number of times we cross a side

            float worldUnrotatedX;
            float worldUnrotatedY;

for (int i = 0; i < cp1.vertexListLength; i++) {

    worldUnrotatedX = cp1.worldLocation.x + cp1.vertexList[i].x;
    worldUnrotatedY = cp1.worldLocation.y + cp1.vertexList[i].y;

    // Now rotate the newly updated point, stored in currentPoint
    // around the centre point of the object (worldLocation)
    cp1.currentPoint.x = cp1.worldLocation.x +
        (int) ((worldUnrotatedX - cp1.worldLocation.x)
        * cosAngle1 - (worldUnrotatedY - cp1.worldLocation.y) *
        sinAngle1);

    cp1.currentPoint.y = cp1.worldLocation.y + 
        (int) ((worldUnrotatedX - cp1.worldLocation.x)
        * sinAngle1 + (worldUnrotatedY - cp1.worldLocation.y) *                   
         cosAngle1);

    // cp1.currentPoint now hold the x/y 
    // world coordinates of the first point to test

// Use two vertices at a time to represent the line we are testing
// We don't test the last vertex because we are testing pairs
// and the last vertex of cp2 is the padded extra vertex.
// It will form part of the last side when we test vertexList[5]

for (int j = 0; j < cp2.vertexListLength - 1; j++) {

    // Now we get the rotated coordinates of 
    // BOTH the current 2 points being
    // used to form a side from cp2 (the asteroid)
    // First we need to rotate the model-space 
    // coordinate we are testing
    // to its current world position
    // First update the regular un-rotated model space coordinates
    // relative to the current world location (centre of object)

    worldUnrotatedX = cp2.worldLocation.x + cp2.vertexList[j].x;
    worldUnrotatedY = cp2.worldLocation.y + cp2.vertexList[j].y;

    // Now rotate the newly updated point, stored in worldUnrotatedX/y
    // around the centre point of the object (worldLocation)

    cp2.currentPoint.x = cp2.worldLocation.x + 
          (int) ((worldUnrotatedX - cp2.worldLocation.x)
          * cosAngle2 - (worldUnrotatedY - cp2.worldLocation.y) *                   
          sinAngle2);

    cp2.currentPoint.y = cp2.worldLocation.y + 
          (int) ((worldUnrotatedX - cp2.worldLocation.x)
          * sinAngle2 + (worldUnrotatedY - cp2.worldLocation.y) *                   
          cosAngle2);

    // cp2.currentPoint now hold the x/y world coordinates
    // of the first point that
    // will represent a line from the asteroid

    // Now we can do exactly the same for the 
    // second vertex and store it in
    // currentPoint2\. We will then have a point and a line (two 
    // vertices)we can use the
    // crossing number algorithm on.

    worldUnrotatedX = cp2.worldLocation.x + cp2.vertexList[i + 1].x;
    worldUnrotatedY = cp2.worldLocation.y + cp2.vertexList[i + 1].y;

    // Now rotate the newly updated point, stored in worldUnrotatedX/Y
    // around the centre point of the object (worldLocation)
    cp2.currentPoint2.x = cp2.worldLocation.x + 
          (int) ((worldUnrotatedX - cp2.worldLocation.x)
          * cosAngle2 - (worldUnrotatedY - cp2.worldLocation.y) *                   
          sinAngle2);

    cp2.currentPoint2.y = cp2.worldLocation.y + 
          (int) ((worldUnrotatedX - cp2.worldLocation.x)
          * sinAngle2 + (worldUnrotatedY - cp2.worldLocation.y) *                   
           cosAngle2);

// And now we can test the rotated point from cp1 against the
// rotated points which form a side from cp2

if (((cp2.currentPoint.y > cp1.currentPoint.y) !=                               
       (cp2.currentPoint2.y > cp1.currentPoint.y)) &&
       (cp1.currentPoint.x < (cp2.currentPoint2.x -                                
     cp2.currentPoint2.x)    *(cp1.currentPoint.y - 
        cp2.currentPoint.y) / (cp2.currentPoint2.y  -                               
  cp2.currentPoint.y) + cp2.currentPoint.x)){

        numCrosses++ ;

}

            }
            }
            // So do we have a collision?
            if (numCrosses % 2 == 0) {
                // even number of crosses(outside asteroid)
                collided = false;
            } else {
                // odd number of crosses(inside asteroid)
                collided = true;
            }

        }// end if

<uses-feature android:glEsVersion="0x00020000" android:required="true" />