Le parallélogramme contient Point

https://stackoverflow.com/questions/1217585

10-07-2019
|

Question

Quel est le moyen le plus rapide de décider si un point est à l'intérieur d'un parallélogramme / rhomboïde?

La solution

Bonjour à nouveau et merci pour toutes vos réponses. Entre-temps, j’ai moi-même proposé quelque chose qui, à mon avis, serait plutôt rapide:

Imaginez que nous ayons un parallélogramme couvert par PQ et PR, où PQ et PR sont des vecteurs (P, Q et R sont des angles). De plus, nous avons le point à vérifier appelé A.

Nous savons que le vecteur PA peut être divisé en deux vecteurs parallèles à PQ et à PR:

PA=n*PQ+m*PR

Nous savons maintenant que n et m DOIVENT être dans l'intervalle [0; 1], nous résolvons n et m:

n = -det(PA, PQ)/det(PQ, PR)
m = det(PA, PR)/det(PQ, PR)

Où det (PA, PQ) est le déterminant des vecteurs PA et PQ:

det(PA, PQ) = PA.x*PQ.y-PQ.x*PA.y

Si le point A est à l'intérieur du parallélogramme, alors 0 < = n < = 1 et 0 < = m < = 1, cela nous donne le pseudocode:

var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
    //inside
}
else
{
    //outside
}

Autres conseils

Imaginez un rayon émanant de votre point dans une direction. Si ce rayon traverse les lignes de votre forme un nombre impair de fois, c'est à l'intérieur de la forme. S'il traverse un nombre pair de fois, c'est en dehors de la forme.

Donc, dans votre programme, vous créez simplement une ligne invisible et vous voyez à quelle fréquence elle se croise. Actionscript a probablement une fonction intégrée pour le faire, j'imagine.

Maintenant, si vous avez une tonne d'objets et que le point ne peut être que dans un, vous pouvez accélérer les choses en utilisant un Partition d'espace binaire pour stocker les emplacements des objets. De cette façon, vous n’aurez pas à comparer votre point avec chaque objet, mais seulement avec ceux qui se trouvent à proximité.

Voir ma réponse à la question , qui est très similaire. Là, je donne ce que je pense être un test assez facile dans le cas où le parallélogramme a un de ses coins à (0,0) car il facilite l'explication de l'explication, mais il n'est pas très difficile de le modifier pour qu'il fonctionne en général.

EDIT: Étant donné que le propriétaire de la question connaît les vecteurs, je vais réécrire ma réponse dans cette langue. Supposons que le parallélogramme soit recouvert par les vecteurs PQ et PR, où P, Q et R sont des angles. Le symbole * désignera le produit scalaire. Choisissez un point q tel que Pq soit perpendiculaire à Pq*PQ=0 (c'est-à-dire PR*Pq>0) et r (par exemple, vous pourriez obtenir PR*Pr=0 en faisant pivoter PQ*Pr>0 de A de 90 degrés). . Choisissez également un point (0 < Pr*PA < Pr*PQ) && (0 < Pq*PA < Pq*PR) tel que <=> et <=>. Ensuite, un point <=> est à l'intérieur si et seulement si <=>.

Ce papier décrit une méthode permettant de déterminer la position d'un rayon et intersection quadrilatérale. Il peut être simplifié davantage si le quadrilatère est un parallélogramme.

Si vous avez un parallélogramme à côtés adjacents décrit par les vecteurs AB et AC . Tout point dans le plan du parallélogramme peut être décrit par le vecteur suivant

T(a, b) = A + a * AB + b * AC

Tout rayon peut être décrit comme une origine O et une direction D

R(t) = O + t * D

L'intersection du 2 est quand T(a, b) == R(t)

O + t * D = A + a * AB + b * AC

Résolvez ceci pour a et b et vérifiez qu'ils sont tous les deux compris entre 0 et 1. Voir le pseudocode à la fin du document pour savoir comment le mettre en œuvre.

L’équation standard d’une ligne est donnée sous la forme ax + bx + c = 0 .., mais curieusement, si vous prenez cette expression ax + bx + c et évaluez les points x, y à partir de a, b, c ligne particulière, vous constaterez que l’expression divise le plan en deux moitiés, une moitié où l’expression est supérieure à zéro, l’autre moitié où il est inférieur.

Maintenant, si vous prenez les quatre points de votre parallélogramme et calculez les coefficients a, b, c pour chaque ligne constituant un côté du parallélogramme, vous pouvez évaluer chaque expression du x, y en question et trouver sur quel côté de chaque ligne ce point est allumé. Le intérieur du parallélogramme sera un ET logique des côtés particuliers.

Ie., une fois que vous avez les a, b, c pour chacune des quatre lignes, vous pouvez faire un test quelque chose comme

if ( ((a1*x+b1*y+c1)>0) && ((a2*x+b2*y+c2)<0) && 
        ((a3*x+b3*y+c3)<0) && ((a4*x+b4*y+c4)>0) {
    // it's in!
}

... le dernier truc restant est que vous devez déterminer la "polarité" de chaque test de signe, c'est-à-dire supérieure ou inférieure à zéro. Le moyen le plus simple de le faire est d’évaluer 0,0 et de voir si c’est du côté que vous voulez, ce qui revient à dire que le signe 'c' vous indique quel moyen de tester.

Certes, c’est un peu une façon brutale de le faire, mais cela peut être étendu pour fonctionner avec n’importe quel polygone convexe ... ou supprimer un point et cela fonctionne aussi pour les triangles.

Ma première observation à propos de ce problème est que le rectangle (aligné avec les axes) est un simple cas dégénéré. Si les deux coins de ce rectangle sont: (x1, y1) et (x2, y2), alors vous testez simplement, étant donné un point (x3, y3), ce min (x1, x2) & Lt; x3 < max (x1, x2) et min (y1, y2) < y3 < max (y1, y3).

Cela pourrait également être une optimisation utile. Si nous trouvons un rectangle de délimitation aligné sur l’axe de notre parallélogramme, nous pouvons commencer par un test rapide de tout point par rapport à cela.

Si nos parallèles ont une pente non nulle, nous calculons les intersections des axes de nos lignes de démarcation et l'intersection des lignes qui passeraient par le point en question sur ces pentes. Si les deux intersections de nos points (définies par les deux pentes) se situent entre les intersections de nos lignes de démarcation, nous y sommes. Si l'un de ces points se situe en dehors de ces limites, nous ne le sommes pas.

Je n'ai pas le temps de coder un exemple, mais le calcul de ces pentes et intersections est une algèbre de première année.

[Addenda]

Je vois maintenant que le premier message (concernant le rayon à partir du point à tester et s'étendant le long d'une pente arbitraire) fait référence à la solution générale à ce problème pour tout polygone planaire fermé ... ou, en fait, pour toute courbe plane fermée. Il peut également être étendu à trois dimensions pour les surfaces fermées.

Cependant, une mise en garde s’applique aux parallélogrammes ni aux rhomboïdes. Dans le cas d'un polygone concave (ou d'une autre courbe) si le rayon touche un sommet (angle), il est possible que le test renvoie un nombre pair de & "Ligne &"; passages à niveau. En d'autres termes, toute partie de la & Quot; courbe & Quot; qui est simultanément inclus dans plusieurs " côtés " du polygone pourrait renvoyer un faux positif.

Deux solutions seraient: tester explicitement les intersections aux limites des segments (angles / sommets) ou traiter chaque segment comme limité à une extrémité par (point + epsilon) (afin que nos calculs ne trouvent aucun point en commun entre deux côtés).

Mon idée de trouver un rectangle de délimitation reste un test rapide utile et s’applique généralement à tous les polygones. Nous trouvons les min () et max () x pour trouver les côtés de délimitation gauche et droit et les min () et et max () y pour trouver les limites inférieure et supérieure. Cela peut aussi être étendu en trois dimensions ... et un ami me dit que les bibliothèques graphiques standard l'utilisent beaucoup pour la détection de collision dans la plupart des jeux de réalité virtuelle et des MMORPG, etc. sur les polygones qui y sont contenus.

Si le parallélogramme est convexe (et étant donné la définition du parallélogramme, il doit être xD), alors tout algorithme permettant de vérifier si elle est dans ses limites devrait améliorer l'efficacité du déroulement de la boucle, car vous savez qu'il n'y a que 4 sommets. , par exemple.

Voici un algorithme simple qui teste le point situé du même côté de tous les segments, en fonction de la règle de la main droite du produit vectoriel (vous pouvez également l'optimiser en remplaçant la division pour normaliser le vecteur par un simple test de signe ):

Comment vérifier si un point se trouve à l’intérieur d’un polygone convexe en coordonnées entières 2D?

Une autre option, si vous voulez faire beaucoup de comparaisons avec le même parallélogramme, est de le normaliser en un carré, d’obtenir la matrice qui effectue la transformation et, chaque fois que vous obtenez un point à tester, multipliez-le par la matrice. puis vérifiez si le point transformé est à l'intérieur du carré normalisé (ce qui devrait être beaucoup plus facile).

Obtenir le contour de votre polygone
Vérifiez si le point se trouve dans le compte

dist1 = cv2.pointPolygonTest(contours[0], (50, 70), True)

dist renvoie l'un des trois éléments suivants:

Valeur positive si le point est à l'intérieur du contour
Valeur négative si le point est en dehors du contour
Zéro si le point est sur le contour

Comment vérifier si un point est placé à l'intérieur contour?

La coordonnée y est la plus simple. Commencez par là. Si la coordonnée y du point se situe entre le haut et le bas de la forme, passez à la coordonnée x. Calculez la coordonnée x des côtés gauche et droit de la forme à la coordonnée y du point et vérifiez si la coordonnée x du point se trouve entre eux.

Modifier:

Étant donné les quatre coordonnées des coins supérieur gauche, supérieur droit, inférieur droit et inférieur gauche:

if (y >= y1 && y <= y3) {
   var k = (x4 - x1) / (y4 - y1);
   var m = x1 - k * y1;
   if (x >= k * y + m) {
     k = (x3 - x2) / (y3 - y2);
     m = x2 - k * y2;
     if (x <= k * y + m) {
       // inside
     }
   }
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow