Как я могу рассчитать точки вдоль линии в PHP?

Question

Я прошу прощения, если это слишком просто, но я - самая далекая вещь из математики, и у меня возникли проблемы с преобразованием абстрактных формул в работоспособный код.Я знаю формулу для линии, но превращение ее в код заставляет мою голову кружиться.И подчеркивая мой отладчик кода.

Учитывая систему координат двумерной сетки, мне нужно иметь возможность указать начальную точку X1, Y1 и конечную точку X2, Y2 и вычислить список всех ячеек сетки непосредственно налиния между этими двумя точками.

Так что если ...

X1,Y1 = 3,3
X2,Y2 = 0,5

Я бы хотел вычислить массив точек

3,3
2,4
1,4
0,5

Или что-то в этом роде.Также очень важно, чтобы я мог перечислять эти точки по порядку - как и выше, я начинаю с начала координат X, Y и двигаюсь к пункту назначения X, Y.

(И нет, этоэто не домашняя работа - я видел, что здесь задавали много других математических вопросов, так что я сразу же все уясню. Возможно, если бы я сделал это как домашнюю работу 25 лет назад, мне бы не понадобилосьспросить сейчас!)

Я нашел PHP Найти координаты между двумя точками , что, кажется, говорит о решении, но комментарии показывают, что «принятый» ответ не завершен.

Большое спасибо.

Answer 1

Похоже, вашей лучшей ставкой может быть Алгоритм Брезенхема для рисования линии , за исключением того, что вместо построения точек вы будете захватывать значения x, y.

Answer 2

Итак, для большей информации, вот функция PHP, которая всегда будет возвращать точки с первым элементом массива в качестве источника и последним в качестве пункта назначения.Это проверено и работает, и является адаптацией http://alex.moutonking.com/wordpress/?p=44.

function bresenham($x1, $y1, $x2, $y2, $guaranteeEndPoint=true) {
    $xBegin = $x1;
    $yBegin = $y1;
    $xEnd = $x2;
    $yEnd = $y2;
    $dots = array();

    $steep = abs($y2 - $y1) > abs($x2 - $x1);

    if ($steep) {
        $tmp = $x1;
        $x1 = $y1;
        $y1 = $tmp;
        $tmp = $x2;
        $x2 = $y2;
        $y2 = $tmp;
    }

    if ($x1 > $x2) {
        $tmp = $x1;
        $x1 = $x2;
        $x2 = $tmp;
        $tmp = $y1;
        $y1 = $y2;
        $y2 = $tmp;
    }

    $deltax = floor($x2 - $x1);
    $deltay = floor(abs($y2 - $y1));
    $error = 0;
    $deltaerr = $deltay / $deltax;
    $y = $y1;
    $ystep = ($y1 < $y2) ? 1 : -1;

    for ($x = $x1; $x < $x2; $x++) {
        $dots[] = $steep ? array($y, $x) : array($x, $y);       
        $error += $deltaerr;        
        if ($error >= 0.5) {
            $y += $ystep;
            $error -= 1;
        }
    } 

    if ($guaranteeEndPoint) {
    if ((($xEnd - $x) * ($xEnd - $x) + ($yEnd - $y) * ($yEnd - $y)) < (($xBegin - $x) * ($xBegin - $x) + ($yBegin - $y) * ($yBegin - $y))) {
        $dots[] = array($xEnd, $yEnd);
    } else 
        $dots[] = array($xBegin, $yBegin);
    }

    if ($dots[0][0] != $xBegin and $dots[0][1] != $yBegin) {
        return array_reverse($dots);        
    } else {
        return $dots;
    }
}

Answer 3

Я предполагаю, что вам нужны координаты целых чисел, поскольку это то, что вы перечислили в примере.Но обратите внимание, что это не обязательно так для любого произвольного набора (x1, y1) и (x2, y2).Мой ответ здесь даст вам только целые числа x-координат.

Я бы использовал двухточечную форму линейного уравнения.yi = (y2-y1) / (x2-x1) * (xi-x1) + y1 где (xi, yi) - это точки, которые вы ищете.

for ($xi=$x1; $xi<$x2; $xi++) {
  $yi = ($y2-$y1)/($x2-$x1)*($xi-$x1) + $y1
  echo $xi + "," + $yi
}

Просто убедитесь, что у вас есть $x1 < $x2 перед запуском вышеуказанного кода.

Более сложная ситуация возникает, когда вы рисуете линию между двумя произвольными точками (x1, y1) и (x2, y2) и хотите вывести список квадратов (ячейки сетки) пересекаются этой линией.

Answer 4

похоже, что вы ищете методы интерполяции, проверьте это: http://paulbourke.net/miscellaneous/interpolation/ (что вам нужно, это линейная интерполяция)

Answer 5

Я не знаю, что это особенно элегантно, но вот как бы я это сделал:

function getLinePoints( $startPoint, $endPoint ){
    $totalSteps = max( abs( $startPoint[0] - $endPoint[0] ), abs( $startPoint[1] - $endPoint[1] ) );
    if ( $totalSteps == 0 ){
      return $startPoint;
    }
    $xStep = ( $endPoint[0] - $startPoint[0] ) / $totalSteps;
    $yStep = ( $endPoint[1] - $startPoint[1] ) / $totalSteps;

    $points[] = $currentPoint = $startPoint;
    for( $step = 0; $step < $totalSteps; $step++ ){
        $currentPoint[0] += $xStep;
        $currentPoint[1] += $yStep;
        $points[] = array( round( $currentPoint[0], 0 ), round( $currentPoint[1], 0 ) );
    }
    return $points;
}

$pointA = array( 3, 3 );
$pointB = array( 0, 5 );
$points = getLinePoints( $pointA, $pointB );

Для этого нужно выполнить следующие шаги:

1. Получите общее количество точек, которые вам нужно пройти по горизонтали или вертикали.
2. Вычисляет, как далеко вам придется продвигаться по горизонтали или вертикали на каждом шаге.
3. Создает массив точек с координатами, округленными до целых чисел.

Возвращаемое значение должно быть:

Array(
    Array( 3, 3 ),
    Array( 2, 4 ),
    Array( 1, 4 ),
    Array( 0, 5 )
)