Le contenu de cet article est très basique, principalement pour les débutants comme moi, alors demandez à tous les empereurs de l'algorithme pour jeter un coup d'œil
Citation
Il est connu que le segment de ligne 1 (a, b) et le segment de ligne 2 (C, D), où ABCD est le point final, trouvez le point d'intersection P du segment de ligne. (parallèle ou colinéaire sont considérés comme disjoints)
Algorithme 1: Trouvez le point d'intersection de la ligne droite où se trouvent les deux segments de ligne, puis déterminez si le point d'intersection se trouve sur les deux segments de ligne.
Lors de la recherche du point d'intersection d'une ligne droite, nous pouvons le trouver à travers l'équation générale d' Ax + par + C = 0 de la ligne droite (ABC dans l'équation est un coefficient, et non le point final mentionné ci-dessus.
Ensuite, sur la base de la relation positionnelle entre le point d'intersection et le point final du segment de la ligne, nous pouvons déterminer si le point d'intersection est sur le segment de la ligne.
La formule est la suivante:
<code> Segments de fonction (a, b, c, d) {/ ** 1 résolvez le système d'équations linéaires et trouvez l'intersection des segments de ligne. ** / // Si le dénominateur est 0, il est parallèle ou colinéaire, et n'inscrit pas Var Denominator = (par - Ay) * (dx - cx) - (ax - bx) * (cy - dy); if (denominator == 0) {return false; } // La coordonnée d'intersection de la ligne droite où le segment de ligne est localisé (x, y) var x = ((bx - ax) * (dx - cx) * (cy - ay) + (by - ay) * (dx - cx) * ax - (dy - cy) * (bx - ax) * cx) / dénominateur; var y = - ((par - ay) * (dy - cy) * (cx - ax) + (bx - ax) * (dy - cy) * ay - (dx - cx) * (by - ay) * cy) / dénominateur; / ** 2 Déterminez si l'intersection se trouve sur deux segments ** / if (// l'intersection est sur le segment de ligne 1 (x - ax) * (x - bx) <= 0 && (y - ay) * (y - by) <= 0 // et l'intersection est également sur le segment de ligne 2 && (x - cx) * (x - dx) <= 0 && (y - cy) * (y - dy) <= 0) <= 0) Retour à l'intersection p return {x: x, y: y}} // sinon, le disjoint return false} </code>L'algorithme a d'abord une idée claire et facile à comprendre, mais ses performances ne sont pas élevées. Parce qu'il calcule l'intersection avant qu'il ne soit incertain si l'intersection est valide (sur le segment en ligne), ce qui prend beaucoup de temps.
Si le point d'intersection est finalement invalide, le calcul précédent sera vain. De plus, l'ensemble du processus de calcul est également très compliqué.
Il y a donc un moyen de savoir s'il y a un point d'intersection efficace d'abord, puis de le calculer?
De toute évidence, la réponse est oui. Donc certains algorithmes sont trouvés.
Algorithme 2: Déterminez si les deux points d'extrémité de chaque segment de ligne sont des deux côtés de l'autre segment de ligne. Trouvez ensuite l'intersection de la ligne droite où se trouvent les deux segments de ligne, sinon ils ne se croisent pas.
La première étape consiste à déterminer si deux points sont des deux côtés d'un certain segment de ligne. La méthode de projection peut généralement être utilisée:
Trouvez le vecteur normal du segment de ligne, puis projetez le point sur la ligne normale et jugez enfin la relation entre le point et le segment de ligne en fonction de la position projetée.
Voir l'image ci-dessous
La projection sur le segment de ligne normal CD des points A et B est illustrée sur la figure. Pour le moment, nous devons également projeter le CD du segment de ligne sur notre ligne normale (sélectionnez simplement l'un des points C ou du point D).
Principalement utilisé pour référence.
Dans la figure, la projection des points A et B est projetée des deux côtés de la projection du point C, indiquant les deux côtés du segment de ligne CD du segment de ligne AB.
De même, jugez simplement si CD est à nouveau des deux côtés du segment de ligne AB.
Trouver des normales, de la projection et d'autres choses semblent très compliquées, mais en fait, c'est en effet assez compliqué pour moi. Je ne savais pas grand-chose sur les connaissances en géométrie il y a quelques mois (j'ai oublié toutes les connaissances de la géométrie lorsque j'étudiais: '()'
Heureusement, l'apprentissage et la mise en œuvre ne sont pas compliqués, et il y a des formules à suivre.
Trouvez la normale du segment de ligne AB:
var nx = by - ay, ny = ax - bx; var normalline = {x: nx, y: ny}; Remarque: Lorsque les significations géométriques de normalLine.x et normalLine.y représentent la direction de la ligne normale, et non les coordonnées.
Trouvez la position de projection du point C sur la ligne normale:
var dist = normalline.x * cx + normalline.y * cy;
Remarque: La "position de projection" ici est un scalaire, qui représente la distance à l'origine de la normale, et non les coordonnées du point de projection.
Il suffit généralement de connaître cette distance.
Après avoir calculé la projection des points A (DISTA), le point B (distb) et le point C (distc) dans la figure, nous pouvons facilement juger la position relative en fonction de leurs tailles respectives.
Lorsque DISTA == DISTB == DISTC, les deux segments sont colinéaires
Lorsque DISTA == DISTB! = DISTC, les deux segments de ligne sont parallèles
Lorsque DISTA et DISTB sont du même côté de DISTC, les deux segments de ligne ne se croisent pas.
Lorsque DISTA et DISTB sont du côté opposé de DISTC, si les deux segments de ligne se croisent doivent être jugés à nouveau si la relation entre le point C et le segment de ligne AB.
Les étapes précédentes ne mettent en œuvre que "à juger si les segments de ligne se croisent". Lorsque le résultat est vrai, nous devons trouver davantage le point d'intersection.
Parlons du processus de recherche du point d'intersection plus tard. Examinons d'abord la mise en œuvre complète de cet algorithme:
Segments de fonction (a, b, c, d) {// normal n1 var nx1 = (by - ay), ny1 = (ax - bx); // N2 VAR N2 VAR NX2 = (DY - CY), NY2 = (CX - DX); // Deux normales sont multipliées, si le résultat est 0, cela signifie que le segment de ligne AB et le CD du segment sont parallèles ou colinéaires, et n'inscrivent pas var dénominateur = nx1 * ny2 - ny1 * nx2; if (denominator == 0) {return false; } // Projection sur N2 Var N2 VAR DISTC_N2 = NX2 * CX + NY2 * CY; var DISTA_N2 = NX2 * AX + NY2 * AY-DISTC_N2; var distb_n2 = nx2 * bx + ny2 * by-ristc_n2; // La projection du point A et du point B est du même côté de la projection du point C (pour le cas sur le segment de la ligne, cet exemple est traité comme disjoint); if (DISTA_N2 * DISTB_N2> = 0) {return false; } // // juge la relation entre le point C Point D et le segment de ligne AB, le principe est le même que ci-dessus // // projection sur N1 var DISTA_N1 = NX1 * AX + NY1 * AY; var distc_n1 = nx1 * cx + ny1 * Cy-Dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dissa_n1; if (distc_n1 * distd_n1> = 0) {return false; } // Calculez les coordonnées d'intersection Var Fraction = DISTA_N2 / DÉNOMINATEUR; var dx = fraction * ny1, dy = -fraction * nx1; return {x: ax + dx, y: Ay + dy}; }La méthode utilisée pour trouver les coordonnées du point d'intersection à la fin semble un peu étrange, et il semble que ce soit discret.
En fait, il est similaire à l'algorithme de l'algorithme 1, sauf que bon nombre des termes de calcul ont été calculés à l'avance.
En d'autres termes, la partie de l'algorithme pour trouver les coordonnées du point d'intersection en deux miles est en fait en équations linéaires d'une ligne droite.
Comparons maintenant l'algorithme un et l'algorithme deux d'une manière simple et rugueuse et non scientifique:
1. Dans le meilleur cas, la complexité des deux algorithmes est la même
2. Dans le pire des cas, la quantité de calcul de l'algorithme 1 et de l'algorithme 2 est presque la même
3. Cependant, l'algorithme 2 fournit plus de "conditions précoces", donc en moyenne, l'algorithme 2 devrait être meilleur.
Après des tests réels, la situation réelle est en effet le cas.
Les deux algorithmes précédents sont essentiellement courants et peuvent faire face à la plupart des situations. Mais en fait, il y a un meilleur algorithme.
C'est ce que je viens d'apprendre récemment (je l'ai appris maintenant et je l'ai vendu maintenant, ne me dérange pas ...)
Algorithme 3: Déterminez si les deux points d'extrémité de chaque segment de ligne sont des deux côtés de l'autre segment de ligne. Si vous trouvez l'intersection de la ligne droite où se trouvent les deux segments de ligne, sinon ils ne se croisent pas.
(Huh? Pourquoi cela ressent-il la même chose que l'algorithme 2? Ne doutez pas que ce soit vraiment la même chose ...)
Le soi-disant algorithme 3 n'est en fait qu'une amélioration de l'algorithme 2. Les principales améliorations sont:
La relation positionnelle entre les points et les segments de ligne n'est pas jugée par une projection normale, mais par la zone de triangles composée de points et de segments de ligne.
Prenons d'abord la formule de la zone du triangle: il est connu que les trois points a (x, y) b (x, y) c (x, y) de la zone du triangle est:
<code> var triadea = ((ax - cx) * (par - cy) - (ay - cy) * (bx - cx)) / 2; </code>
Étant donné que la zone d'un parallélogramme (deux vecteurs est des côtés adjacents) composés de deux vecteurs en train de former == les deux vecteurs, la formule ci-dessus n'est pas difficile à comprendre.
De plus, comme les vecteurs ont des instructions, la zone a également des instructions. Habituellement, nous utilisons le sens antihoraire comme positif et dans le sens horaire comme négatif.
Les points clés de l'algorithme amélioré sont:
Si les signes positifs et négatifs de la zone du triangle formé par "le segment de ligne AB et Point C" sont différents de la zone du triangle formé par "Segment de ligne AB et Point D",
Le point C et le point D sont alors situés des deux côtés du segment de ligne AB.
Comme indiqué dans la figure ci-dessous:
Le triangle montré par la ligne pointillée de la figure a des directions d'enroulement différentes (l'ordre de définition des trois côtés), donc les symboles positifs et négatifs de la zone sont différents.
Regardons d'abord le code:
Comme nous n'avons besoin que de juger le symbole, nous n'avons pas besoin de diviser ce qui suit par 2 dans la formule de la zone du triangle précédent.
Segments de fonction (a, b, c, d) {// 2 fois la zone du triangle ABC var area_abc = (ax - cx) * (par - cy) - (ay - cy) * (bx - cx); // 2 fois la zone du triangle ABD var Area_abd = (ax - dx) * (par - dy) - (ay - dy) * (bx - dx); // Si les symboles de zone sont les mêmes, les deux points ne se croisent pas du même côté (dans le cas du point sur le segment de la ligne, cet exemple est traité comme disjoint); if (area_abc * area_abd> = 0) {return false; } // 2 fois la zone du triangle CDA var Area_cda = (cx - ax) * (dy - ay) - (cy - ay) * (dx - ax); // 2 fois la zone du triangle CDB // Remarque: Il y a une petite optimisation ici. Il n'est pas nécessaire de calculer la zone avec la formule, mais elle est dérivée en ajoutant et en soustrayant les trois zones connues. var area_cdb = area_cda + area_abc - area_abd; if (area_cda * area_cdb> = 0) {return false; } // Calculez les coordonnées d'intersection var t = Area_cda / (Area_abd- Area_abc); var dx = t * (bx - ax), dy = t * (par - ay); return {x: ax + dx, y: Ay + dy}; }Enfin, la pièce qui calcule les coordonnées d'intersection est la même que l'algorithme.
Sur la base de l'algorithme 2, l'algorithme 3 simplifie considérablement les étapes de calcul et le code est plus rationalisé. On peut dire que c'est le meilleur parmi les trois algorithmes. Il en va de même pour les résultats réels des tests.
Bien sûr, nous devons être honnêtes, en JavaScript, la complexité du temps des trois algorithmes est en fait similaire pour les calculs ordinaires (en particulier dans le moteur V8).
Dans mon cas de test, j'ai également effectué des tests d'intersection de segment de ligne à un million de niveaux anormaux pour élargir l'écart entre les trois algorithmes.
Résumer
Cependant, avec l'attitude de rechercher l'excellence et l'apprentissage, la poursuite d'un meilleur algorithme a toujours sa signification positive. Ce qui précède est plusieurs algorithmes qui utilisent JS pour atteindre les points d'intersection du segment de ligne. Le contenu n'est pas très profond. J'espère qu'il sera utile à tout le monde d'apprendre JS.