Расширить отрезок линии до ограничительной рамки

Question

У меня есть две точки a и b и ограничивающий прямоугольник на 0,0, w, h. Обе точки находятся в ограничительной рамке. Как расширить отрезок, созданный a и b, чтобы найти точки c и d, где линия пересекает прямоугольник?

*c-------------*
| \            |
|  \           |
|   a          |
|    \         |
|     \        |
|      b       |
|       \      |
*--------d-----*

Answer 1

Получите уравнение для линии
Для каждой (вертикальной) стороны возьмите это X и решите для Y - проверьте, находится ли Y между вершиной и основанием.
Если нет, тогда используйте значения Y горизонтальной стороны и решите для 'X'

Answer 2

Забавно, вчера вечером я понял, что мое решение было слишком общим для данной проблемы ... Приятно иметь общее решение, но для тестирования только по вертикальным и горизонтальным линиям формулы могут быть намного проще .

Итак, я написал упрощенную версию и пришел сюда, чтобы показать ее ... чтобы увидеть, что первый ответ, принятый ответ, только что заявил, что! Я упустил подсказку, прыгнув на более общее решение ...

В любом случае, так как это может представлять интерес для других посетителей, вот альтернативная версия:

void FindIntersections()
{
  // Test against the sides of the BB
  PVector pT = IntersectHorizontalSegment(yMin, xMin, xMax);
  PVector pB = IntersectHorizontalSegment(yMax, xMin, xMax);
  PVector pL = IntersectVecticalSegment(xMin, yMin, yMax);
  PVector pR = IntersectVecticalSegment(xMax, yMin, yMax);

  int i = 0;
  // Eliminates the non-intersecting solutions
  if (pT != null) pointsI[i++] = pT;
  if (pB != null) pointsI[i++] = pB;
  if (pL != null) pointsI[i++] = pL;
  if (pR != null) pointsI[i++] = pR;
}

PVector IntersectHorizontalSegment(float y, float xMin, float xMax)
{
  float d = pointA.y - pointB.y;
  if (d == 0)
    return null;  // Horizontal line doesn't intersect horizontal segment (unless they have same y)

  float x = -(pointA.x * pointB.y - pointA.y * pointB.x - y * (pointA.x - pointB.x)) / d;
  println("X: " + x);
  if (x < xMin || x > xMax)
    return null;  // Not in segement

  return new PVector(x, y);
}

PVector IntersectVecticalSegment(float x, float yMin, float yMax)
{
  float d = pointA.x - pointB.x;
  if (d == 0)
    return null;  // Vertical line doesn't intersect vertical segment (unless they have same x)

  float y = (pointA.x * pointB.y - pointA.y * pointB.x - x * (pointA.y - pointB.y)) / d;
  println("Y: " + y);
  if (y < yMin || y > yMax)
    return null;  // Not in segement

  return new PVector(x, y);
}

Он меньше создает объекты, что хорошо. В программе, вызывающей эти подпрограммы интенсивно, я бы даже вообще избегал создания объектов (передача объекта для получения результатов), поскольку сборка мусора может замедлять работу многих приложений, для которых важна частота кадров (с видимым падением).

Answer 3

Лучший способ ответить для меня - поэкспериментировать с этой темой, поскольку она меня интересует.

Я использовал Обработка для визуальной части (и его PVector, но это тривиально в его использовании здесь). По сути, это код Java. Я использовал пересечение строк и линий из Википедии формула статьи.

int MARGIN = 10;
int POINT_SIZE = 7;

// Definition of the bouding box
float xMin, xMax;
float yMin, yMax;

// The two points inside the bounding box
// A PVector is just a pair of x and y coordinates
PVector pointA = new PVector();
PVector pointB = new PVector();

// The intersection points
PVector[] pointsI = new PVector[2];

void setup()
{
  size(800, 800);
  MakeBB();
  SetPoints();
  FindIntersections();
}

void draw()
{
  background(#DDFFFF);
  stroke(#FFFF00);
  fill(#8000FF);
  rect(xMin, yMin, xMax - xMin, yMax - yMin);

  noStroke();
  fill(#FF8000);
  ellipse(pointA.x, pointA.y, POINT_SIZE, POINT_SIZE);
  fill(#FF8000);
  ellipse(pointB.x, pointB.y, POINT_SIZE, POINT_SIZE);
  stroke(#FFFF00);
  strokeWeight(5);
  line(pointA.x, pointA.y, pointB.x, pointB.y);

  noStroke();
  fill(#FF0000);
  ellipse(pointsI[0].x, pointsI[0].y, POINT_SIZE * 2, POINT_SIZE * 2);
  fill(#FF0000);
  ellipse(pointsI[1].x, pointsI[1].y, POINT_SIZE * 2, POINT_SIZE * 2);
  stroke(#FF8000);
  strokeWeight(1);
  line(pointsI[0].x, pointsI[0].y, pointsI[1].x, pointsI[1].y);
}

void keyPressed()
{
  MakeBB();
  SetPoints();
  FindIntersections();
}

// Make bounding box
void MakeBB()
{
  xMin = (int) random(MARGIN, width/2);
  xMax = (int) random(width/2, width - MARGIN);
  yMin = (int) random(MARGIN, height/2);
  yMax = (int) random(height/2, height - MARGIN);
}

void SetPoints()
{
  pointA.x = (int) random(xMin, xMax);
  pointA.y = (int) random(yMin, yMax);
  pointB.x = (int) random(xMin, xMax);
  pointB.y = (int) random(yMin, yMax);
}

void FindIntersections()
{
  // The corners of the BB
  PVector pTL = new PVector(xMin, yMin);
  PVector pBL = new PVector(xMin, yMax);
  PVector pTR = new PVector(xMax, yMin);
  PVector pBR = new PVector(xMax, yMax);
  // The sides of the BB
  PVector pT = IntersectLines(pTL, pTR);
  PVector pB = IntersectLines(pBL, pBR);
  PVector pL = IntersectLines(pTL, pBL);
  PVector pR = IntersectLines(pTR, pBR);

  int i = 0;
  // Eliminates the intersection points out of the segments
  if (pT != null && pT.x >= xMin && pT.x <= xMax) pointsI[i++] = pT;
  if (pB != null && pB.x >= xMin && pB.x <= xMax) pointsI[i++] = pB;
  if (pL != null && pL.y >= yMin && pL.y <= yMax) pointsI[i++] = pL;
  if (pR != null && pR.y >= yMin && pR.y <= yMax) pointsI[i++] = pR;
}

// Compute intersection of the line made of pointA and pointB
// with the given line defined by two points
PVector IntersectLines(PVector p1, PVector p2)
{
  PVector pRes = new PVector();
  float v1 = pointA.x * pointB.y - pointA.y * pointB.x;
  float v2 = p1.x * p2.y - p1.y * p2.x;
  float d = (pointA.x - pointB.x) * (p1.y - p2.y) -
      (pointA.y - pointB.y) * (p1.x - p2.x);
  if (d == 0)
  {
    println("Ouch!");
    return null;
  }
  pRes.x = (v1 * (p1.x - p2.x) - (pointA.x - pointB.x) * v2) / d;
  pRes.y = (v1 * (p1.y - p2.y) - (pointA.y - pointB.y) * v2) / d;
  return pRes;
}

Это быстрый взлом, не оптимизированный и все. Но это работает ...: -)

Answer 4

Поскольку прямая линия, мы знаем, что градиент:

gradient = (ax - bx) / (ay - by)

Фактически для любой точки X, Y на прямой:

gradient = (X - bx) / (Y - by)

Переставляя, мы получаем следующие выражения, которые позволяют нам найти X с учетом Y или Y с учетом X:

X = (gradient * (Y - by)) + bx

Y = ((X - bx) / gradient) + by

У нас также есть границы поля, назовите их leftX , rightx , topy и bottomy .

Мы можем определить точки, в которых линия пересекает каждую из этих границ, используя приведенные выше уравнения, например:

Y = ((leftx - bx) / gradient) + by

дает некоторое значение для Y, когда X = leftx .

Реальный вопрос заключается в том, находится ли эта точка линии внутри рамки. В вашем примере мы получили бы значение Y больше topy , и поэтому мы можем заключить, что линия не пересекается с левым краем поля.

Вычислите все четыре точки пересечения, и вы обнаружите, что только две из них находятся в пределах поля. Это те, которые вам нужны. Конечно, в особых случаях, когда ваши точки C и D на самом деле являются самыми угловыми участками, ваше решение leftx будет таким же, как ваше решение topy (в вашем примере : может быть leftx и bottomy , если линия наклонена в другую сторону).

Answer 5

Хорошо, если вы ошибаетесь, давайте рассмотрим пример: предположим, что w = 6 и h = 5, и предположим, что отрезок прямой находится между (3,4) и (2,1).

y
^
|
6
5------------
4     x     |
3           |
2           |
1   x       |
0 1 2 3 4 5 6 -->x

Найдем склон,

m = (y2-y1)/(x2-x1) = (4-1)/(3-2) = 3

Теперь перехват c где, y = mx + c. Используя первую точку (2,1),

1 = 3*2 + c => c = -5.

Таким образом, уравнение линии равно y = 3x -5 или 3x - y - 5 = 0.

Теперь добавьте значение ограничивающих линий, используя граничные условия y>=0 AND y<=5 и x>=0 AND x<=6

x = 0 => 3*0 - y - 5 = 0 => y = -5    --> Out of boundary
y = 0 => 3*x - 0 - 5 = 0 => x = 5/3   --> Within boundary (Intersects bottom line)
x = 6 => 3*6 - y - 5 = 0 => y = 13    --> Out of boundary
y = 5 => 3*x - 5 - 5 = 0 => x = 10/3  --> Within boundary (Intersects top line)