Домашнее задание 4

Следующее, четвёртое, домашнее задание, предложенное программистам, было следующим: на ограниченном куске плоскости случайным образом задаются 50 точек. Требуется по ним по всем построить замкнутый контур, и нарисовать его. Первая мысль, которая приходит в голову - напилить треугольничков между точками, чтоб получился граф. И по графу искать нужный контур. Эту мысль я отмёл сразу как очень трудоёмкую, и стал думать. И совершенно случайно в пятницу вечером за вискарём во время обсуждения я высказал вслух отличное решение. Моё отличное решение очень простое - поставить куда-нибудь в середину точку и объявить её центром полярной системы координат. Относительно неё перевести все 50 точек в полярные координаты, отсортировать по углу, и соединить.

<?php

$image_width   = 700;
$image_height  = 500;
$points_number = 50;

function dekart2polar($point_x, $point_y, $center_x, $center_y)
{
	$x = $point_x - $center_x;
	$y = $center_y - $point_y;
	$a = sqrt(pow($x, 2) + pow($y, 2));
	if($a == 0)
	{
		$f = 0;
	}
	else
	{
		$f = atan($y / $x);
	}
	if($x < 0)
	{
		$f += 3.14159265;
	}
	elseif($y < 0)
	{
		$f += 2 * 3.14159265;
	}
	return array($a, $f);
}

function polar2dekart($point_a, $point_f, $center_x, $center_y)
{
	$x = $point_a * cos($point_f) + $center_x;
	$y = $center_y - $point_a * sin($point_f);
	return array($x, $y);
}

$_POINTS = array();
for($i = 0; $i < $points_number; $i++)
{
	$_POINTS[] = array(round(mt_rand(0, $image_width)), round(mt_rand(0, $image_height)));
}

$image = imagecreatetruecolor($image_width, $image_height);
imagefill($image, 1, 1, imagecolorallocate($image, 255, 255, 255));

$max_x = $max_y = 0;
$min_x = $min_y = false;
foreach($_POINTS as $point)
{
	$max_x = max($max_x, $point[0]);
	$max_y = max($max_y, $point[1]);
	$min_x = $min_x === false ? $point[0] : min($min_x, $point[0]);
	$min_y = $min_y === false ? $point[1] : min($min_y, $point[1]);
	
	// для отладки - если на картинке останутся чёрные точки, значит, алгоритм дерьмо
	imagesetpixel($image, $point[0], $point[1], 0);
}
$center_x = ($max_x - $min_x) / 2;
$center_y = ($max_y - $min_y) / 2;

$_POINTS_POLAR = array();
foreach($_POINTS as $point)
{
	$_POINTS_POLAR[] = dekart2polar($point[0], $point[1], $center_x, $center_y);
}

usort($_POINTS_POLAR, create_function('$a, $b', 'return $a[1] > $b[1];'));

$red = imagecolorallocate($image, 255, 0, 0);

$prev_x = $prev_y = false;
foreach($_POINTS_POLAR as $point)
{
	$point = polar2dekart($point[0], $point[1], $center_x, $center_y);
	$x = round($point[0]);
	$y = round($point[1]);
	if($prev_x !== false)
	{
		imageline($image, $prev_x, $prev_y, $x, $y, $red);
	}
	else
	{
		$first_point = array($x, $y);
	}
	$prev_x = $x;
	$prev_y = $y;
}
imageline($image, $x, $y, $first_point[0], $first_point[1], $red);
imagepng($image, 'circular.png');
imagedestroy($image);

?>

Результат выполнения: