Polygon intersection helper

This module has an algorithm to check if two simple polygons intersect, and another to find the intersection polygons.

Definition of intersection

For an intersection to exist, the intersection area must be > 0. In other words, the polygon interiors must intersect. For example, the orange and blue polygons do not intersect in the first case, but intersect in the second:

⠀	⠀

For more examples, check below the table of tests both algortihms were submitted to.

How the algorithms work

The algorithm to check if the intersection exists was based on the observation that an intersection occurs if one of the following criteria is fulfilled:

An edge of one polygon crosses an edge of the other;
A point of one polygon lies inside the other;
A point of one polygon lies on an edge of the other, in such a way that the interior of the point's corner intersects the interior of the other polygon.

The algorithm to find the intersection polygons was then designed to apply these three tests in an iterative fashion and save the points it considers to be part of the intersection polygon.

How to use them

To use each algorithm, both polygons must be arrays of 2D point coordinates, ordered counter-clockise. Then, they may be called like:

const polygon1 = [[0,0],[1,0],[1,1],[0,1]];
const polygon2 = [[0,-1],[2,0.5],[0,2]];
const polygonsIntersect = checkIfPolygonsIntersect(polygon1, polygon2);
const intersectionPolygons = findIntersectionBetweenPolygons(polygon1, polygon2);

Validation tests

⠀	⠀	⠀	⠀
Test 01. Intersection: true	Test 02. Intersection: true	Test 03. Intersection: false	Test 04. Intersection: true
Test 05. Intersection: true	Test 06. Intersection: false	Test 07. Intersection: false	Test 08. Intersection: true
Test 09. Intersection: false	Test 10. Intersection: true	Test 11. Intersection: false	Test 12. Intersection: true
Test 13. Intersection: true	Test 14. Intersection: true	Test 15. Intersection: true	Test 16. Intersection: true
Test 17. Intersection: true	Test 18. Intersection: true