De quelle manière est la plus rapide de décider si un point est à l'intérieur d'un parallélogramme / rhomboide?
9 Réponses :
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. Si cela traverse un nombre pair de fois, il est en dehors de la forme.
Donc, dans votre programme, vous créez simplement une ligne invisible et voyez combien de fois cela traverse. 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 qu'en un, vous pouvez accélérer les choses en utilisant un Partition spatiale binaire pour stocker les emplacements des objets. De cette façon, vous n'avez pas besoin de comparer votre point avec chaque objet, juste ceux qui lui sont proches.
Cette solution est précise pour tous les polygones fermés.
Cette solution est précise pour toute forme fermée, avec la mise en garde obligatoire que le rayon que vous choisissez mai frappe la limite de la forme tangentielle, auquel cas ce serait une erreur de compter comme une simple intersection. C'est une très belle solution pour une personne qui regarde un labyrinthe de Squiggles, mais pour un programme informatique, calculer ces intersections n'est pas toujours la voie la plus simple.
Anton: Cela semble vraiment improbable. Avec un polygone (comme dans la question), cela ne se produirait que si le point et le segment de ligne étaient sur la même ligne. Dans ce cas, il n'y aurait pas une solution, mais infiniment beaucoup. Cette situation devrait être évidente et vous pouvez l'ignorer. Pour les courbes tangentes, vous pouvez simplement calculer la tangente au point d'intersection et voir si elle est égale à la ligne. Si oui, jetez-le. Mais il semble tellement improbable qu'il soit prudent de l'ignorer.
@Chad Okere: Bien sûr, il est vraiment improbable, mais il est important de considérer des cas dégénèrent lorsque vous faites un algorithme de faire quelque chose (en supposant que vous souhaitiez que l'algorithme fonctionne toujours; pas seulement généralement Work). Une autre manière que cela pourrait arriver (à part la façon dont vous avez décrit) est si le point est en dehors du polygone et que le rayon passe à travers un coin du polygone. Quant aux tangentes à courbes, vous ne voulez pas simplement jeter des intersections lorsque la ligne tangente est d'accord avec le rayon car le rayon peut passer à travers un point d'inflexion , auquel cas vous devriez compter une intersection .
La coordonnée Y est la plus simple, alors commencez avec cela. Si la coordonnée Y du point est 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 est entre elles.
EDIT: P>
Compte tenu des quatre coordonnées Parmi les angles en haut à gauche, en haut à droite, à droite et inférieur gauche: p>
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
}
}
}
Voir ma réponse à Cette question , qui est très similaire. Là-bas, je donne ce que je pense est un test assez facile dans le cas où le parallélogramme a un de ses coins à EDIT: Étant donné que le propriétaire de la question est familier avec les vecteurs, je vais essentiellement réécrire ma réponse dans cette langue. Supposons que le parallélogramme soit renversé par des vecteurs (0,0) car il rend l'explication plus facile à regarder, mais ce n'est pas très difficile de le modifier pour travailler en général.
PQ et pr , où p , q et r < / code> sont des coins. Le symbole * désignera le produit DOT. Choisissez un point q tel que pq est perpendiculaire à pq (c.-à-d. pq * pq = 0 ) et PR * PQ> 0 (par exemple, vous pouvez obtenir q en rotation q autour de p de 90 degrés). Choisissez également un point r tel que pr * pr = 0 et pq * pr> 0 . Ensuite, un point A est à l'intérieur si et seulement si (0
Ma première observation sur ce problème est que le rectangle (aligné avec les axes) est un cas dégénéré simple. Si deux coins de ce rectangle sont les suivants: (x1, y1) et (x2, y2), alors vous testez simplement un point (x3, y3), que min (x1, x2) Cela pourrait également être une optimisation utile. Si nous trouvons un rectangle de bornage aligné à l'axe de notre parallélogramme, nous pouvons commencer par un test rapide de tout point donné contre cela.
Si nos parallèles ont une pente non nulle, nous calculons les intersections de l'axe de nos lignes de sélection et l'intersection des lignes qui transmettraient le point en question sur ces pentes. Si les intersections de notre point (définies par les deux pistes) se situent entre nos intersections de nos lignes de liaison, nous sommes là. Si l'une de ces gammes est hors de ces gammes, nous ne sommes pas.
Je n'ai pas le temps de coder un exemple, mais calculant ces pentes et intersections sont l'algèbre de la première année.
[addenda]
Je vois maintenant que le premier message (concernant les rayons du point à tester et s'étendant le long de toute pente arbitraire) est une 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.
Il y a cependant une mise en garde qui s'appliquerait aux parallélogrammes ni aux rhomboïdes. Dans le cas d'un polygone concave (ou d'autres courbes) si le rayon frappe tout APEX (coin), il est possible que le test renvoie un nombre pair de traversées de "ligne". En d'autres termes, toute partie de la "courbe" incluse simultanément dans plusieurs "côtés" du polygone pourrait renvoyer un faux positif.
Deux solutions de ce serait: test explicitement des intersections aux limites de segment de ligne (coin / apexes) ou traiter chaque segment de ligne telle que borné à 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 liaison est toujours un test rapide utile et s'étend généralement à tous les polygones. Nous trouvons le min () et max () x () x pour trouver les côtés de bornisation gauche et droit et les min () et et max () Y pour trouver les limites inférieure et supérieure. Cela peut également être étendu à trois dimensions ... et un ami me dit que les bibliothèques graphiques standard utilisent cette largement pour la détection de collision dans la plupart des réalités virtuelles et des MMORPGS, etc. lorsque les collisions trouvées dans des zones de sélectionnementrices sont alors plus fines. sur les polygones qui y sont contenus.
L'équation standard d'une ligne est donnée sous la forme d'AX + BX + C = 0 .. Mais de manière intéressante, si vous prenez cette expression AX + BX + C et évaluez les points X, Y donné le A, B, C pour votre Ligne particulière, vous constaterez que l'expression cloisons l'avion en deux moitiés, une moitié où l'expression est supérieure à zéro, l'autre moitié où elle est moins.
Maintenant, si vous prenez les quatre points de votre parallélogramme et calculez les coefficients A A, B, C pour chaque ligne qui constitue un côté du parallélogramme, vous pouvez évaluer chaque expression pour le x, y en question et trouver de quel côté de chaque ligne est allumé. Les à l'intérieur du parallélogramme seront logiques et particuliers. IE, une fois que vous avez le A, B, C's pour chacune des quatre lignes, vous pouvez faire un test quelque chose comme .. Le seul tour restant étant que vous devez déterminer la "polarité" de chaque test de signalisation, c'est-à-dire plus ou moins que zéro. Le moyen facile 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 de 'C' vous dit de quelle manière de tester. Certes C'est une sorte de force de force brute de le faire, mais elle peut être étendue au travail pour tout polygone convexe. Ou, enlever un point et cela fonctionne pour les triangles, aussi.
Salut encore et merci pour toutes vos réponses. Entre-temps, j'ai moi-même proposé quelque chose que je pense être plutôt rapide:
Imaginez que nous avons un parallélogramme qui est renversé par PQ et PR, où PQ et PR sont des vecteurs (P, Q et R sont des coins). De plus, nous avons le point que nous voulons vérifier appelé A. p>
Nous savons que le vecteur PA peut être divisé en deux vecteurs parallèlement à PQ et PR: p>
var d:Number = det(PQ, PR);
if (0 <= -det(PA, PQ)/d <= 1 && 0 <= det(PA, PR)/d <= 1)
{
//inside
}
else
{
//outside
}
Désolé, c'est incorrect. Le problème est que la projection de pa sur pq peut être négative même si a est à l'intérieur du parallélogramme. Par exemple, si PQ et PR sont à un angle obtus, et A est un point intérieur très proche de r , alors la projection de pa sur pq est négatif.
Merci Anton, j'ai fait de la mathématique à jeûner et je ne l'ai pas donné une seconde pensée. Maintenant, je l'ai corrigé et ma réponse devrait être correcte: D
@sigvardsen: Je pense qu'il y a toujours un problème. Vos formules pour n et m ne sont pas corrects. Autant que je sache, il n'y a pas de dépendance sur pa.y . Si pr = (0,1) , pq = (1,0) et pa = (. 5.1000) , alors votre L'algorithme dirait que A est à l'intérieur.
Parfait. La façon dont vous avez écrit la solution admet également une très jolie interprétation. Det (PR, PQ) = + - Zone (PR, PQ) est la zone du parallélogramme remplacée par PR et pq (négatif si PR et pq est dans le "mauvais" ordre). Donc, votre formule indique que pour A dans le parallélogramme, la zone du parallélogramme remplacée par PR et pa doit être entre 0 et zone (PR, PQ) et la zone du parallélogramme remplacée par pa et pq doit être entre 0 et zone (PR, PQ) . C'est très intuitif si vous dessinez la photo. Bon travail. +1
@sigvardsen Je comprends presque complètement cela et comment ça marche, sauf une chose. Pourquoi Det (PA, PQ) / DET (PQ, PR) a-t-il été annulé pour n? Dans mes propres tests, je semble le faire fonctionner, mais seulement quand je ne le nie pas. Qu'est-ce que je rate?
Ce papier décrit une méthode pour déterminer où une rayon et intersect quadrilatère. Il peut être simplifié en outre si le quadrilatère est un parallélogramme.
Si vous avez un parallélogramme avec des côtés adjacents décrits par des vecteurs ab em> et ac em>. Tout point dans le plan du parallélogramme peut être décrit par le vecteur suivant p> n'importe quelle rayon peut être décrit comme une origine o em> et de direction D EM> P> O + t * D = A + a * AB + b * AC
Si le parallélogramme est convexe (et étant donné la définition du parallélogramme, il doit être XD), puis tout algorithme à tester s'il est dans ses limites, vous pouvez améliorer l'efficacité déroulant la boucle, car vous savez qu'il n'y a que 4 sommets , par exemple.
Voici un algorithme simple qui teste le point étant du même côté de tous les segments, sur la base de la règle de la main droite du produit vectoriel (vous pouvez l'optimiser également en remplaçant la division pour normaliser le vecteur avec un test de signalisation simple. ):
Comment tester si un point est à l'intérieur d'un polygone convexe dans des coordonnées entier 2D?
Une autre option, si vous allez faire beaucoup de comparaisons contre le même parallélogramme consiste à le normaliser à un carré, obtenez la matrice qui fait la transformation et chaque fois que vous avez un point à tester, multipliez-la par la matrice puis vérifiez si le point transformé est à l'intérieur du carré normalisé (ce qui devrait être beaucoup plus facile).
dist renvoie l'un des trois suivants:
Comment vérifier si le point est placé à l'intérieur Contour? dist1 = cv2.pointpolygontest (contours [0], (50, 70), true)