Calculate a convex hull from a given array of x, y coordinate - Graham Algo - Pure PHP, no dependencies

Graham_Hull.php

<?php


namespace App\Common;



class Graham
{


    const ONE_RADIAN = 57.295779513082;

    public ?Point $anchorPoint = null;
    public array $points = [];
    private bool $reverse = false;


    /**
     * @param Point[] $points
     * @return $this
     */
    public function addPoints(array $points):Graham
    {

        foreach($points as $point){
            $this->addPoint($point[0],$point[1]);
        }
        return $this;
    }

    public function _findPolarAngle(?Point $a,?Point $b):float{

        if(!$a || !$b) return 0;
        $deltaX = ($b->x - $a->x);
        $deltaY = ($b->y - $a->y);
        if($deltaX === 0 || $deltaY === 0){
            return 0;
        }
        $angle = atan2($deltaY,$deltaX) * self::ONE_RADIAN;
        if($this->reverse){
            if($angle <= 0){
                $angle+=360;
            }
        }else{
            if($angle >= 0){
                $angle+=360;
            }
        }
        return $angle;
    }


    public function addPoint(float $x,float $y):void
    {

        $newAnchor =
        ($this->anchorPoint === null) ||
        ( $this->anchorPoint->y > $y ) ||
        ( $this->anchorPoint->y === $y && $this->anchorPoint->x > $x );

        if ( $newAnchor ) {
            if ( $this->anchorPoint instanceof Point) {
                array_push($this->points,new Point($this->anchorPoint->x,$this->anchorPoint->y));
            }
            $this->anchorPoint = new Point($x,$y);
        } else {
            array_push($this->points,new Point($x,$y));
        }
    }

    public function getPoints():array
    {
        return $this->points;
    }



    public function _checkPoints($p0, $p1, $p2)
    {
            $cwAngle = $this->_findPolarAngle($p0,$p1);
            $ccwAngle = $this->_findPolarAngle($p0,$p2);
            if($cwAngle > $ccwAngle){
                $difAngle = $cwAngle - $ccwAngle;
                return !($difAngle > 180);
            }else if($cwAngle < $ccwAngle){
                $difAngle = $ccwAngle - $cwAngle;
                return ($difAngle > 180);
            }
            return true;
    }


    public function sortPoints()
    {
        usort($this->points,function($a,$b){
            $polarA = $this->_findPolarAngle($this->anchorPoint,$a);
            $polarB = $this->_findPolarAngle($this->anchorPoint,$b);
            if ($polarA < $polarB) {
                return -1;
            }
            if ($polarA > $polarB) {
                return 1;
            }
            return 0;
        });
        return $this->points;
    }


    public function getHull()
    {

        $array_any = function(array $array, callable $fn) {
            foreach ($array as $value) {
                if($fn($value)) {
                    return true;
                }
            }
            return false;
        };

        $every = function($array,$callback)
        {
            return  !in_array(false,  array_map($callback,$array));
        };

        $hullPoints = [];
        $points = null;
        $pointsLength = null;

        $this->reverse = $every($this->points,function(Point $point){
            return ($point->x < 0 && $point->y < 0);
        });

        $points = $this->sortPoints();
        $pointsLength = count($points);
        if($pointsLength < 3){ // @todo  Remove anchorpoint from list and return a linestring... but here it is null...
            array_unshift($points,$this->anchorPoint);
            return $points;
        }

        $t = array_shift($points);
        array_push($hullPoints,$t);
        $t = array_shift($points);
        array_push($hullPoints,$t);


        while(true){

            $temp = array_shift($points);
            array_push($hullPoints,$temp);

            $p0 = $hullPoints[count($hullPoints) -3];
            $p1 = $hullPoints[count($hullPoints) -2];
            $p2 = $hullPoints[count($hullPoints) -1];
            if($this->_checkPoints($p0,$p1,$p2)){
                array_splice($hullPoints,count($hullPoints)-2,1);
            }
            if(count($points) === 0){
                if($pointsLength === count($hullPoints)){
                    $ap = $this->anchorPoint;
                    $hullPoints = array_filter($hullPoints,function($p){
                        return !!$p;
                    });
                    if(!$array_any($hullPoints,function(Point $p) use ($ap){
                        return ($p->x === $ap->x && $p->y === $ap->y);
                    })){
                        array_unshift($hullPoints,$this->anchorPoint);
                    }
                    return $hullPoints;
                }
                $points = $hullPoints;
                $pointsLength = count($points);
                $hullPoints = [];
                $hullPoints[] = array_shift($points);
                $hullPoints[] = array_shift($points);
            }
        }
    }
}

Graham_Hull_Test.php

<?php


use App\Common\Graham;
use App\Common\Point;

class HullTest extends TestCase
{


    /**
     * @outputBuffering disabled
     */
    public function testSortPoints()
    {

        $points = [
        new Point(48.8,11.3),
            new Point(48.8167,11.3667),
            new Point(48.1,11.1),
            new Point(48.9,11.7),
            new Point(48.7833,11.2333),
        ];
        $sortedPoints = [
            new Point(48.1,11.1),
            new Point(48.7833,11.2333),
            new Point(48.8,11.3),
            new Point(48.8167,11.3667),
            new Point(48.9,11.7),
        ];

        $poly = new Graham();
        $poly->points = $points;
        $poly->anchorPoint =  new Point(48.1,11.1);
        $poly->sortPoints();
        $this->assertSame(serialize($sortedPoints),serialize($poly->getPoints()));
    }


    public function testCorrectCalculation()
    {
        $graham = new Graham();
        $angle = $graham->_findPolarAngle(new Point(11.1, 48.1),new Point(11.3, 48.8));
        $this->assertEquals(434.0546040990765, $angle);
    }

    public function testPolarAngleComparison()
    {

        $testPoints = [
            new Point(48.1,11.1),
            new Point(48.7833,12.2333),
            new Point(48.8,11.3),
        ];
        $graham = new Graham();
        $this->assertTrue($graham->_checkPoints($testPoints[0],$testPoints[1],$testPoints[2]));
    }

    public function testHullIsCreated()
    {
        $points = [
            [50.76947080994697,7.84698486328125],
            [50.65990836093937,8.01177978515625],
            [50.88917404890332,8.20404052734375],
            [50.76947080994697,8.338623046874998],
            [50.793783247910106,8.09967041015625]
        ];
        $graham = new Graham();

        foreach ($points as $point) {
            $graham->addPoint($point[0],$point[1]);
        }
        $this->assertNotNull($graham->anchorPoint);


        $hull = $graham->getHull();
        //fwrite(STDOUT,print_r($hull,true)); // 5 points to 4 points. a nice rectangle :)
        $this->assertIsArray($hull);
        $this->assertCount(4,$hull);


    }


}