We have looked at various methods available within the Geom.Intersects class. There are methods that detect the overlap between many different combinations of geometries. In this post we look at the methods available to detect overlap between two polygons.
There is no PolygonToPolygon method
The first thing one will notice if one looks at the official documentation of Geom.Intersects class is that there is no PolygonToPolygon or GetPolygonToPolygon method, which is somewhat of a surprise. The only method that comes close is the GetLineToPolygon (there is no LineToPolygon method).
<static> GetLineToPolygon(line, polygons [, out])
According to the official documentation, this method checks for the closest point of intersection between a line segment and an array of polygons. If no intersection is found, this function returns null.
The following is the key section of the underlying code of this method.
for (var i = 0; i < polygons.length; i++)
{
if (GetLineToPoints(line, polygons[i].points, tempIntersect))
{
if (!closestIntersect || tempIntersect.z < out.z)
{
out.set(tempIntersect.x, tempIntersect.y, tempIntersect.z, i);
closestIntersect = true;
}
}
}In particular, the method relies on another method called GetLineToPoints, which according to the official documentation checks for the closest point of intersection between a line segment and an array of points, where each pair of points are converted to line segments for the intersection tests.
The key underlying code of this GetLineToPoints is as follows. It simply loops through all the points, creating a line object between successive points, and calling GetLineToLine.
In otherwords, GetLineToPolygons is actually testing for intersection between the specific line vs every edge of the polygon (or array of polygons).
var prev = points[0];
for (var i = 1; i < points.length; i++)
{
var current = points[i];
segment.setTo(prev.x, prev.y, current.x, current.y);
prev = current;
if (GetLineToLine(line, segment, tempIntersect))
{
if (!closestIntersect || tempIntersect.z < out.z)
{
out.copy(tempIntersect);
closestIntersect = true;
}
}
}
(Note, segment is a global variable that is a Geom.Line object.)
Let's create our own PolygonToPolygon method
Armed with the above knowledge, it is very simple to create our own method for detecting intersection between two polygons.
PolygonToPolygon(polygonA, polygonB)
We can do this by looping through every edge of polygon A against every edge of polygon B, and checking whether there is an intersecting edge. If we are simply interested in finding out whether the two polygons intersect of nor, and not the actual point of intersection, then one can exit the loop as soon as there is an intersection.
class Intersects {
static PolygonToPolygon(polygonA, polygonB) {
var prevA, prevB, currentA, currentB;
const pointsA = polygonA.points;
const pointsB = polygonB.points;
prevA = pointsA[pointsA.length-1];
for (let i = 0; i < pointsA.length; i++) {
currentA = pointsA[i];
tmpSegmentA.setTo(prevA.x, prevA.y, currentA.x, currentA.y);
prevA = currentA;
prevB = pointsB[pointsB.length-1];
for (let j = 0; j < pointsB.length; j++) {
currentB = pointsB[j];
tmpSegmentB.setTo(prevB.x, prevB.y, currentB.x, currentB.y);
prevB = currentB;
if (Phaser.Geom.Intersects.LineToLine(tmpSegmentA, tmpSegmentB)) {
return true;
}
}
}
return false;
}There is one flaw with this algorithm in that if one polygon is entirely "inside" the other polygon, such a situation will not register as an intersection. As has been seen with the Triangle intersection method, code to check for this "degenerate" case should be added to make the method "complete". I will not however do this here, as there is an alternative method of detecting intersections, and that is to check to see if any of the vertices of one polygon is inside the other polygon, as opposed to checking for edge vs edge intersections, which is pretty much what we would have to do to check whether a polygon is entirely inside another.
GetPolygonToPolygon(polygonA, polygonB)
Detecting intersection and returning the intersection points is easy enough by relying on the GetLinToLine method.
static GetPolygonToPolygon(polygonA, polygonB, out) {
if (out === undefined) { out = []; }
var prevA, prevB, currentA, currentB;
const pointsA = polygonA.points;
const pointsB = polygonB.points;
prevA = pointsA[pointsA.length-1];
for (let i = 0; i < pointsA.length; i++) {
currentA = pointsA[i];
tmpSegmentA.setTo(prevA.x, prevA.y, currentA.x, currentA.y);
prevA = currentA;
prevB = pointsB[pointsB.length-1];
for (let j = 0; j < pointsB.length; j++) {
currentB = pointsB[j];
tmpSegmentB.setTo(prevB.x, prevB.y, currentB.x, currentB.y);
prevB = currentB;
var intersect = Phaser.Geom.Intersects.GetLineToLine(tmpSegmentA, tmpSegmentB);
if (intersect) {
out.push(intersect)
}
}
}
return out;
}It should be noted that the above code relies Geom.Intersects.GetLineToLine of version 3.6 of Phaser 3, which was NOT available when this post was originally written. With older version of Phaser 3, one will need to write a custom version of the GetLineToLine method since older version of Phaser's GetLineToLine will treat lines as .. well, lines, as opposed to segments, and will produce false positives.
The above code can be accessed from the Codepen below.
Alternative method for detecting intersections
Whereas the above methods relies on checking for intersections between the edges of the polygons, one can also check for intersection by seeing if any of the vertices of one polygon is inside the other polygon.
The most difficult part of implementing this algorithm is how to detect whether a point lies within a polygon - thankfully, Phaser provides us with a method to do just that - Geom.Polygon.contains(x,y)
function PolygonToPolygon(polygonA, polygonB) {
const pointsA = polygonA.points;
const pointsB = polygonB.points;
for (let i = 0; i < pointsA.length; i++) {
const p = pointsA[i];
if (polygonB.contains(p.x, p.y)) return true;
}
for (let j = 0; j < pointsB.length; j++) {
const p = pointsB[j];
if (polygonA.contains(p.x, p.y)) return true;
}
return false;
}This version can be accessed from the Codepen below.
Concluding remarks
The above algorithms work. However, they are computationally expensive. We will explore other algorithms for detecting intersections between two polygons, the easiest of which is to get the axis aligned bounding box (Phaser provides a method to do this) and calling RectangleToRectangle to filter out polygons which are clearly not intersecting, but might potentially be intersecting. You can call the above method only when the AABB's are colliding.
Comments