Comment vérifier si le segment coupe un rectangle?

Si vous avez 2 points (x1, y1) et (x2, y2), qui représentent les deux coins opposés d'un rectangle, et les 2 autres points, (x3,y3) et (x4,y4), qui représentent les 2 extrémités d'un segment de ligne, comment pouvez-vous vérifier si le segment de ligne coupe le rectangle?

(Le segment de ligne est juste le segment compris entre la donnée des points de terminaison. Il n'est pas d'une infinie longueur de la ligne définie par ces deux points.)

InformationsquelleAutor omega | 2013-04-24
  1. 27

    Une option très simple serait d'utiliser un algorithme standard pour vérifier si deux segments se coupent pour vérifier si les segments de ligne coupe l'un des quatre segments qui composent les coins de la boîte. Il est calcul très efficace pour vérifier si deux segments de ligne se croisent, donc je m'attends à ce que ce pouvait courir très vite.

    Espérons que cette aide!

    • Il y a un cas qui n'est pas géré par l'idée donnée par @templatetypedef: le cas où les deux extrémités du segment de ligne sont à l'intérieur du rectangle. Mais ce cas est facile à vérifier: x1 < x3 && x3 < x2 && y1 < y3 && y3 < y2.
    • Sauf que si c'est inclus dans le rectangle, il ne coupe pas le rectangle.
    • cela dépend si l'on considère le rectangle comme-est, ou seulement la limite de.
    • Quelle est la meilleure façon de gérer le cas où le segment de ligne passe directement par un coin du rectangle, ainsi à l'origine d'intersection des contrôles avec les deux côtés du rectangle de toucher le coin de la panne?
    • Ne pas passer les tests de collision si la ligne de frappe un corner? Supposons que vous disposez d'un système inclusif de vérifier pour chaque bord, vous devriez être bien.
    • Oui, vous avez raison. J'ai pensé que j'étais une erreur d'arrondi, mais mon segment de ligne d'intersection de code était juste vérifier exclusivement, pas inclusivement. Merci! (Je les fais, quand même, me demande encore si c'est possible pour les erreurs d'arrondi pour causer des problèmes ici.)

    InformationsquelleAutor templatetypedef
  2. 1

    De comprendre comment obtenir la formule pour tester si une ligne du segment coupe un rectangle, il est important de se rappeler les propriétés de la vecteur produit scalaire.

    Représenter la ligne du segment comme une unité, et un vecteur de distance entre la ligne du segment du point de départ et l'origine. Voici un code C# pour calculer qu'à partir de la PointF variables a_ptStart et a_ptEnd, à l'aide d'un Vector:

    Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y);
double dLengthLine = vecLine.Length;
vecLine /= dLengthLine;
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y));

    Vous aurez aussi besoin de calculer le vecteur perpendiculaire, et sa distance par rapport à l'origine, pour le segment de ligne. La rotation d'un vecteur unitaire de 90° est facile.

    Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X);
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y));

    En supposant que les quatre coins du rectangle sont en Vector des variables appelées vecRect1, vecRect2, vecRect3, et vecRect4, calculer la distance entre la ligne de segment et de tous les quatre coins de la cible de sélection rectangle:

    double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine;
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine;
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine;
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine;
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2,
    Math.Min(dPerpLineDist3, dPerpLineDist4)));
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2,
    Math.Max(dPerpLineDist3, dPerpLineDist4)));

    Si toutes les distances sont positives, ou toutes les distances sont négatifs, alors le rectangle est sur un côté de la ligne ou de l'autre, donc il n'y a pas d'intersection. (Zéro-mesure rectangles ne sont pas considérés comme à l'intersection avec une ligne-segment.)

    if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0
        || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0)
    /* no intersection */;

    Prochain, d'un projet, tous les quatre coins de la cible du rectangle de délimitation sur la ligne du segment. Cela nous donne la distance entre la ligne de l'origine et de la projection du rectangle de coin sur cette ligne.

    double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine;
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine;
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine;
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine;
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2,
    Math.Min(dDistLine3, dDistLine4)));
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2,
    Math.Max(dDistLine3, dDistLine4)));

    Si le rectangle de points ne tombent pas dans le segment de la ligne de mesure, alors il n'y a pas d'intersection.

    if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine)
    /* no intersection */;

    Je crois que c'est suffisant.

    • cette méthode se généralise à la 3D? En supposant que nous avons normal de ce rectangle. Avec le segment de direction et de normal que nous pouvons obtenir 3ème direction qui est perpendiculaire à la fois d'eux, de sorte que l'on peut calculer 'vecPerpLine'. Reste est à l'aide de point des produits et des soustractions de distance. Qui fait sens pour moi. Quelqu'un peut commenter mon idée ?
    InformationsquelleAutor ulatekh
  3. 0

    Obtenir le produit scalaire de tous les 4 sommets (les coins du rectangle) avec le vecteur de direction du segment de ligne. Si tous les 4 ont des valeurs de même signe, alors tous les sommets sont sur le même côté de la ligne (pas le segment de la ligne, mais la ligne infinie) et donc la ligne ne coupe pas le rectangle. Cette approche est viable que pour la 2D intersection de détection. Ceci peut être utilisé pour filtrer au travers de la plupart d'entre eux rapidement (en utilisant seulement les multiplications et d'additions). Vous aurez à faire d'autres vérifications pour des segments de ligne, au lieu de lignes.

    • J'ai pensé à ce sujet... Ce n'est pas correct. De tous les sommets peut se situer du même côté de la ligne, mais produisent un point des produits avec des signes opposés. Aussi à l'aide du vecteur de direction ne tient pas compte de l'endroit où la ligne est en réalité. On peut choisir deux lignes parallèles: celui qui coupe le rectangle, et un qui ne l'est pas. Depuis, leur direction est la même, les quatre points produits produira les mêmes valeurs pour les deux lignes, ce qui est manifestement en contradiction avec le théorème. Je -1 ce, bien que l'idée initiale a été de nice.
    InformationsquelleAutor Srinivasan