Detecting collisions for regular polygons is relatively simple.
A square will always have 4 sides, a pentagon will always have an internal angle of 108ยบ and so on. Their shapes and properties are always the same, no matter their size or position.
But what if we're dealing with irregular polygons?
They can assume an infinite number of shapes, sides and angles. They're impossible to predict!
The first thing we need to learn is how we tell if a point is inside a polygon or not. There are several techniques, but I'm going to use the Jordan Curve Theorem.
This theorem basically says that a closed shape divides the space in an "inside" and an "outside" areas. And if a point is inside the shape, when you cast a ray it will always have an odd number of intersections with the shape's boundaries.
There is one exception however. If the point is inside, but the ray passes through exactly at one of the vertices, the number of intersections is even, not odd.
So if we have a point (p) and the list of points that define the polygon, the first thing we need to do is define a line that passes through the point. Personally I always define a vertical line, to make the next calculations easier.
The next thing we need to do is loop through the polygon points and find the equation of the line for each edge. Then we just need to replace the X with the value of the vertical line to find the intersection point of both lines (and check if it's within the edge's boundaries).
But since we're dealing with a full line and not a semi-straight line passing through the point, we need to count the amount of intersections that are occurring below and above the point.
As for detecting the collision between 2 polygons, finding out if the vertices of one polygon is inside the other isn't enough, because it can be only the edges that are colliding.
So we need to loop between the vertices of both polygons, define the lines and find out if the they're intersecting each other, as it's explained here.
A square will always have 4 sides, a pentagon will always have an internal angle of 108ยบ and so on. Their shapes and properties are always the same, no matter their size or position.
But what if we're dealing with irregular polygons?
They can assume an infinite number of shapes, sides and angles. They're impossible to predict!
The first thing we need to learn is how we tell if a point is inside a polygon or not. There are several techniques, but I'm going to use the Jordan Curve Theorem.
This theorem basically says that a closed shape divides the space in an "inside" and an "outside" areas. And if a point is inside the shape, when you cast a ray it will always have an odd number of intersections with the shape's boundaries.There is one exception however. If the point is inside, but the ray passes through exactly at one of the vertices, the number of intersections is even, not odd.
So if we have a point (p) and the list of points that define the polygon, the first thing we need to do is define a line that passes through the point. Personally I always define a vertical line, to make the next calculations easier.
x = px
The next thing we need to do is loop through the polygon points and find the equation of the line for each edge. Then we just need to replace the X with the value of the vertical line to find the intersection point of both lines (and check if it's within the edge's boundaries).
y = m px + b
But since we're dealing with a full line and not a semi-straight line passing through the point, we need to count the amount of intersections that are occurring below and above the point.
if ( y < py ){
// The intersection is below the point
}
// The intersection is below the point
}
if ( y > py ){
// The intersection is above the point
}
// The intersection is above the point
}
So we need to loop between the vertices of both polygons, define the lines and find out if the they're intersecting each other, as it's explained here.
0 comments:
Post a Comment