Я ищу какой-нибудь эффективный код matlab, который проверяет, пересекает ли отрезок прямой квадрат Квадрат выровнен по оси, отрезок не обязательно должен быть выровнен по оси. Это процедура принятия решения, то есть возвращение Y или N, поэтому мне не требуются точки пересечения. Каждый отрезок имеет начальную точку и конечную точку.
Я начинаю с двумерного случая, но мне потребуется код, который работает для d-мерного пространства.
У меня есть быстрый код для простых случаев:
1) отрезок линии входит в квадрат (начальная точка вне квадрата, конечная точка внутри квадрата).
2) отрезок линии выходит из квадрата (начальная точка внутри квадрата, конечная точка вне квадрата).
3) отрезок внутри квадрата (начальная и конечная точки внутри квадрата).
4) отрезок линии находится далеко и не пересекает квадрат (начальная и конечная точки вне квадрата и ограничивающий прямоугольник отрезка не покрывает какую-либо часть квадрата).
Однако у меня пока нет кода для менее простой проверки, где начальная и конечная точки сегмента линии находятся за пределами квадрата, а ограничивающий прямоугольник сегмента линии покрывает часть (или всю) квадрата.
В этом случае отрезок может:
я) пересекают кончик квадратного угла,
II) пересекают два квадратных ребра, или
iii) не пересекать квадрат вообще.
Есть идеи, как проверить этот последний случай? И как заставить код работать для d-мерных отрезков и квадратов (кубов и т. Д.)?
Спасибо!
Чтобы помочь визуализировать это, я обновляю этот пост с помощью некоторого кода Matlab, который тестирует случаи 1-4 выше.
s = [1 4]; % line segment start point, [x y] coordinates
e = [3 2]; % line segment end point, [x y] coordinates
% define the square.
% instead of defining the four corners, describe the square as a bounding box.
% first row is set of min coordinates, second row is set of max coordinates.
% first column is x coordinate, second column is y coordinate.
sq = [2 1;6 5];
% now, the code below tests if the line segment start and end points are covered by the square.
% note that this code works for d-dimensional space for cases 1-5 below.
% for each line segment start point coordinate, test if it is >= both the min and max square coordinates
tmpS = s >= sq;
% if the line segment start point coordinates are all >= the square min coordinates,
% and the line segment start point coordinates are all < the square max coordinates,
% then the line segment start point is covered by the square.
coveredS = all(tmpS(1,:) == 1) && all(tmpS(2,:) == 0);
% now simply do the same for the end point line segment
tmpE = e >= sq;
coveredE = all(tmpE(1,:) == 1) && all(tmpE(2,:) == 0);
% now there is enough information to test if we are in cases 1,2, and 3.
if coveredS == false && coveredE == true
disp('Case 1: line segment enters a square');
elseif coveredS == true && coveredE == false
disp('Case 2: line segment exits a square');
elseif coveredS == true && coveredE == true
disp('Case 3: line segment within a square');
else
disp('Case still unknown! Both start and end points are outside of square');
end
% for case 4 create a bounding box around the line segement and
% compare it to the square
bb = [min([s; e]); max([s; e])]; % line segment bounding box
% if any of the line seg bounding box min coordinates are > the square max
% coordinates, or any of the line seg bounding box max coordinates are <
% the square min coordinates, then the line seg bb does not cover any part
% of the square.
if any(bb(1,:) > sq(2,:) == 1) || any(bb(2,:) < sq(1,:) == 1)
disp('Case 4: line segment is far and does not intersect square');
end
% now, if all the above checks fail, then the line seg bounding box
% partially (or fully) covers the square, and the line seg start and end
% points are not covered by the square. But, we do not know if the line
% segment in this state intersects the square or not. An additional check
% must be made here.
% so this is the question of my post - what is the the most efficient code
% that can check this state, and also works for d-dimensional space?