Comment vérifier si un point est sur une ligne entre les 2 autres points

Comment pourrais-je écrire cette fonction? Des exemples apprécié

function isPointBetweenPoints(currPoint, point1, point2):Boolean {

    var currX = currPoint.x;
    var currY = currPoint.y;

    var p1X = point1.x;
    var p1y = point1.y;

    var p2X = point2.x;
    var p2y = point2.y;

    //here I'm stuck
}

Il y a quelques bonnes réponses ci-dessous, mais j'ai pensé que je ferais remarquer que vous devriez regarder dehors pour la précision en virgule flottante de questions. Quelle que soit la méthode que vous utilisez, vous aurez probablement à permettre à une petite quantité d'erreur lorsque, par exemple, de tester si deux pentes différentes sont les mêmes.
McCarthy: C'est le problème majeur avec la pente des méthodes basées sur. Les changements de pente non uniforme avec un angle le plus proche de la ligne est verticale, plus la pente augmente (même pas de mentionner le cas particulier vertical et presque à la verticale de la ligne). Il n'y a tout simplement pas de bons pente de stratégie. J'aimerais éviter de pente à base de méthodes à tous les coûts.

OriginalL'auteur nuway | 2012-08-10

algorithm geometry

38

En supposant que point1 et point2 sont différents, il faut d'abord vérifier si le point se trouve sur la ligne. Pour cela, vous avez simplement besoin d'un "multi-produits" de vecteurs point1 -> currPoint et point1 -> point2.
```
dxc = currPoint.x - point1.x;
dyc = currPoint.y - point1.y;

dxl = point2.x - point1.x;
dyl = point2.y - point1.y;

cross = dxc * dyl - dyc * dxl;
```
Votre point se trouve sur la ligne si et seulement si cross est égal à zéro.
```
if (cross != 0)
  return false;
```
Maintenant, comme vous le savez que le point ne se trouvent sur la ligne, il est temps de vérifier si elle se trouve entre les points originaux. Ceci peut être facilement fait en comparant la x coordonnées, si la ligne est "plus horizontale que verticale", ou y coordonnées autrement
```
if (abs(dxl) >= abs(dyl))
  return dxl > 0 ? 
    point1.x <= currPoint.x && currPoint.x <= point2.x :
    point2.x <= currPoint.x && currPoint.x <= point1.x;
else
  return dyl > 0 ? 
    point1.y <= currPoint.y && currPoint.y <= point2.y :
    point2.y <= currPoint.y && currPoint.y <= point1.y;
```
Noter que l'algorithme ci-dessus si entièrement partie intégrante si les données d'entrée est intégrale, c'est à dire il ne nécessite pas de calculs en virgule flottante pour une entrée entière. Attention aux éventuels débordement lors du calcul de cross.

P. S. Cet algorithme est absolument précis, ce qui signifie qu'il va rejeter les points qui se situent très près de la ligne, mais pas exactement sur la ligne. Parfois, ce n'est pas ce qui est nécessaire. Mais c'est une autre histoire.

Vous pouvez diminuer l'algorithme de précision par la mise en œuvre de seuil pour la validation de la croix-produit de Sorte que si le produit vectoriel est près de zéro, alors le point est presque sur la ligne threshold = 0.1; if (abs(cross) > threshold) return false;.
Pourrait-on simplifier cela? Puisque nous savons qu'il est SUR la ligne, pourquoi nous nous soucions si elle est plus horizontale que verticale? Il peut y avoir une seule valeur de y pour tout x sur la ligne, donc si currPoint.x est entre point1.x et point2.x, comment pourrait-il être n'importe où ailleurs que sur la ligne?
peut être qu'une seule valeur de y pour tout x sur la ligne" - pas vrai pour une ligne verticale. Si le segment est strictement verticale, puis vérifiez pour x produit pas de réponse significative. Oui, on peut toujours vérifier x gamme, sauf que pour un usage strictement segment vertical on doit vérifier y gamme à la place. Mon approche "horizontale"ou"verticale" est juste à l'équilibre de la généralisation de cette.
Merci pour ces précisions @Fourmi, vous avez raison! if dxl != 0 peut-être plus au point, et un peu plus rapide.
Gardez à l'esprit que l'algorithme fonctionne comme si la ligne est infinie. Si vous avez besoin de vérifier si le point est entre les deux points d'un segment, vous devez utiliser un autre algorithme.

OriginalL'auteur AnT
20
```
Distance(point1,currPoint)+Distance(currPoint,point2)==Distance(point1,point2)
```
Mais attention, si vous avez des valeurs à virgule flottante, les choses sont différentes pour eux...

Très agréable, avec des valeurs à virgule flottante (en JavaScript), vous pouvez faire quelque chose comme return distanceAC + distanceBC - distanceAB < THRESHOLD;
Cette méthode est plus stable que la Fourmi réponse ci-dessus avec la croix de la valeur.
Mais il a besoin de beaucoup plus de puissance de calcul (3 fois la racine carrée).
si la racine carrée est un goulot de bouteille, l'équation peut être réécrite de façon à éviter - la quadrature des deux parties, seul, ne reste qu'une racine carrée, avec plus de complication que nous pourrons nous débarrasser de ce trop.

OriginalL'auteur maxim1000
4

Vous voulez vérifier si la pente de point1 à currPoint est la même que la pente de currPoint à point2, donc:
```
m1 = (currY - p1Y) /(currX - p1X);
m2 = (p2Y - currY) /(p2X - currX);
```
Vous voulez également vérifier si currPoint est à l'intérieur de la boîte créée par les deux autres, donc:
```
return (m1 == m2) && (p1Y <= currY && currY <= p2Y) && (p1X <= currX && currX <= p2X);
```
Edit: Ce n'est pas une très bonne méthode; regardez maxim1000 de la solution pour beaucoup plus de bon sens.

Ouais, je viens de réaliser mon erreur. Je pense que je peux ajouter une autre contrainte pour résoudre ce problème.
Mais les données d'entrée n'est pas l'état qui p1X <= p2X et p1Y <= p2Y (d'ailleurs, il ne peut tout simplement pas être vrai dans tous les cas). Pourtant, votre contrôle final ne fonctionnera correctement que si ces conditions sont remplies. En plus de cela, votre algorithme s'appuie sur direct précis de la comparaison de valeurs à virgule flottante m1 et m2. Inutile de dire que ce ne sera tout simplement pas de travail due à l'imprécision des calculs en virgule flottante.
... même pas de mentionner que la pente base de la méthode ne peut pas gérer des lignes verticales. Ce sujet de division par zéro?

OriginalL'auteur Christian Mann

Ceci est indépendant de Javascript. Essayez l'algorithme suivant, avec des points p1=point 1 et p2=point2, et votre troisième point p3=currPoint:

v1 = p2 - p1
v2 = p3 - p1
v3 = p3 - p2
if (dot(v2,v1)>0 and dot(v3,v1)<0) return between
else return not between

Si vous voulez être sûr que c'est sur la segment de ligne entre p1 et p2 ainsi:

v1 = normalize(p2 - p1)
v2 = normalize(p3 - p1)
v3 = p3 - p2
if (fabs(dot(v2,v1)-1.0)<EPS and dot(v3,v1)<0) return between
else return not between

OriginalL'auteur imallett

0

Illustration graphique

Si vous voulez savoir si le point se trouve sur la ligne entre deux points ou pas, vous avez besoin de trouver les vecteurs de ces points et de calculer le produit scalaire de ces vecteurs.

Supposons que vous avez deux points A et B. Et le point P que vous souhaitez tester. D'abord à calculer les vecteurs PA, PB
- PA = A - P
- PB = B - P
Puis on calcule le produit scalaire de ces vecteurs DotProduct(PA, PB). Pour simplifier, nous allons supposer que les calculs sont fait en 2D.

test_dot_product = DotProduct(PA, PB) = PA.x * PB.x + PA.y * PB.y

Donc quand produit scalaire est calculé, nous avons besoin de vérifier si elle est de valeur inférieure ou égale à 0. Si oui, cela signifie que les vecteurs PA et PB orientés dans différentes directions et le point P est quelque part entre A et B. Autrement vecteurs orientés dans la même direction et le point P est à l'extérieur AB gamme.
```
if(test_dot_product <= 0.0f){
    Point P IS between A and B
}
else{
    Point P IS NOT between A and B
}
```
Voici un exemple de code. C'est le code de mon moteur 2D de la physique raycasting système. Quand je trouve du coup le point de le ray et le bord j'ai besoin de vérifier si c'est entre le bord du min et max de points...
```
    ....
    v2 HitPP1 = Edge->Min - HitData->HitPoint;
    v2 HitPP2 = Edge->Max - HitData->HitPoint;

    //NOTE(dima): If hit point is between edge min and max points
    if (Dot(HitPP1, HitPP2) <= 0.0f) {
        HitData->HitHappened = 1;
        AtLeastOneHitHappened = 1;
    }
    .....
```
Désolé pour mon anglais

OriginalL'auteur Gorevoy Dima

Vous devez vous connecter pour publier un commentaire.