hotrush/angular-sweep

v1.0.0 2019-04-09 13:28 UTC

Requires

• php: >=7.1

Requires (Dev)

• phpunit/phpunit: ^7.5

MIT

• hotrush

README

PHP implementation of angular sweep algorithm

Solves issue of finding maximum points that can be enclosed in a circle of given radius and getting the center of this point.

https://en.wikipedia.org/wiki/Visibility_polygon#Angular_sweep

https://www.geeksforgeeks.org/angular-sweep-maximum-points-can-enclosed-circle-given-radius/

https://github.com/pear/Math_Complex/blob/master/Math/Complex.php

Installation

composer require hotrush/angular-sweep

Usage

use Hotrush\AngularSweep\NumbersCollection;
use Hotrush\AngularSweep\ComplexNumber;
use Hotrush\AngularSweep\AngularSweep;

$coordinates = [
    [6.47634, 7.69628],
    [5.16828, 4.79915],
    [6.69533, 6.20378],
];

$collection = new NumbersCollection();

foreach ($coordinates as $coordinate) {
    $collection->add(new ComplexNumber($coordinate[0], $coordinate[1]));
}

$radius = 1;

$sweep = new AngularSweep($collection, $radius);

echo $sweep->getMax();
// 2

$center = $sweep->getMaxCenter();
echo $center->getReal() . '-' . $center->getIm();
// '6.47634-7.69628'

Testing

phpunit

FYI

https://www.geeksforgeeks.org/find-minimum-radius-atleast-k-point-lie-inside-circle/