У кого-нибудь есть простой алгоритм для этого? Нет необходимости в вращении или что-то в этом роде. Просто найти, пересекает ли отрезок, составленный из двух точек, квадрат
Определить, пересекает ли отрезок квадрат квадрат
Ответы (3)
Этот код должен помочь. Он проверяет, где линия пересекает стороны, а затем проверяет, находится ли она в пределах ширины квадрата. Возвращается количество пересечений.
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;
}
NB: этот код является теоретическим и может быть неправильным, так как он не тестировался.
Вы можете сделать это, создав вектор и подсчитав количество ребер, которые он пересекает.
Если ребра, которые он пересекает, четные, он находится вне объекта, если ребра, которые он пересекает, нечетные, он внутри.
Это работает для всех замкнутых полигонов.
Вот способ:
- отсортировать вершины квадрата по координате x
- отсортировать конечную точку линии по координате x
- вычислить угол от minX конца линии до каждой из две средние (по x-координате) квадратные вершины
- вычислить угол линии
- если угол линии находится в пределах возможных углов, все, что вам нужно сделать, это проверить длину, это maxX конец линии > minX вершина квадрата
Это, вероятно, сломается, если квадрат прямо обращен к линии, в этом случае я бы просто выделил его, проверив первый край квадрата.