I'm going to just drop a bunch of stuff because I wanted to explain it all and implement it myself.
The general point in polygon problem has a bunch of different solutions. Here is one based on the winding number; the number of times a curve wraps around a point. Basically, if you look at any polygon in terms of a bunch of edges going in a sequence and wrapping back to the first point, you can say a point is inside the polygon by counting the winding number. If it's 0, the point is outside. This used to be computed by taking angles from the point to each of the polygon's vertices, adding them up, and if it's 360 then it's inside (winding number of 1). But this is expensive because of trig functions and stuff. Instead you can do the following:
Here you look at an imaginary ray coming from the point, and check where it hits the edges of the polygon. If the edge (moving clockwise around the polygon) is going upwards when the ray crosses it (i.e. the point is on the left-hand side of the edge) the winding number decreases, and if it's going downwards when the ray crosses it (the point is on the right-hand side of the edge) the number increases. Note by left-hand and right-hand I mean relative to the edge in the direction it's "moving". You can see in the picture what's happening, and it's pretty simple here because it's just a rectangle. The same thing applies; if the winding number isn't 0 the point is inside.
// `poly` is an array of points like [[x1,y1], [x2,y2], [x3,y3], [x4,y4]] where edges connect between two adjacent points
function is_collided_polygon(x, y, poly){
let wn = 0;
poly = poly ~ [poly[0]]; // connect edge from last to first vertex
ascent(i in 0..length(poly)-1){
if(poly[i][1] > y){
if(poly[i+1][1] <= y){ // ascending edge crossing point
if(point_edge_side(x, y, poly[i][0], poly[i][1], poly[i+1][0], poly[i+1][1]) < 0){ // point left-hand of edge
wn--;
}
}
}else{
if(poly[i+1][1] > y){ // descending edge crossing point
if(point_edge_side(x, y, poly[i][0], poly[i][1], poly[i+1][0], poly[i+1][1]) > 0){ // point right-hand of edge
wn++;
}
}
}
}
// winding number of 0 iff point outside polygon
return (wn != 0);
function point_edge_side(px, py, ax, ay, bx, by){
// AB.x * AP.y - AB.y * AP.x
return ( (bx - ax) * (py - ay) - (by - ay) * (px - ax) );
}
}
Calculating which side the point is relative to an edge is done with the perpendicular dot product which is just some multiplication. Look into it yourself if you want to know how that works.
So this works for checking collision just fine, but this was a general solution for polygons with however many sides and doesn't take advantage of the fact that you're using a rectangle. So you can do better.
The next solution is a modified version of a sort-of-common collision algorithm for checking polygon-polygon collision that is based on SAT, the Separating Axis Theorem. You can read more about this algorithm
here or
here. Essentially the gist is that if you can fit a line anywhere between the two polygons they aren't collided. This is then equivalent to finding that if you have imaginary axes parallel to all the polygons' edges, and if any of the projections (like shadows) of the polygons on each of those axes aren't overlapping, they aren't collided, and if they are overlapping on each projection they are collided. Check the above links for some extra visual examples.
The main benefit to this here is that 1) you can simplify one of the polygons to a point which has no axes to check, and 2) the other polygon is a rectangle where the opposing sides would have the same axes, and so you only have to check two.
See that here the red lines are the projections the rectangle makes on its own axes. The green point's projection is within the rectangle's projection on both axes (so it's collided), but the blue point fails on one of them (so it isn't collided).
function is_collided_rect(x, y, poly){
return is_point_projected_line(x, y, poly[0][0], poly[0][1], poly[1][0], poly[1][1])
&& is_point_projected_line(x, y, poly[1][0], poly[1][1], poly[2][0], poly[2][1]);
function is_point_projected_line(px, py, ax, ay, bx, by){
let abx = bx-ax;
let aby = by-ay;
let proj = (px-ax)*abx + (py-ay)*aby;
let magn = abx*abx + aby*aby;
return (proj > 0 && proj < magn);
}
}
How exactly this is done is by checking if the length of those projected lines is between 0 and the rectangle's own projection. Doing the vector projection can be read about
here and
here, again requiring some dot products. One other optimization is that while you want to be checking for
0 < (AP . AB) / |AB| < |AB|, getting the magnitude of AB needs a square root so it's better to compute
0 < (AP . AB) < |AB|^2 instead, or
0 < (AP . AB) < (AB . AB) as done in the code.
One last thing is that for both of these methods you can try to cut down the number of times this specific collision checking occurs by only checking points that are within the smallest bounding box that surrounds the rectangle. You only have to compute what the bounding box is once and then use it for all the other checks so it speeds things up by a lot.
You can get all the complete code for these two methods here.
