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

Question

J'ai une ligne qui va de points de A à B; je l'ai (x,y) de deux points. J'ai aussi un rectangle de centre B et de la largeur et la hauteur du rectangle.

J'ai besoin de trouver un point dans la ligne qui coupe le rectangle. Est-il une formule qui me donne l' (x,y) de ce point?

PS: je travaille avec C#, mais une solution dans un langage similaire serait bien.

Merci

Answer 1

Le point A est toujours à l'extérieur du rectangle et le point B est toujours au centre du rectangle

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, puis la ligne de coupe:
  • Le bord droit si Ax > Bx
  • Le bord gauche si Ax < Bx.
• Si-w/2 < = h/2)/s <= w/2, puis la ligne de coupe:
  • Le bord supérieur si Ay > Par
  • Le bord inférieur si Ay < Par.

Answer 2

Vous voudrez peut-être consulter les Graphiques des Gemmes (http://tog.acm.org/resources/GraphicsGems/gemsii/xlines.c) - c'est un classique, un ensemble de routines pour les graphiques et comprend un grand nombre d'algorithmes nécessaires. Même si c'est en C et légèrement daté les algorithmes encore de l'éclat et il doit être facile à transférer à d'autres langues.

Pour votre problème actuel de la juste créer les quatre lignes du rectangle et de voir ce qui se croisent votre ligne.

Answer 3

Voici une solution en Java qui retourne vrai si un segment de ligne (les 4 premiers paramètres) coupe l'axe aligné rectangle (les 4 derniers paramètres). Il serait trivial de retour le point d'intersection au lieu d'un booléen. Il fonctionne en vérifiant d'abord si complètement à l'extérieur, d'autre à l'aide de l'équation de droite y=m*x+b. Nous savons que les lignes qui composent le rectangle sont de l'axe aligné, de sorte que les contrôles 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 raccourci si le début ou la fin d'un segment est à l'intérieur du rectangle, mais il est probablement mieux de faire le calcul, qui vous permettra de toujours retourner true si l'une ou les deux de fin de segment sont à l'intérieur. Si vous souhaitez créer un raccourci de toute façon, insérez le code ci-dessous après la "complètement en dehors de" vérifier.

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

Answer 4

Je ne vais pas vous donner un programme pour le faire, mais ici, c'est comment vous pouvez le faire:

• calculer l'angle de la ligne
• calculer l'angle d'une ligne tirée du centre du rectangle à l'un de ses coins
• basé sur les angles de déterminer de quel côté de la ligne de croiser le rectangle
• calculer l'intersection entre le côté du rectangle et de la ligne

Answer 5

Je ne sais pas si c'est la meilleure façon, mais ce que vous pourriez faire est de déterminer la proportion de la ligne qui est à l'intérieur du rectangle. Vous pouvez obtenir ce à partir de la largeur du rectangle et la différence entre les coordonnées x de A et de B (ou de la hauteur et y coordonnées; basé sur la largeur et la hauteur, vous pouvez vérifier quels cas s'applique, et l'autre sera sur l'extension d'un côté du rectangle). Quand vous avez cela, il suffit de prendre la partie de l'vecteur de B à A et que vous avez votre point d'intersection des coordonnées.