Определить, пересекает ли отрезок квадрат - PullRequest
Новая
       33

Определить, пересекает ли отрезок квадрат

4 голосов
/ 30 августа 2009

У кого-нибудь есть простой алгоритм для этого? Не нужно вращение или что-то еще. Просто находим, пересекает ли отрезок из двух точек квадрат

Ответы [ 3 ]

4 голосов
/ 30 августа 2009

Этот код должен помочь. Он проверяет, где линия пересекает стороны, а затем проверяет, находится ли это в пределах ширины квадрата. Количество пересечений возвращается. 

float CalcY(float xval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return y0 + (xval - x0)*(y1 - y0)/(x1 - x0);
}

float CalcX(float yval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return x0 + (yval - y0)*(y1 - y0)/(x1 - x0);
}

int LineIntersectsSquare(int x0, int y0, int x1, int y1, int left, int top, int right, int bottom)
{
    int intersections = 0;
    if(CalcX(bottom, x0, y0, x1, y1) < right && CalcX(bottom, x0, y0, x1, y1) > left  ) intersections++;
    if(CalcX(top   , x0, y0, x1, y1) < right && CalcX(top   , x0, y0, x1, y1) > left  ) intersections++;
    if(CalcY(left  , x0, y0, x1, y1) < top   && CalcY(left  , x0, y0, x1, y1) > bottom) intersections++;
    if(CalcY(right , x0, y0, x1, y1) < top   && CalcY(right , x0, y0, x1, y1) > bottom) intersections++;
    return intersections;
}

Примечание: этот код является теоретическим и может быть неверным, так как он не был проверен

1 голос
/ 30 августа 2009

Вы можете сделать это путем приведения вектора и подсчета количества ребер, которые он пересекает.

Если ребра, которые он пересекает, четные, он находится за пределами объекта, если ребра, которые он пересекает, нечетные, он находится внутри.

Это работает для всех замкнутых полигонов.

0 голосов
/ 30 августа 2009

Вот способ:
- отсортировать точки вершины квадрата по x-координатам
- отсортировать конечную точку линии по x-координатам
- вычислить угол от конца линии minX до каждой из двух средних (по координате x) квадратных вершин
- рассчитать угол наклона линии
- если угол линии находится в пределах возможных углов, все, что вам нужно сделать, это проверить длину, это maxX конец линии> minX вершина квадрата

Это, вероятно, сломается, если квадрат будет обращен прямо к линии, в этом случае я бы просто специально осмотрел его, проверив первый край квадрата.

...