Следующее, четвёртое, домашнее задание, предложенное программистам, было следующим: на ограниченном куске плоскости случайным образом задаются 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);
?>
Результат выполнения:
Комментариев нет:
Отправка комментария
Ублюдочный Гугл поломал форму комментариев. Извините.