arcade.geometry.are_polygons_intersecting calculates intersections for convex hull

[LiorAvrahami]

Bug Report

arcade.geometry.are_polygons_intersecting calculates intersections for the convex hull of the given polygons. this is a problem when "hit_box_algorithm" is selected to be "Detailed", which in general doesn't generate convex hitboxes.
as far as I could find, the fact that arcade.geometry.are_polygons_intersecting calculates intersections of the convex hulls is not documented so at the very least this documentation issue should be fixed (altho this issue massively hinders the effectiveness of the "Detailed" "hit_box_algorithm", and thus I think we should look for a different polygon intersector).
I have an idea for a solution, see - "What is wrong with it? How can it be improved?", I would be happy to implement it myself, but am new to github so don't really know how all these forks and merges work (I have always only worked alone on git)

Actual behavior:

given two polygons, "arcade.geometry.are_polygons_intersecting" calculates intersections of their convex hulls, so if one of them is not convex, the collision calculation will be false.

Expected behavior:

are_polygons_intersecting should calculate the intersections of the polygons without taking their convex hulls.

Steps to reproduce/example code:

at the bottom of this page

What would it help with?

currently if a "Detailed" hit_box_algorithm is selected when creating a texture, than the hitbox is in general very well made. it's too bad that the polygon collision doesn't allow for general detailed hitboxes, and works correctly for allows convex ones.

What documentation needs to change?

if this issue is not addressed than the documentation should state clearly at both the documentation of the hit_box_algorithm parameter in the Texture initialization function and at the documentation of arcade.geometry.are_polygons_intersecting that collisions are calculated for convex hulls only

What is wrong with it? How can it be improved?

this algorithm uses a projections technique, it projects each polygon onto a line, thus "transforming" each polygon in to a line-segment. a projection brings the interior of the polygon to the interior of the line segment so if the polygons intersect than it's trivial that these line segments will intersect. thus if these line segments don't intersect, than for sure the polygons don't intersect (this is the situation where we get to the "return False" in the code). this is done in a loop, projecting the polygons onto all the lines that are parallel to the segments that comprise the polygon (I don't know why specifically all these lines were chosen). but it is from here safe to say that this algorithm has no false negatives. the problem is that any projection of a polygon is identical to the projection of it's convex hull, so no matter which projections you chose to do, you get these false positives with this algorithm because these projections don't hold enough information about the real polygon (under these projections the polygon is equivalent to it's convex hull).
for comparison this algorithm has complexity of o((n+m)^2) where n,m are the number of points in each polygon respectively.

my idea for solution:
sympy implements polygon collision detection by resolving all possible 2d segment intersections (o(n*m))
which is mathematically simpler (altho I must admit less elegant). the problem with this algorithm is that it **only calculates intersections of the boundaries of the polygons and doesn't count one polygon residing inside the other as collision. but the solution to this is trivial, after you run the 2d segment intersections and no collision is found, you only need to choose a single point in each of the two polygons and check if it is inside the oher polygon (o(n+m)). the function for calculating if a point is inside a polygon already exists in the file arcade.geometry
I would be happy to implement this, but am new to github so don't really know how all these forks and merges work (I have always only worked alone on git)

Steps to reproduce/example code:

#these tests should all be passing, if polygon collisions are implemented correctly
#but at the time of writing this, "test_that_p1_p2_do_not_collide" doesn't pass because of this convex hull issue

import unittest
import arcade.geometry

p1 = [[400, 100],[600, 30],[800, 100],[800,0],[400,0]]
p2 = [[500,100],[600,150],[600,90]]
p3 = [[600,60],[700,50],[600,40]]
p4 = [[650,20],[750,40],[700,20]]

class test_geometry_collitions(unittest.TestCase):

    def test_that_p1_p2_do_not_collide(self):
        self.assertFalse(arcade.geometry.are_polygons_intersecting(p1,p2),"p1, and p2 should not collide")

    def test_that_p1_p3_do_collide(self):
        self.assertTrue(arcade.geometry.are_polygons_intersecting(p1, p3), "p3, and p2 should collide")

    def test_that_p1_p4_do_collide(self):
        self.assertTrue(arcade.geometry.are_polygons_intersecting(p1, p4), "p3, and p2 should collide")

    def test_that_p2_p4_do_not_collide(self):
        self.assertFalse(arcade.geometry.are_polygons_intersecting(p2, p4), "p3, and p2 should collide")

    def test_draw_all_polygons(self):
        # not really a test, I use this in pycharm to draw the polygons
        import matplotlib.pyplot as plt
        import numpy as np
        h = np.array(p1)
        plt.scatter(h[:, 0], h[:, 1],c="b",label="p1")
        plt.plot(h[:, 0], h[:, 1],"b")
        plt.plot([h[-1, 0],h[0, 0]], [h[-1, 1],h[0, 1]],"b--")
        h = np.array(p2)
        plt.scatter(h[:, 0], h[:, 1],c="r",label="p2")
        plt.plot(h[:, 0], h[:, 1],"r")
        plt.plot([h[-1, 0], h[0, 0]], [h[-1, 1], h[0, 1]], "r--")
        h = np.array(p3)
        plt.scatter(h[:, 0], h[:, 1],c="g",label="p3")
        plt.plot(h[:, 0], h[:, 1],"g")
        plt.plot([h[-1, 0], h[0, 0]], [h[-1, 1], h[0, 1]], "g--")
        h = np.array(p4)
        plt.scatter(h[:, 0], h[:, 1],c="k",label="p4")
        plt.plot(h[:, 0], h[:, 1],"k")
        plt.plot([h[-1, 0], h[0, 0]], [h[-1, 1], h[0, 1]], "k--")
        plt.legend(loc='upper right')
        plt.show()

[pvcraven]

This would be interesting. The key to this (aside from work) is seeing if it is slower, the same, or faster. I'd welcome a PR that implements this, so we can compare and see what works best.

[LiorAvrahami]

PR sent

[pvcraven]

This seems to pass now, with shapely.