Как проверить, пересекает ли отрезок линии выровненную по оси прямоугольник в 2D? Сегмент определяется двумя его концами: p1, p2. Прямоугольник определяется с верхними и нижними правыми точками.
Как проверить, пересекает ли отрезок линии выровненную по оси прямоугольник в 2D?
Ответ 1
Оригинальный плакат хотел бы ОБНАРУЖИТЬ пересечение между сегментом линии и полигоном. Не нужно было LOCATE пересечение, если оно есть. Если вы так выразились, вы можете сделать меньше работы, чем Лян-Барский или Коэн-Сазерленд:
Пусть конечные точки отрезка равны p1 = (x1 y1) и p2 = (x2 y2).
Пусть углы прямоугольника (xBL yBL) и (xTR yTR).
Тогда все, что вам нужно сделать, это
а. Проверьте, находятся ли все четыре угла прямоугольника на одной стороне линии. Неявное уравнение для линии через p1 и p2 имеет вид:
F (x y) = (y2-y1) * x + (x1-x2) * y + (x2 * y1-x1 * y2)
Если F (x y) = 0, (x y) - ON линия.
Если F (x y) > 0, (x y) "выше" линии.
Если F (x y) 0, (x y) находится "ниже" линии.
Подставьте все четыре угла в F (x y). Если они все отрицательные или все положительные, пересечения нет. Если некоторые положительные и некоторые отрицательные, перейдите к шагу B.
В. Проецируйте конечную точку на ось x и проверьте, пересекает ли тень сегмента тень полигона. Повторите на оси y:
Если (x1 > xTR и x2 > xTR), то нет пересечения (строка справа от прямоугольника).
Если (x1 < xBL и x2 < xBL) нет пересечения (строка слева от прямоугольника).
Если (y1 > yTR и y2 > yTR), пересечение (линия над прямоугольником).
Если (y1 < yBL и y2 < yBL), то нет пересечения (строка ниже прямоугольника).
иначе, есть пересечение. Коэн-Сазерленд или какой-либо другой код, упомянутый в других ответах на ваш вопрос.
Вы можете, конечно, сначала сделать B, затем A.
Алехо
Ответ 2
Написал довольно простое и эффективное решение:
bool SegmentIntersectRectangle(double a_rectangleMinX,
double a_rectangleMinY,
double a_rectangleMaxX,
double a_rectangleMaxY,
double a_p1x,
double a_p1y,
double a_p2x,
double a_p2y)
{
// Find min and max X for the segment
double minX = a_p1x;
double maxX = a_p2x;
if(a_p1x > a_p2x)
{
minX = a_p2x;
maxX = a_p1x;
}
// Find the intersection of the segment and rectangle x-projections
if(maxX > a_rectangleMaxX)
{
maxX = a_rectangleMaxX;
}
if(minX < a_rectangleMinX)
{
minX = a_rectangleMinX;
}
if(minX > maxX) // If their projections do not intersect return false
{
return false;
}
// Find corresponding min and max Y for min and max X we found before
double minY = a_p1y;
double maxY = a_p2y;
double dx = a_p2x - a_p1x;
if(Math::Abs(dx) > 0.0000001)
{
double a = (a_p2y - a_p1y) / dx;
double b = a_p1y - a * a_p1x;
minY = a * minX + b;
maxY = a * maxX + b;
}
if(minY > maxY)
{
double tmp = maxY;
maxY = minY;
minY = tmp;
}
// Find the intersection of the segment and rectangle y-projections
if(maxY > a_rectangleMaxY)
{
maxY = a_rectangleMaxY;
}
if(minY < a_rectangleMinY)
{
minY = a_rectangleMinY;
}
if(minY > maxY) // If Y-projections do not intersect return false
{
return false;
}
return true;
}
Ответ 3
Поскольку ваш прямоугольник выровнен, Liang-Barsky может быть хорошим решением. Это быстрее, чем Коэн-Сазерленд, если скорость здесь значительна.
Объяснение сигграфа
Еще одно хорошее описание
И, конечно же, Википедия
Ответ 4
Вы также можете создать прямоугольник из сегмента и проверить, сталкивается ли с ним другой прямоугольник, поскольку это всего лишь серия сравнений. Из источника pygame:
def _rect_collide(a, b):
return a.x + a.w > b.x and b.x + b.w > a.x and \
a.y + a.h > b.y and b.y + b.h > a.y
Ответ 5
Используйте алгоритм Коэн-Сазерленд.
Он используется для отсечения, но может быть слегка изменен для этой задачи. Он разделяет 2D-пространство на доску с тик-таком и ваш прямоугольник как "центральный квадрат".
затем он проверяет, в какой из девяти областей каждая из двух строк находится в вашей строке.
- Если обе точки левые, правые, верхние или нижние, вы отклоняете тривиально.
- Если какая-либо точка внутри, вы принимаете тривиально.
- В редких остальных случаях вы можете сделать математику, чтобы пересечься с тем, какие стороны прямоугольника можно пересечь, в зависимости от того, в каких регионах они находятся.
Ответ 6
Или просто используйте/скопируйте код уже в методе Java
java.awt.geom.Rectangle2D.intersectsLine(double x1, double y1, double x2, double y2)
Ниже приведен метод после преобразования в статический для удобства:
/**
* Code copied from {@link java.awt.geom.Rectangle2D#intersectsLine(double, double, double, double)}
*/
public class RectangleLineIntersectTest {
private static final int OUT_LEFT = 1;
private static final int OUT_TOP = 2;
private static final int OUT_RIGHT = 4;
private static final int OUT_BOTTOM = 8;
private static int outcode(double pX, double pY, double rectX, double rectY, double rectWidth, double rectHeight) {
int out = 0;
if (rectWidth <= 0) {
out |= OUT_LEFT | OUT_RIGHT;
} else if (pX < rectX) {
out |= OUT_LEFT;
} else if (pX > rectX + rectWidth) {
out |= OUT_RIGHT;
}
if (rectHeight <= 0) {
out |= OUT_TOP | OUT_BOTTOM;
} else if (pY < rectY) {
out |= OUT_TOP;
} else if (pY > rectY + rectHeight) {
out |= OUT_BOTTOM;
}
return out;
}
public static boolean intersectsLine(double lineX1, double lineY1, double lineX2, double lineY2, double rectX, double rectY, double rectWidth, double rectHeight) {
int out1, out2;
if ((out2 = outcode(lineX2, lineY2, rectX, rectY, rectWidth, rectHeight)) == 0) {
return true;
}
while ((out1 = outcode(lineX1, lineY1, rectX, rectY, rectWidth, rectHeight)) != 0) {
if ((out1 & out2) != 0) {
return false;
}
if ((out1 & (OUT_LEFT | OUT_RIGHT)) != 0) {
double x = rectX;
if ((out1 & OUT_RIGHT) != 0) {
x += rectWidth;
}
lineY1 = lineY1 + (x - lineX1) * (lineY2 - lineY1) / (lineX2 - lineX1);
lineX1 = x;
} else {
double y = rectY;
if ((out1 & OUT_BOTTOM) != 0) {
y += rectHeight;
}
lineX1 = lineX1 + (y - lineY1) * (lineX2 - lineX1) / (lineY2 - lineY1);
lineY1 = y;
}
}
return true;
}
}
Ответ 7
Быстрый поиск Google вывел страницу с кодом С++ для проверки пересечения.
В основном он проверяет пересечение между линией и каждой границей или прямоугольником.
Ответ 8
Я сделал небольшое решение для салфеток.
Далее найдите m и c и, следовательно, уравнение y = mx + c
y = (Point2.Y - Point1.Y) / (Point2.X - Point1.X)
Замените координаты P1, чтобы теперь найти c
Теперь для вершины прямоугольника поместите значение X в линейное уравнение, получите значение Y и посмотрите, находится ли значение Y в границах прямоугольника, показанных ниже
(вы можете найти постоянные значения X1, X2, Y1, Y2 для прямоугольника таким образом, что)
X1 <= x <= X2 &
Y1 <= y <= Y2
Если значение Y удовлетворяет указанному выше условию и лежит между (Point1.Y, Point2.Y) - мы имеем пересечение. Попробуйте каждую вершину, если этот не сможет выполнить разрез.
Ответ 9
Я смотрел на аналогичную проблему, и вот что я придумал. Сначала я сравнивал края и кое-что понял. Если средняя точка края, которая попала в противоположную ось первого окна, находится в пределах половины длины этого края внешних точек на первой в той же самой оси, тогда есть где-то пересечение этой стороны. Но это было одно измерение и требовало взглянуть на каждую сторону второго ящика, чтобы понять.
Мне внезапно пришло в голову, что если вы найдете "середину" второго блока и сравните координаты середины, чтобы увидеть, попадают ли они в 1/2 длины стороны (второго блока) внешних размеров из первого, то есть где-то пересечение.
i.e. box 1 is bounded by x1,y1 to x2,y2
box 2 is bounded by a1,b1 to a2,b2
the width and height of box 2 is:
w2 = a2 - a1 (half of that is w2/2)
h2 = b2 - b1 (half of that is h2/2)
the midpoints of box 2 are:
am = a1 + w2/2
bm = b1 + h2/2
So now you just check if
(x1 - w2/2) < am < (x2 + w2/2) and (y1 - h2/2) < bm < (y2 + h2/2)
then the two overlap somewhere.
If you want to check also for edges intersecting to count as 'overlap' then
change the < to <=
Конечно, вы могли бы так же легко сравнить наоборот (проверяя середину поля 1 в пределах 1/2 длины внешних размеров окна 2)
И даже большее упрощение - сдвиньте среднюю точку на половину длины, и она будет идентичной точке начала этого окна. Это означает, что теперь вы можете проверить только ту точку, которая попадает в пределы диапазона, и, перемещая ящик вверх и влево, нижний угол теперь является нижним углом первого окна. Гораздо меньше математики:
(x1 - w2) < a1 < x2
&&
(y1 - h2) < b1 < y2
[overlap exists]
или не замещаемый:
( (x1-(a2-a1)) < a1 < x2 ) && ( (y1-(b2-b1)) < b1 < y2 ) [overlap exists]
( (x1-(a2-a1)) <= a1 <= x2 ) && ( (y1-(b2-b1)) <= b1 <= y2 ) [overlap or intersect exists]
Ответ 10
пример кода в PHP (я использую объектную модель, которая имеет методы для таких вещей, как getLeft(), getRight(), getTop(), getBottom() для получения внешних координат многоугольника, а также имеет getWidth ( ) и getHeight() - в зависимости от того, какие параметры были ему поданы, он будет вычислять и кэшировать неизвестные, т.е. я могу создать многоугольник с x1, y1 и... w, h или x2, y2, и он может рассчитать остальные)
Я использую 'n' для обозначения "нового" элемента, который проверяется для перекрытия ($ nItem - это экземпляр моего объекта polygon) - элементы, которые будут проверяться снова [это программа рюкзака bin/sort], находятся в массив, состоящий из большего числа экземпляров (одного и того же) объекта полигона.
public function checkForOverlaps(BinPack_Polygon $nItem) {
// grab some local variables for the stuff re-used over and over in loop
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) &&
((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return false;
}
}
return true;
}
Ответ 11
Пример кода для моего решения (в php):
// returns 'true' on overlap checking against an array of similar objects in $this->packed
public function checkForOverlaps(BinPack_Polygon $nItem) {
$nX = $nItem->getLeft();
$nY = $nItem->getTop();
$nW = $nItem->getWidth();
$nH = $nItem->getHeight();
// loop through the stored polygons checking for overlaps
foreach($this->packed as $_i => $pI) {
if(((($pI->getLeft() - $nW) < $nX) && ($nX < $pI->getRight())) && ((($pI->getTop() - $nH) < $nY) && ($nY < $pI->getBottom()))) {
return true;
}
}
return false;
}
Ответ 12
Здесь javascript-версия @metalal answer
var isRectangleIntersectedByLine = function (
a_rectangleMinX,
a_rectangleMinY,
a_rectangleMaxX,
a_rectangleMaxY,
a_p1x,
a_p1y,
a_p2x,
a_p2y) {
// Find min and max X for the segment
var minX = a_p1x
var maxX = a_p2x
if (a_p1x > a_p2x) {
minX = a_p2x
maxX = a_p1x
}
// Find the intersection of the segment and rectangle x-projections
if (maxX > a_rectangleMaxX)
maxX = a_rectangleMaxX
if (minX < a_rectangleMinX)
minX = a_rectangleMinX
// If their projections do not intersect return false
if (minX > maxX)
return false
// Find corresponding min and max Y for min and max X we found before
var minY = a_p1y
var maxY = a_p2y
var dx = a_p2x - a_p1x
if (Math.abs(dx) > 0.0000001) {
var a = (a_p2y - a_p1y) / dx
var b = a_p1y - a * a_p1x
minY = a * minX + b
maxY = a * maxX + b
}
if (minY > maxY) {
var tmp = maxY
maxY = minY
minY = tmp
}
// Find the intersection of the segment and rectangle y-projections
if(maxY > a_rectangleMaxY)
maxY = a_rectangleMaxY
if (minY < a_rectangleMinY)
minY = a_rectangleMinY
// If Y-projections do not intersect return false
if(minY > maxY)
return false
return true
}