fix: Updated PolygonComponent.containsPoint to account for concave polygons

[davidjan3]

Description

Previously, the PolygonComponent.containsPoint() and .containsLocalPoint() functions consisted of duplicate code that checked whether a given point lies within a convex polygon. They didn't function properly with concave polygons.

I created a new _containsPoint() function that is called from both functions to reduce redundancies. This new function uses a different approach to figure out whether a point lies within a polygon, which should also work for concave polygons, or even polygons with holes. The algorithm is vaguely explained within code comments, and is visualized in this post: https://stackoverflow.com/a/218081/5008997

Checklist

• I have followed the Contributor Guide when preparing my PR.
• I have updated/added tests for ALL new/updated/fixed functionality.
• I have updated/added relevant documentation in docs and added dartdoc comments with ///.
• I have updated/added relevant examples in examples or docs.

Breaking Change?

• Yes, this PR is a breaking change.
• No, this PR is not a breaking change.

Related Issues

[spydon]

Looks good after a quick look, how's the performance impact?

[davidjan3]

Just stress-tested the performance within my current project.
Calling containsPoint(vertex) for 4 vertices on 10,000 randomly generated polygons with 10-24 vertices each:
Old method avg: ~370ms
New method avg: ~530ms

So it takes about 43% longer on average.

However, by replacing

final edge = getEdge(i, vertices: vertices);

with

final from = vertices[i];
final to = vertices[(i + 1) % vertices.length];

It goes down to ~350ms and still survives every test.
Though this also speeds up the old version to ~320ms.

It's important to note that in my test, the old function returns false almost all the time. And looking at the code, returning false can happen much faster than checking all edges before returning true.

[spydon]

@davidjan3 can you try with a bit more vertices, like 10?

[davidjan3]

All polygons had 10-24 vertices. My test just ran the .containsPoint(vertex) method 4 times per polygon, to see if all 4 corners of a rectangle lie within it. I can share my code sample after work.

[davidjan3]

@spydon Code sample (useless of course, just to serve performance testing):

final stopwatch = Stopwatch()..start();
for (Vector2 vertex in rect.globalVertices()) {
  for (PolygonComponent polygon in polygons) {
    // polygon is a random convex or concave polygon with between 10 and 24 vertices
    collided = polygon.containsPoint(vertex);
  }
}
log("Collision check took ${stopwatch.elapsedMilliseconds} ms");

Ran this in a loop and it kept averaging around the numbers stated in earlier comments.

If you like, I can push the version where getEdge() is substituted for performance gains as described above.
Otherwise I'd just add a couple tests and hope for approval.

[spydon]

Otherwise I'd just add a couple tests and hope for approval.

Sounds good, seems like a reasonable performance trade-off.

[davidjan3]

@spydon So would you prefer keeping the getEdge() function for consistency, or should I push this?:

However, by replacing

final edge = getEdge(i, vertices: vertices);

with

final from = vertices[i];
final to = vertices[(i + 1) % vertices.length];

It goes down to ~350ms and still survives every test.

That way its worst case would outperform the old implementation's average, so no performance trade-off :)

[spydon]

@davidjan3 sounds like it's definitely worth changing it then! :)

[davidjan3]

@spydon Added said optimization, and a little test :)

[spydon]

Lgtm! Sorry for the delay, I've been away skiing in the alps the last week 😅