Come trovare il punto di intersezione tra una linea e un rettangolo?

Question

Ho una linea che va dai punti A a B; Ho (x, y) di entrambi i punti. Ho anche un rettangolo centrato su B e la larghezza e l'altezza del rettangolo.

Devo trovare il punto nella linea che interseca il rettangolo. C'è una formula che mi dà il (x, y) di quel punto?

Answer 1

Non ti darò un programma per fare questo, ma ecco come si può fare:

• calcolare l'angolo della linea
• calcolare l'angolo di una linea dal centro di il rettangolo di uno dei suoi angoli
• basato su angoli determinare su quale lato non intersechi la linea del rettangolo
• calcolare intersezione tra il lato del rettangolo e la linea

Answer 2

Non so se questo è il modo migliore, ma quello che potresti fare è capire la proporzione della linea che si trova all'interno del rettangolo. Puoi ottenerlo dalla larghezza del rettangolo e dalla differenza tra le coordinate x di A e B (o le coordinate di altezza e y, in base alla larghezza e all'altezza puoi controllare quale caso si applica e l'altro caso sarà sull'estensione di un lato del rettangolo). Quando hai questo, basta prendere quella proporzione del vettore da B ad A e hai le coordinate del punto di intersezione.

Answer 3

Il punto A è sempre al di fuori del rettangolo e il punto B è sempre al centro del rettangolo

Supponendo che il rettangolo è l'asse-allineati, questo rende le cose piuttosto semplice:

La pendenza della linea è s = (Ay - By)/(Ax - Bx).

• Se -h/2 < = s * w/2 < = h/2 poi la linea interseca:
  • Il bordo destro se Ax> Bx
  • Il bordo sinistro se Ax < Bx .
• Se -w/2 < = (h/2)/s < = w/2 allora la linea interseca:
  • Il bordo superiore se Ay> Per
  • Il bordo inferiore se Ay < di.

Una volta noto il bordo interseca vedi una coordinata: x = Bx ± w/2 o y = Per ± h/2 a seconda del bordo colpite. L'altra coordinata è data da y = By + s * w/2 o x = Bx + (h/2)/s.

Answer 4

Si potrebbe voler verificare Graphics Gems - questo è un classico set di routine per la grafica e include molti degli algoritmi richiesti. Sebbene sia in C e leggermente datato, gli algoritmi continuano a brillare e dovrebbe essere banale trasferirlo in altre lingue.

Per il tuo problema corrente basta creare le quattro linee per il rettangolo e vedere quali si intersecano con la tua linea indicata.

Answer 5

Ecco una soluzione in Java che restituisce true se un segmento di linea (i primi 4 parametri) interseca un rettangolo allineato sull'asse (gli ultimi 4 parametri). Sarebbe banale restituire il punto di intersezione invece di un booleano. Funziona innanzitutto controllando se completamente fuori, altrimenti usando l'equazione di linea y=m*x+b. Sappiamo che le linee che compongono il rettangolo sono allineate sull'asse, quindi i controlli sono facili.

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

E 'possibile scorciatoia se l'inizio o la fine del segmento è all'interno del rettangolo, ma probabilmente è meglio solo che la matematica, che sarà sempre ritornare vero se le estremità o entrambe segmento sono all'interno. Se si desidera comunque la scorciatoia, inserire il codice seguente dopo il controllo "completamente esterno".

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

Answer 6

io non sono un fan di matematica né mi piace particolarmente traducendo roba da altre lingue se gli altri lo hanno già fatto, quindi, quando ho completare un compito di traduzione noioso, lo aggiungo per l'articolo che mi ha portato alla codice. Per evitare che qualcuno faccia il doppio lavoro.

Quindi, se si vuole avere il codice di intersezione in C#, date un'occhiata qui http://dotnetbyexample.blogspot.nl/2013/09/utility-classes-to-check-if-lines-andor.html

Answer 7

Questo vuole essere un metodo leggermente verbose che restituisce gli intervalli di intersezione tra una linea (infinito) e un rettangolo utilizzando la matematica solo di 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; 
} 

Questo approccio offre un elevato grado di stabilità numerica (gli intervalli sono, in ogni caso, il risultato di una singola sottrazione e divisione), ma comporta qualche ramificazione.

Per un segmento di linea (con punti iniziale e finale), è necessario fornire il punto iniziale del segmento come origine e direzione, end - start. Il calcolo delle coordinate delle due intersezioni è semplice come entryPoint = origin + direction * contacts.Entry e exitPoint = origin + direction * contacts.Exit.

Answer 8

/** 
 
* 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 
 
* @see <a href="http://stackoverflow.com/a/31254199/253468">source</a> 
 
* @see <a href="http://stackoverflow.com/a/18292964/253468">based on</a> 
 
*/ 
 
function pointOnRect(x, y, minX, minY, maxX, maxY, validate) { 
 
\t //assert minX <= maxX; 
 
\t //assert minY <= maxY; 
 
\t if (validate && (minX < x && x < maxX) && (minY < y && y < maxY)) 
 
\t \t throw "Point " + [x,y] + "cannot be inside " 
 
\t \t  + "the rectangle: " + [minX, minY] + " - " + [maxX, maxY] + "."; 
 
\t var midX = (minX + maxX)/2; 
 
\t var midY = (minY + maxY)/2; 
 
\t // if (midX - x == 0) -> m == ±Inf -> minYx/maxYx == x (because value/±Inf = ±0) 
 
\t var m = (midY - y)/(midX - x); 
 

 
\t if (x <= midX) { // check "left" side 
 
\t \t var minXy = m * (minX - x) + y; 
 
\t \t if (minY <= minXy && minXy <= maxY) 
 
\t \t \t return {x: minX, y: minXy}; 
 
\t } 
 

 
\t if (x >= midX) { // check "right" side 
 
\t \t var maxXy = m * (maxX - x) + y; 
 
\t \t if (minY <= maxXy && maxXy <= maxY) 
 
\t \t \t return {x: maxX, y: maxXy}; 
 
\t } 
 

 
\t if (y <= midY) { // check "top" side 
 
\t \t var minYx = (minY - y)/m + x; 
 
\t \t if (minX <= minYx && minYx <= maxX) 
 
\t \t \t return {x: minYx, y: minY}; 
 
\t } 
 

 
\t if (y >= midY) { // check "bottom" side 
 
\t \t var maxYx = (maxY - y)/m + x; 
 
\t \t if (minX <= maxYx && maxYx <= maxX) 
 
\t \t \t return {x: maxYx, y: maxY}; 
 
\t } 
 

 
\t // edge case when finding midpoint intersection: m = 0/0 = NaN 
 
\t if (x === midX && y === midY) return {x: x, y: y}; 
 

 
\t // Should never happen :) If it does, please tell me! 
 
\t throw "Cannot find intersection for " + [x,y] 
 
\t  + " inside rectangle " + [minX, minY] + " - " + [maxX, maxY] + "."; 
 
} 
 

 
(function tests() { 
 
\t var left = 100, right = 200, top = 50, bottom = 150; // a square, really 
 
\t var hMiddle = (left + right)/2, vMiddle = (top + bottom)/2; 
 
\t function intersectTestRect(x, y) { return pointOnRect(x,y, left,top, right,bottom, true); } 
 
\t function intersectTestRectNoValidation(x, y) { return pointOnRect(x,y, left,top, right,bottom, false); } 
 
\t function checkTestRect(x, y) { return function() { return pointOnRect(x,y, left,top, right,bottom, true); }; } 
 
\t QUnit.test("intersects left side", function(assert) { 
 
\t \t var leftOfRect = 0, closerLeftOfRect = 25; 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 25), {x:left, y:75}, "point above top"); 
 
\t \t assert.deepEqual(intersectTestRect(closerLeftOfRect, top), {x:left, y:80}, "point in line with top"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 70), {x:left, y:90}, "point above middle"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, vMiddle), {x:left, y:100}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 130), {x:left, y:110}, "point below middle"); 
 
\t \t assert.deepEqual(intersectTestRect(closerLeftOfRect, bottom), {x:left, y:120}, "point in line with bottom"); 
 
\t \t assert.deepEqual(intersectTestRect(leftOfRect, 175), {x:left, y:125}, "point below bottom"); 
 
\t }); 
 
\t QUnit.test("intersects right side", function(assert) { 
 
\t \t var rightOfRect = 300, closerRightOfRect = 250; 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 25), {x:right, y:75}, "point above top"); 
 
\t \t assert.deepEqual(intersectTestRect(closerRightOfRect, top), {x:right, y:75}, "point in line with top"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 70), {x:right, y:90}, "point above middle"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, vMiddle), {x:right, y:100}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 130), {x:right, y:110}, "point below middle"); 
 
\t \t assert.deepEqual(intersectTestRect(closerRightOfRect, bottom), {x:right, y:125}, "point in line with bottom"); 
 
\t \t assert.deepEqual(intersectTestRect(rightOfRect, 175), {x:right, y:125}, "point below bottom"); 
 
\t }); 
 
\t QUnit.test("intersects top side", function(assert) { 
 
\t \t var aboveRect = 0; 
 
\t \t assert.deepEqual(intersectTestRect(80, aboveRect), {x:115, y:top}, "point left of left"); 
 
\t \t assert.deepEqual(intersectTestRect(left, aboveRect), {x:125, y:top}, "point in line with left"); 
 
\t \t assert.deepEqual(intersectTestRect(120, aboveRect), {x:135, y:top}, "point left of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, aboveRect), {x:150, y:top}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(180, aboveRect), {x:165, y:top}, "point right of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(right, aboveRect), {x:175, y:top}, "point in line with right"); 
 
\t \t assert.deepEqual(intersectTestRect(220, aboveRect), {x:185, y:top}, "point right of right"); 
 
\t }); 
 
\t QUnit.test("intersects bottom side", function(assert) { 
 
\t \t var belowRect = 200; 
 
\t \t assert.deepEqual(intersectTestRect(80, belowRect), {x:115, y:bottom}, "point left of left"); 
 
\t \t assert.deepEqual(intersectTestRect(left, belowRect), {x:125, y:bottom}, "point in line with left"); 
 
\t \t assert.deepEqual(intersectTestRect(120, belowRect), {x:135, y:bottom}, "point left of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, belowRect), {x:150, y:bottom}, "point exact middle"); 
 
\t \t assert.deepEqual(intersectTestRect(180, belowRect), {x:165, y:bottom}, "point right of middle"); 
 
\t \t assert.deepEqual(intersectTestRect(right, belowRect), {x:175, y:bottom}, "point in line with right"); 
 
\t \t assert.deepEqual(intersectTestRect(220, belowRect), {x:185, y:bottom}, "point right of right"); 
 
\t }); 
 
\t QUnit.test("intersects a corner", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(left-50, top-50), {x:left, y:top}, "intersection line aligned with top-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right+50, top-50), {x:right, y:top}, "intersection line aligned with top-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(left-50, bottom+50), {x:left, y:bottom}, "intersection line aligned with bottom-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right+50, bottom+50), {x:right, y:bottom}, "intersection line aligned with bottom-right corner"); 
 
\t }); 
 
\t QUnit.test("on the corners", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(left, top), {x:left, y:top}, "top-left corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right, top), {x:right, y:top}, "top-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(right, bottom), {x:right, y:bottom}, "bottom-right corner"); 
 
\t \t assert.deepEqual(intersectTestRect(left, bottom), {x:left, y:bottom}, "bottom-left corner"); 
 
\t }); 
 
\t QUnit.test("on the edges", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, top), {x:hMiddle, y:top}, "top edge"); 
 
\t \t assert.deepEqual(intersectTestRect(right, vMiddle), {x:right, y:vMiddle}, "right edge"); 
 
\t \t assert.deepEqual(intersectTestRect(hMiddle, bottom), {x:hMiddle, y:bottom}, "bottom edge"); 
 
\t \t assert.deepEqual(intersectTestRect(left, vMiddle), {x:left, y:vMiddle}, "left edge"); 
 
\t }); 
 
\t QUnit.test("validates inputs", function(assert) { 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle-10), /cannot be inside/, "top left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle), /cannot be inside/, "left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, vMiddle+10), /cannot be inside/, "bottom left of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle-10), /cannot be inside/, "above center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle), /cannot be inside/, "center"); 
 
\t \t assert.throws(checkTestRect(hMiddle, vMiddle+10), /cannot be inside/, "below center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle-10), /cannot be inside/, "top right of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle), /cannot be inside/, "right of center"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, vMiddle+10), /cannot be inside/, "bottom right of center"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle-10), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(left+10, vMiddle+10), /cannot be inside/, "right of left edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle-10), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(right-10, vMiddle+10), /cannot be inside/, "left of right edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, top+10), /cannot be inside/, "below top edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle-10, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t \t assert.throws(checkTestRect(hMiddle+10, bottom-10), /cannot be inside/, "above bottom edge"); 
 
\t }); 
 
\t QUnit.test("doesn't validate inputs", function(assert) { 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle-10), {x:left, y:top}, "top left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle), {x:left, y:vMiddle}, "left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle-10, vMiddle+10), {x:left, y:bottom}, "bottom left of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle-10), {x:hMiddle, y:top}, "above center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle), {x:hMiddle, y:vMiddle}, "center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle, vMiddle+10), {x:hMiddle, y:bottom}, "below center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle-10), {x:right, y:top}, "top right of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle), {x:right, y:vMiddle}, "right of center"); 
 
\t \t assert.deepEqual(intersectTestRectNoValidation(hMiddle+10, vMiddle+10), {x:right, y:bottom}, "bottom right of center"); 
 
\t }); 
 
})();

<link href="https://code.jquery.com/qunit/qunit-2.3.2.css" rel="stylesheet"/> 
 
<script src="https://code.jquery.com/qunit/qunit-2.3.2.js"></script> 
 
<div id="qunit"></div>

Answer 9

Un'altra opzione che si può prendere in considerazione soprattutto se si prevede di testare molte linee con la stessa rettangolo è di trasformare il vostro sistema di coordinate di avere gli assi allineati con diagonali del rettangolo. Quindi, dal momento che la linea o il raggio inizia al centro del rettangolo, puoi determinare l'angolo, quindi puoi dire quale segmento intersecherà per l'angolo (ad esempio < seg segg 1, 90deg < < 180deg seg 2 ecc ...). Quindi ovviamente devi tornare al sistema di coordinate originale

Anche se questo sembra più un lavoro, la matrice di trasformazione e il suo inverso possono essere calcolati una volta e poi riutilizzati. Questo si estende anche ai rettangoli di dimensione superiore più facilmente dove dovresti considerare i quadranti e le intersezioni con le facce in 3D e così via.