the polygon: we'll fix that later.
CIRCLE
POLYGON/To test if a circle has collided with a polygon, we can simplify the problem to a series of Line/Circle collisions, one for each side of the polygon. Since we've already covered the steps to go through the vertices as lines, and Line/Circle collisions, let's just look at the test for each side:
var collision = ;if collision return true;
Cool! We can build on previous code this way, allowing flexible, complex code to emerge from simpler pieces.
Here's the full example:
var cx = 0; // position of the circlevar cy = 0;var r = 30; // circle's radius // array of PVectors, one for each vertex in the polygonvar vertices = ; { var canvas = ; ; // set position of the vertices (here a trapezoid) vertices0 = ; vertices1 = ; vertices2 = ; vertices3 = ;} { ; // update circle to mouse coordinates cx = mouseX; cy = mouseY; // check for collision // if hit, change fill color var hit = ; if hit ; else ; // draw the polygon using beginShape() ; ; for var i=0; i<verticeslength; i++ var v = verticesi; ; ; // draw the circle ; ;} // POLYGON/CIRCLE { // go through each of the vertices, plus // the next vertex in the list var next = 0; for var current=0; current<verticeslength; current++ // get next vertex in list // if we've hit the end, wrap around to 0 next = current+1; if next == verticeslength next = 0; // get the PVectors at our current position // this makes our if statement a little cleaner var vc = verticescurrent; // c for "current" var vn = verticesnext; // n for "next" // check for collision between the circle and // a line formed between the two vertices var collision = ; if collision return true; // the above algorithm only checks if the circle // is touching the edges of the polygon – in most // cases this is enough, but you can un-comment the // following code to also test if the center of the // circle is inside the polygon // var centerInside = polygonPoint(vertices, cx,cy); // if (centerInside) return true; // otherwise, after all that, return false return false;} // LINE/CIRCLE { // is either end INSIDE the circle? // if so, return true immediately var inside1 = ; var inside2 = ; if inside1 || inside2 return true; // get length of the line var distX = x1 - x2; var distY = y1 - y2; var len = ; // get dot product of the line and circle var dot = cx-x1*x2-x1 + cy-y1*y2-y1 / ; // find the closest point on the line var closestX = x1 + dot * x2-x1; var closestY = y1 + dot * y2-y1; // is this point actually on the line segment? // if so keep going, but if not, return false var onSegment = ; if !onSegment return false; // get distance to closest point distX = closestX - cx; distY = closestY - cy; var distance = ; // is the circle on the line? if distance <= r return true; return false;} // LINE/POINT { // get distance from the point to the two ends of the line var d1 = ; var d2 = ; // get the length of the line var lineLen = ; // since floats are so minutely accurate, add // a little buffer zone that will give collision var buffer = 01; // higher # = less accurate // if the two distances are equal to the line's // length, the point is on the line! // note we use the buffer here to give a range, rather // than one # if d1+d2 >= lineLen-buffer && d1+d2 <= lineLen+buffer return true; return false;} // POINT/CIRCLE { // get distance between the point and circle's center // using the Pythagorean Theorem var distX = px - cx; var distY = py - cy; var distance = ; // if the distance is less than the circle's // radius the point is inside! if distance <= r return true; return false;} // POLYGON/POINT// only needed if you're going to check if the circle// is INSIDE the polygon { var collision = false; // go through each of the vertices, plus the next // vertex in the list var next = 0; for var current=0; current<verticeslength; current++ // get next vertex in list // if we've hit the end, wrap around to 0 next = current+1; if next == verticeslength next = 0; // get the PVectors at our current position // this makes our if statement a little cleaner var vc = verticescurrent; // c for "current" var vn = verticesnext; // n for "next" // compare position, flip 'collision' variable // back and forth if vcy > py && vny < py || vcy < py && vny > py && px < vnx-vcx*py-vcy / vny-vcy+vcx collision = !collision; return collision;}
Since polyCircle()
calls lineCircle()
which calls linePoint()
, we could combine these into a single function, but the idea of functions in programming is reusability. Now, if we update linePoint()
, it carries through all our projects.
But! We have a bit of a problem. Try moving the circle so it's completely inside the polygon. No more collision! These situations are called "edge cases", ones that require a different set of parameters to check for.
In most situations, we don't need to know if the circle is inside: imagine the polygon is a spaceship and the circle is an asteroid. As soon as the asteroid touches the ship, we'd register the collision and do something (like blow up the ship).
If you do need to know if the circle is inside the polygon, you can add two more lines to the polyCircle()
function (right before the final return false;
) to test if the center of the circle is inside the polygon:
var centerInside = ;if centerInside return true;
We do this after we test the edges, since those are more likely to be hit first. Unless you need this functionality, leave it out. It requires running through all the vertices of the polygon again, which will slow down your program.