J'ai deux points a et b et un cadre de délimitation à 0,0, w, h. Les deux points sont dans la boîte de délimitation. Comment puis-je étendre le segment de ligne créé par a et b pour trouver les points c et d où la ligne coupe la boîte?Étendre un segment de ligne à un cadre de délimitation
*c-------------*
| \ |
| \ |
| a |
| \ |
| \ |
| b |
| \ |
*--------d-----*
Obtenir la equation for the line
Pour chaque (vertical) côté prendre que X et Y pour résoudre - vérifier si Y se situe entre le haut et le bas.
Sinon, utilisez les valeurs Y du côté horizontal et résolvez pour 'X'
Ok, si vous vous trompez, regardons un exemple: Supposons w = 6, et h = 5, et supposons que le le segment de ligne est compris entre (3,4) et (2,1).
y
^
|
6
5------------
4 x |
3 |
2 |
1 x |
0 1 2 3 4 5 6 -->x
Trouvons la pente,
m = (y2-y1)/(x2-x1) = (4-1)/(3-2) = 3
Maintenant, le point d'intersection où c, y = mx + c. En utilisant le premier point (2,1),
1 = 3*2 + c => c = -5.
Par conséquent, l'équation de la droite est y = 3x -5 ou 3x - y - 5 = 0.
Maintenant, branchez la valeur des lignes de délimitation en utilisant les conditions aux limites y>=0 AND y<=5 et 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)
Depuis la ligne est que nous savons droit que le gradient est:
gradient = (ax - bx)/(ay - by)
En fait, pour tout point X, Y sur la ligne:
gradient = (X - bx)/(Y - by)
Réarranger nous obtenons les expressions suivantes qui nous permettent de trouver X donnée Y ou Y donné X:
X = (gradient * (Y - by)) + bx
Y = ((X - bx)/gradient) + by
Nous avons aussi les limites de la boîte, appelez les leftX, rightx, topy et bottomy.
Nous pouvons déterminer les points auxquels la droite coupe chacune de ces limites en utilisant les équations ci-dessus.
Y = ((leftx - bx)/gradient) + by
donne une certaine valeur pour Y lorsque X = leftx.
La vraie question est de savoir si ce point de ligne est à l'intérieur de la boîte. Dans votre exemple, nous obtiendrions une valeur de Y plus grande que topy et donc nous pouvons conclure que la ligne ne se croise pas avec le bord gauche de la boîte.
Calculez les quatre points d'intersection et vous constaterez que seulement deux d'entre eux sont dans les limites de la boîte. Ce sont les deux dont vous avez besoin.Bien sûr, dans les cas particuliers où vos points C et D sont en fait les coins même de la boîte, votre solution leftx sera le même point que votre topy solution (dans votre exemple: pourrait être leftx et bottomy si la ligne est inclinée dans l'autre sens).
La meilleure façon de répondre était, pour moi, d'expérimenter avec ce sujet, car il m'intéresse.
J'ai utilisé Processing pour la partie visuelle (et son PVector, mais il est trivial dans son utilisation ici). Fondamentalement, c'est du code Java. J'ai utilisé la formule de l'article Wikipedia's Line-line intersection.
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;
}
C'est un hack rapide, pas optimisé et tout. Mais ça marche ... :-)
Amusant, hier soir, j'ai réalisé que ma solution était un peu trop générique pour le problème donné ... C'est sympa d'avoir une solution générique, mais pour tester contre la verticale et lignes horizontales seulement, les formules peuvent être beaucoup plus simples.
J'ai donc écrit une version simplifiée et je suis venu ici pour le montrer ... pour voir que la première réponse, la réponse acceptée, vient de le dire! Je l'indice négligé, sauter à la solution plus générique ...
Quoi qu'il en soit, comme cela peut intéresser d'autres visiteurs, voici la version alternative:
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);
}
Il fait moins de créations d'objets, qui c'est une bonne chose. Dans un programme appelant intensivement ces routines, j'éviterais même complètement la création d'objets (en passant autour d'un objet pour obtenir des résultats), car le garbage collection peut ralentir beaucoup d'applications où le framerate est important (incidence visible).
Je le fais déjà et ça ne marche pas pour moi, c'est pourquoi j'ai demandé. –
Mais je le faisais mal, et maintenant c'est corrigé. Apparemment, je ne me souviens pas de l'algèbre de 7e année –