Polygon intersection helper

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

Install

You can install it via npm:

``sh
$ npm i polygon-intersection
`

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:

⠀ | ⠀ |
|:-------------------------:|:-------------------------:|
!Intersection example | !Intersection example

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:
1. An edge of one polygon crosses an edge of the other;
2. A point of one polygon lies inside the other;
3. 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:

`typescript
import {
checkIfPolygonsIntersect,
findIntersectionBetweenPolygons,
} from 'polygon-intersection';

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

Validation tests ##

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