Выделение всех точек, в которых линии сетки пересекаются прямой линией в трехмерном декартовом графе - PullRequest
Новая
       18

Выделение всех точек, в которых линии сетки пересекаются прямой линией в трехмерном декартовом графе

1 голос
/ 28 августа 2011

Я использую PHP и сгенерировал трехмерную декартову систему координат (x, y, z). Я хочу путешествовать по прямой линии между двумя точками. Я называю каждый квадрат 1x1x1 сектором, идентифицированным соседней точкой решетки, ближайшей к началу координат. Я пытаюсь определить каждый сектор, через который проходит отрезок.

Следующий пост был полезен, но, поскольку он касается 2D-систем, это было не совсем то, что мне нужно.

PHP Найти координаты между двумя точками

Спасибо

Jason

Ответы [ 3 ]

1 голос
/ 31 августа 2011

Я не эксперт по PHP, но это то же самое решение для 3d-системы: 

// Points
$p1 = array(
    'x' => 50,
    'y' => 50,
    'z' => 20,

);

$p2 = array(
    'x' => 234,
    'y' => 177,
    'z' => 100
);

// Work out distances
$pxd = $p2['x'] - $p1['x'];
$pyd = $p2['y'] - $p1['y'];
$pzd = $p2['z'] - $p1['z'];
// Find out steps
$steps = max(abs($pxd), abs($pyd), abs($pzd));

$coords = array();

for ($i = 0; $i < $steps; ++ $i) {
    $coords[] = array(
        'x' => round($p1['x'] += $pxd / $steps),
        'y' => round($p1['y'] += $pyd / $steps),
        'z' => round($p1['z'] += $pzd / $steps)
    );
}

print_r($coords);
0 голосов
/ 29 августа 2011

Я не эксперт, но один (глупый?) Подход - написать функцию, которая находит «среднюю точку» двух координат ((x1 + x2) / 2, (y1 + y2) / 2, (z1 + z2) / 2), затем округлите их, чтобы получить действительную координату.Теперь вы можете найти всю «линию», просто рекурсивно применив функцию ко всем ногам, пока не появится новая средняя точка. 

func findMiddlePoint(a, b)
  return new Point(
        ((a.x + b.x).abs / 2).round, 
        ((a.y + b.y).abs / 2).round, 
        ((a.z + b.z).abs / 2).round)
func findLine(points, a, b)
  if a == b # no new points
    return 
  middle = findMiddlePoint(a, b)
  points.add(middle)
  findLine(points, a, middle)
  findLine(points, middle, b)

func findFullLine(a, b)
  points = []
  points.add(a)
  findLine(points, a, b)
  opints.add(b)
  return points
0 голосов
/ 28 августа 2011

Я бы посоветовал взглянуть на простой алгоритм DDA, который позволяет эффективно определять, через какие ячейки регулярной сетки проходит отрезок. Эта статья описывает это довольно хорошо, а также предоставляет пример реализации:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf

Возможно, вы захотите согласовать условие завершения для внешнего цикла, поскольку в документе рассматриваются лучи, которые, в отличие от вашего случая, не имеют конкретной точки завершения, кроме границ сетки.

...