Как проверить, пересекается ли отрезок прямой с выровненным по оси прямоугольником в 2D?

Question

Как проверить, пересекается ли отрезок прямой с выровненным по оси прямоугольником в 2D? Сегмент определяется двумя концами: p1, p2. Прямоугольник определяется с верхними левым и нижним правым точками.

Answer 1

Первоначальный плакат хотел определить пересечение отрезка и многоугольника. Не было необходимости НАЙТИ пересечение, если оно есть. Если вы это и имели в виду, вы можете выполнять меньше работы, чем Лян-Барский или Коэн-Сазерленд:

Пусть конечными точками сегмента являются p1 = (x1 y1) и p2 = (x2 y2).
Пусть углы прямоугольника будут (xBL yBL) и (xTR yTR).

Тогда все, что вам нужно сделать, это

A. Проверьте, все ли четыре угла прямоугольника находятся на одной стороне линии. Неявное уравнение для линии, проходящей через p1 и p2:

F (x y) = (y2-y1) * x + (x1-x2) * y + (x2 * y1-x1 * y2)

Если F (x y) = 0, (x y) находится на линии.
Если F (x y)> 0, (x y) «выше» линии.
Если F (x y) <0, (x y) находится «ниже» линии. </p>

Подставьте все четыре угла в F (x y). Если они все отрицательные или все положительные, пересечения нет. Если некоторые из них положительные, а некоторые отрицательные, перейдите к шагу B.

B. Спроецируйте конечную точку на ось x и проверьте, пересекает ли тень сегмента тень многоугольника. Повторите по оси Y:

Если (x1> xTR и x2> xTR), пересечения нет (линия находится справа от прямоугольника).
Если (x1 Если (y1> yTR и y2> yTR), пересечения нет (линия находится над прямоугольником).
Если (y1 иначе есть пересечение. Сделайте Коэн-Сазерленд или любой другой код, упомянутый в других ответах на ваш вопрос.

Можно, конечно, сначала сделать B, потом A.

Алехо

Answer 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's and rectangle's 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's and rectangle's 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;
  }

Answer 3

Вы также можете создать прямоугольник из сегмента и проверить, сталкивается ли другой прямоугольник с ним, поскольку это просто серия сравнений. Из источника 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

Answer 4

Поскольку ваш прямоугольник выровнен, Лян-Барский может быть хорошим решением. Это быстрее, чем Коэн-Сазерленд, если скорость здесь значительна.

Сиграфное объяснение
Еще одно хорошее описание
И, конечно же, Википедия

Answer 5

Использовать алгоритм Коэна-Сазерленда .

Он используется для отсечения, но может быть слегка подправлен для этой задачи. Он делит двумерное пространство на крестики-нолики с прямоугольником в виде «центрального квадрата».
затем он проверяет, в какой из девяти областей каждая из двух точек вашей линии находится.

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

Answer 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;
    }
}

Answer 7

Быстрый поиск в Google открыл страницу с кодом C ++ для проверки пересечения.

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

Код пересечения прямоугольника и линии

Answer 8

Вот javascript-версия ответа @ metamal

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's and rectangle's 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's and rectangle's 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
}

Answer 9

Пример кода для моего решения (в 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;
}

Answer 10

пример кодирования в PHP (я использую объектную модель, которая имеет методы для таких вещей, как getLeft (), getRight (), getTop (), getBottom (), чтобы получить внешние координаты многоугольника, а также имеет getWidth ( ) и getHeight () - в зависимости от того, какие параметры были переданы ему, он будет вычислять и кэшировать неизвестные - т.е. я могу создать многоугольник с x1, y1 и ... w, h или x2, y2, и он может вычислить остальные)

Я использую 'n', чтобы обозначить 'новый' элемент, проверяемый на перекрытие ($ nItem - это экземпляр моего объекта многоугольника) - элементы, которые должны быть проверены снова [это программа для рюкзака / сортировки], находятся в массив, состоящий из нескольких экземпляров (того же самого) объекта многоугольника.

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;
}