opencubicles / php-convexhull

Simple PHP implementation of the "Andrew's Monotone Chain" algorithm

PHP Convex Hull

Simple PHP implementation of the "Andrew's Monotone Chain" convex hull algorithm

$input = [
	[ -1.4227294921875, 52.19413974159753 ],
	[ -2.1148681640624996, 51.88666357770388 ],
	[ -1.69189453125, 51.879882095410224 ],
	[ -2.0709228515625, 51.2928411273273 ],
	[ -1.1151123046875, 51.155231611562265 ],
	[ -1.4666748046875, 51.57706953722567 ],
	[ -0.5548095703125, 51.64870258356996 ],
	[ -1.1920166015625, 51.84595933666338 ],
	[ -0.648193359375, 52.11325243469631 ],
	[ -1.285400390625, 52.55965567958736 ],
	[ -1.4227294921875, 52.19413974159753 ]
];

$output = convexHull($input);

/*
	-2.11486816406, 51.8866635777
	-2.07092285156, 51.2928411273
	-1.11511230469, 51.1552316116
	-0.554809570312, 51.6487025836
	-0.648193359375, 52.1132524347
	-1.28540039062, 52.5596556796
	-2.11486816406, 51.8866635777
*/