Comment trouver le point d’intersection entre une ligne et un rectangle?

J’ai une ligne qui va des points A à B; J’ai (x, y) des deux points. J’ai aussi un rectangle centré sur B et la largeur et la hauteur du rectangle.

J’ai besoin de trouver le point dans la ligne qui coupe le rectangle. Y a-t-il une formule qui me donne le (x, y) de ce point?

Vous pourriez vouloir vérifier Graphics Gems – il s’agit d’un ensemble classique de routines pour les graphiques et comprend de nombreux algorithmes requirejs. Bien que ce soit en C et légèrement daté, les algorithmes brillent toujours et il devrait être sortingvial de les transférer dans d’autres langages.

Pour votre problème actuel, créez simplement les quatre lignes du rectangle et voyez celles qui intersectent votre ligne donnée.

Le point A est toujours en dehors du rectangle et le point B est toujours au centre du rectangle

En supposant que le rectangle est aligné sur l’axe, cela rend les choses assez simples:

La pente de la ligne est s = (Ay – By) / (Ax – Bx).

  • Si -h / 2 <= s * w / 2 <= h / 2 alors la ligne coupe:
    • Le bord droit si Ax> Bx
    • Le bord gauche si Ax
  • Si -w / 2 <= (h / 2) / s <= w / 2 alors la ligne coupe:
    • Le bord supérieur si Ay> By
    • Le bord inférieur si Ay

Une fois que vous connaissez le bord d’intersection, vous connaissez une coordonnée: x = Bx ± w / 2 ou y = par ± h / 2 selon le bord que vous frappez. L’autre coordonnée est donnée par 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"); }); })(); 
   

Voici une solution en Java qui renvoie true si un segment de ligne (les 4 premiers parameters) coupe un rectangle aligné sur l’axe (les 4 derniers parameters). Ce serait sortingvial de renvoyer le point d’intersection au lieu d’un booléen. Cela fonctionne en vérifiant d’abord si complètement en dehors, sinon en utilisant l’équation de ligne y=m*x+b . Nous soaps que les lignes qui composent le rectangle sont alignées sur les axes, donc les vérifications sont faciles.

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

Il est possible de raccourcir si le début ou la fin du segment est à l'intérieur du rectangle, mais il est probablement préférable de faire le calcul, qui retournera toujours true si l'une ou les deux extrémités du segment sont à l'intérieur. Si vous voulez le raccourci de toute façon, insérez le code ci-dessous après la vérification "complètement en dehors".

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

Je ne vous donnerai pas de programme pour le faire, mais voici comment vous pouvez le faire:

  • calculer l’angle de la ligne
  • calculer l’angle d’une ligne du centre du rectangle à l’un de ses coins
  • sur la base des angles, déterminer de quel côté la ligne coupe le rectangle
  • calculer l’intersection entre le côté du rectangle et la ligne

Je ne suis pas un fan des mathématiques et je n’aime pas particulièrement traduire des choses dans d’autres langues si d’autres l’ont déjà fait, alors chaque fois que je termine une tâche de traduction ennuyeuse, je l’ajoute à l’article qui m’a amené au code. Empêcher quiconque de faire un double travail.

Donc, si vous voulez avoir ce code d’intersection en C #, jetez un coup d’oeil ici http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html

Une autre option que vous pouvez envisager en particulier si vous envisagez de tester plusieurs lignes avec le même rectangle est de transformer votre système de coordonnées pour que les axes soient alignés avec les diagonales du rectangle. Puis, comme votre ligne ou rayon commence au centre du rectangle, vous pouvez déterminer l’angle puis vous pouvez dire quel segment il va croiser par l’angle (c.-à-d. <90deg seg 1, 90deg <180deg seg 2 etc…). Ensuite, bien sûr, vous devez revenir au système de coordonnées d'origine

Bien que cela semble fonctionner davantage, la masortingce de transformation et son inverse peuvent être calculés une fois puis réutilisés. Cela s’étend également plus facilement aux rectangles de dimensions plus élevées où vous devriez considérer les quadrants et les intersections avec des faces en 3D et ainsi de suite.

Je ne sais pas si c’est le meilleur moyen, mais ce que vous pouvez faire est de déterminer la proportion de la ligne qui se trouve à l’intérieur du rectangle. Vous pouvez obtenir cela à partir de la largeur du rectangle et de la différence entre les coordonnées x de A et B (ou les coordonnées hauteur et y; en fonction de la largeur et de la hauteur, vous pouvez vérifier quel cas s’applique et l’autre cas sera sur l’extension) d’un côté du rectangle). Lorsque vous avez ceci, prenez simplement cette proportion du vecteur de B à A et vous avez les coordonnées de votre point d’intersection.

Voici une méthode légèrement verbeuse qui renvoie les intervalles d’intersection entre une ligne (infinie) et un rectangle en utilisant uniquement des calculs de base:

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

Cette approche offre un haut degré de stabilité numérique (les intervalles sont, dans tous les cas, le résultat d’une seule soustraction et division) mais implique une certaine ramification.

Pour un segment de ligne (avec des points de début et de fin), vous devez indiquer le sharepoint départ du segment comme origine et pour direction, end - start et end - start . Le calcul des coordonnées des deux intersections est simple comme entryPoint = origin + direction * contacts.Entry et exitPoint = origin + direction * contacts.Exit .

Voici une solution qui fonctionne pour moi. Je suppose que le rect est aligné sur les axes.

Les données:

 // 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 

Maintenant, traduisez le point A par le centre du rectangle pour centrer le rectangle sur O (0,0) et considérez le problème au premier sortingmestre (c.-à-d. X> 0 et 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]