Como encontrar o ponto de intersecção entre uma linha e um retângulo?

Eu tenho uma linha que vai dos pontos A ao B; Eu tenho (x, y) de ambos os pontos. Eu também tenho um retângulo centrado em B e a largura e a altura do retângulo.

Eu preciso encontrar o ponto na linha que intercepta o retângulo. Existe uma fórmula que me dê o (x, y) desse ponto?

Você pode querer verificar Graphics Gems – este é um conjunto clássico de rotinas para charts e inclui muitos dos algoritmos necessários. Embora seja em C e ligeiramente datado, os algoritmos ainda brilham e deve ser trivial transferir para outros idiomas.

Para o seu problema atual, basta criar as quatro linhas para o retângulo e ver quais delas interceptam a linha.

O ponto A está sempre fora do retângulo e o ponto B está sempre no centro do retângulo

Assumindo que o retângulo está alinhado ao eixo, isso torna as coisas muito simples:

A inclinação da linha é s = (Ay – By) / (Ax – Bx).

  • Se -h / 2 <= s * w / 2 <= h / 2 então a linha intercepta:
    • A borda direita se Ax> Bx
    • A borda esquerda se Axe
  • Se -w / 2 <= (h / 2) / s <= w / 2, a linha intercepta:
    • A borda superior se Ay> By
    • A borda inferior se Ay

Uma vez que você sabe que a aresta cruza, você conhece uma coordenada: x = Bx ± w / 2 ou y = Por ± h / 2 dependendo de qual borda você acertar. A outra coordenada é dada por y = By + s * w / 2 ou x = Bx + (h / 2) / s.

/** * Finds the intersection point between * * the rectangle * with parallel sides to the x and y axes * * the half-line pointing towards (x,y) * originating from the middle of the rectangle * * Note: the function works given min[XY] <= max[XY], * even though minY may not be the "top" of the rectangle * because the coordinate system is flipped. * Note: if the input is inside the rectangle, * the line segment wouldn't have an intersection with the rectangle, * but the projected half-line does. * Warning: passing in the middle of the rectangle will return the midpoint itself * there are infinitely many half-lines projected in all directions, * so let's just shortcut to midpoint (GIGO). * * @param x:Number x coordinate of point to build the half-line from * @param y:Number y coordinate of point to build the half-line from * @param minX:Number the "left" side of the rectangle * @param minY:Number the "top" side of the rectangle * @param maxX:Number the "right" side of the rectangle * @param maxY:Number the "bottom" side of the rectangle * @param validate:boolean (optional) whether to treat point inside the rect as error * @return an object with x and y members for the intersection * @throws if validate == true and (x,y) is inside the rectangle * @author TWiStErRob * @licence Dual CC0/WTFPL/Unlicence, whatever floats your boat * @see source * @see based on */ function pointOnRect(x, y, minX, minY, maxX, maxY, validate) { //assert minX <= maxX; //assert minY <= maxY; if (validate && (minX < x && x < maxX) && (minY < y && y < maxY)) throw "Point " + [x,y] + "cannot be inside " + "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + "."; var midX = (minX + maxX) / 2; var midY = (minY + maxY) / 2; // if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value / ±Inf = ±0) var m = (midY - y) / (midX - x); if (x <= midX) { // check "left" side var minXy = m * (minX - x) + y; if (minY <= minXy && minXy <= maxY) return {x: minX, y: minXy}; } if (x >= midX) { // check "right" side var maxXy = m * (maxX - x) + y; if (minY <= maxXy && maxXy <= maxY) return {x: maxX, y: maxXy}; } if (y <= midY) { // check "top" side var minYx = (minY - y) / m + x; if (minX <= minYx && minYx <= maxX) return {x: minYx, y: minY}; } if (y >= midY) { // check "bottom" side var maxYx = (maxY - y) / m + x; if (minX <= maxYx && maxYx <= maxX) return {x: maxYx, y: maxY}; } // edge case when finding midpoint intersection: m = 0/0 = NaN if (x === midX && y === midY) return {x: x, y: y}; // Should never happen :) If it does, please tell me! throw "Cannot find intersection for " + [x,y] + " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + "."; } (function tests() { var left = 100, right = 200, top = 50, bottom = 150; // a square, really var hMiddle = (left + right) / 2, vMiddle = (top + bottom) / 2; function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); } function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); } function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; } QUnit.test("intersects left side", function(assert) { var leftOfRect = 0, closerLeftOfRect = 25; assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top"); assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top"); assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle"); assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle"); assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle"); assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom"); assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom"); }); QUnit.test("intersects right side", function(assert) { var rightOfRect = 300, closerRightOfRect = 250; assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top"); assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top"); assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle"); assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle"); assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle"); assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom"); assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom"); }); QUnit.test("intersects top side", function(assert) { var aboveRect = 0; assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left"); assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left"); assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle"); assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle"); assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle"); assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right"); assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right"); }); QUnit.test("intersects bottom side", function(assert) { var belowRect = 200; assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left"); assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left"); assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle"); assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle"); assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle"); assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right"); assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right"); }); QUnit.test("intersects a corner", function(assert) { assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner"); assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner"); assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner"); assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner"); }); QUnit.test("on the corners", function(assert) { assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner"); assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner"); assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner"); assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner"); }); QUnit.test("on the edges", function(assert) { assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge"); assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge"); assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge"); assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge"); }); QUnit.test("validates inputs", function(assert) { assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center"); assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center"); assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center"); assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center"); assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center"); assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center"); assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center"); assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center"); assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge"); assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge"); assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge"); assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge"); assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge"); assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge"); }); QUnit.test("doesn't validate inputs", function(assert) { assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center"); assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center"); }); })(); 
   

Aqui está uma solução em Java que retorna true se um segmento de linha (os primeiros 4 parâmetros) cruzar um retângulo alinhado ao eixo (os últimos 4 parâmetros). Seria trivial retornar o ponto de interseção em vez de um booleano. Ele funciona primeiro verificando se completamente fora, senão usando a equação de linha y=m*x+b . Sabemos que as linhas que compõem o retângulo estão alinhadas com o eixo, portanto, as verificações são fáceis.

 public boolean aabbContainsSegment (float x1, float y1, float x2, float y2, float minX, float minY, float maxX, float maxY) { // Completely outside. if ((x1 <= minX && x2 <= minX) || (y1 <= minY && y2 <= minY) || (x1 >= maxX && x2 >= maxX) || (y1 >= maxY && y2 >= maxY)) return false; float m = (y2 - y1) / (x2 - x1); float y = m * (minX - x1) + y1; if (y > minY && y < maxY) return true; y = m * (maxX - x1) + y1; if (y > minY && y < maxY) return true; float x = (minY - y1) / m + x1; if (x > minX && x < maxX) return true; x = (maxY - y1) / m + x1; if (x > minX && x < maxX) return true; return false; } 

É possível fazer um atalho se o início ou o final do segmento estiver dentro do retângulo, mas provavelmente é melhor fazer apenas a matemática, que sempre retornará true se uma ou ambas as extremidades do segmento estiverem dentro. Se você quiser o atalho de qualquer maneira, insira o código abaixo após a verificação "completamente fora".

 // Start or end inside. if ((x1 > minX && x1 < maxX && y1 > minY && y1 < maxY) || (x2 > minX && x2 < maxX && y2 > minY && y2 < maxY)) return true; 

Eu não vou te dar um programa para fazer isso, mas aqui está como você pode fazer isso:

  • calcular o ângulo da linha
  • calcular o ângulo de uma linha do centro do retângulo para um dos cantos
  • com base nos ângulos determinam em qual lado a linha cruza o retângulo
  • calcular a intersecção entre o lado do retângulo e a linha

Eu não sou um fã de matemática, nem eu particularmente gosto de traduzir coisas de outros idiomas se outros já o fizeram, então sempre que eu termino uma tarefa de tradução entediante, eu a adiciono ao artigo que me levou ao código. Para evitar que alguém faça trabalho duplo.

Então, se você quiser ter esse código de interseção em C #, dê uma olhada aqui http://dotnetbyexample.blogspot.nl/2013/09/utility-classs-to-check-if-lines-andor.html

Outra opção que você pode considerar, especialmente se estiver planejando testar muitas linhas com o mesmo retângulo, é transformar seu sistema de coordenadas para alinhar os eixos com as diagonais do retângulo. Então, desde que sua linha ou raio começa no centro do retângulo, você pode determinar o ângulo, então você pode dizer qual segmento ele irá se cruzar pelo ângulo (ie <90deg 1, 90deg <<180deg seg2 etc ...). Então, claro, você tem que se transformar de volta ao sistema de coordenadas original

Embora isso pareça mais trabalho, a matriz de transformação e seu inverso podem ser calculados uma vez e depois reutilizados. Isso também se estende a retângulos dimensionais maiores com mais facilidade, onde você teria que considerar quadrantes e interseções com faces em 3D e assim por diante.

Não sei se esse é o melhor caminho, mas o que você poderia fazer é descobrir a proporção da linha que está dentro do retângulo. Você pode obter isso da largura do retângulo e da diferença entre as coordenadas x de A e B (ou coordenadas de altura e y; com base na largura e altura você pode verificar qual caso se aplica, e o outro caso estará na extensão de um lado do retângulo). Quando você tiver isso, apenas pegue a proporção do vetor de B para A e você terá as coordenadas do ponto de interseção.

Aqui está um método ligeiramente detalhado que retorna os intervalos de interseção entre uma linha (infinita) e um retângulo usando apenas matemática básica:

 // Line2 - 2D line with origin (= offset from 0,0) and direction // Rectangle2 - 2D rectangle by min and max points // Contacts - Stores entry and exit times of a line through a convex shape Contacts findContacts(const Line2 &line, const Rectangle2 &rect) { Contacts contacts; // If the line is not parallel to the Y axis, find out when it will cross // the limits of the rectangle horizontally if(line.Direction.X != 0.0f) { float leftTouch = (rect.Min.X - line.Origin.X) / line.Direction.X; float rightTouch = (rect.Max.X - line.Origin.X) / line.Direction.X; contacts.Entry = std::fmin(leftTouch, rightTouch); contacts.Exit = std::fmax(leftTouch, rightTouch); } else if((line.Offset.X < rect.Min.X) || (line.Offset.X >= rect.Max.X)) { return Contacts::None; // Rectangle missed by vertical line } // If the line is not parallel to the X axis, find out when it will cross // the limits of the rectangle vertically if(line.Direction.Y != 0.0f) { float topTouch = (rectangle.Min.Y - line.Offset.Y) / line.Direction.Y; float bottomTouch = (rectangle.Max.Y - line.Offset.Y) / line.Direction.Y; // If the line is parallel to the Y axis (and it goes through // the rectangle), only the Y axis needs to be taken into account. if(line.Direction.X == 0.0f) { contacts.Entry = std::fmin(topTouch, bottomTouch); contacts.Exit = std::fmax(topTouch, bottomTouch); } else { float verticalEntry = std::fmin(topTouch, bottomTouch); float verticalExit = std::fmax(topTouch, bottomTouch); // If the line already left the rectangle on one axis before entering it // on the other, it has missed the rectangle. if((verticalExit < contacts.Entry) || (contacts.Exit < verticalEntry)) { return Contacts::None; } // Restrict the intervals from the X axis of the rectangle to where // the line is also within the limits of the rectangle on the Y axis contacts.Entry = std::fmax(verticalEntry, contacts.Entry); contacts.Exit = std::fmin(verticalExit, contacts.Exit); } } else if((line.Offset.Y < rect.Min.Y) || (line.Offset.Y > rect.Max.Y)) { return Contacts::None; // Rectangle missed by horizontal line } return contacts; } 

Esta abordagem oferece um alto grau de estabilidade numérica (os intervalos são, em todos os casos, o resultado de uma única subtração e divisão), mas envolve algumas ramificações.

Para um segmento de linha (com pontos inicial e final), você precisaria fornecer o ponto inicial do segmento como a origem e a direção, o end - start . Calcular as coordenadas das duas interseções é um simples como entryPoint = origin + direction * contacts.Entry exitPoint = origin + direction * contacts.Exit e exitPoint = origin + direction * contacts.Exit .

Aqui está uma solução que funciona para mim. Eu suponho que o rect está alinhado com os eixos.

Dados:

 // Center of the Rectangle let Cx: number let Cy: number // Width let w: number // Height let h: number // Other Point let Ax: number let Ay: number 

Agora, traduza o ponto A pelo centro do retângulo, de modo que o retângulo esteja centralizado em O (0,0) e considere o problema no primeiro trimestre (ex. X> 0 e y> 0).

 // Coordinates Translated let Px = Math.abs(Ax - Cx) let Py = Math.abs(Ay - Cy) // Slope of line from Point P to Center let Pm = Py / Px // Slope of rectangle Diagonal let Rm = h / w // If the point is inside the rectangle, return the center let res: [number, number] = [0, 0] // Check if the point is inside and if so do not calculate if (!(Px < w / 2 && Py < h / 2)) { // Calculate point in first quarter: Px >= 0 && Py >= 0 if (Pm <= Rm) { res[0] = w / 2 res[1] = (w * Pm) / 2 } else { res[0] = h / (Pm * 2) res[1] = h / 2 } // Set original sign if (Ax - Cx < 0) res[0] *= -1 if (Ay - Cy < 0) res[1] *= -1 } // Translate back return [res[0] + Cx, res[1] + Cy]