Recherche de présence de boucles (interconnexions) dans une ligne

Question

J'ai un ensemble de coordonnées 2D. Cela peut être positif, négatif et aussi en fractions. Donc, les points sont similaires,

50.2345,-23.452 
1.345,-14.206 

ainsi de suite. Maintenant, ma question est de savoir si je trace ces coordonnées sur un graphique, comment déterminer si la ligne se croiserait pour former une boucle ou si elle resterait comme une ligne en zigzag (sans s'intersecter).

Answer 1

Ceci peut être calculé avec une boucle FOR imbriquée.

Supposons que j'ai 5 points: [0,0], [1,1], [2,1], [2,0], [0,1]

Cela nous donne 4 Arêtes, le dernier chevauchera le premier. bord ([0,0], [1,1]) se croisent avec bord ([2,0], [0,1]).

Effectuez une itération sur chaque arête (segment de ligne) et testez l'intersection avec tous les autres segments de ligne.

pseudocode:

for(edge1 in edges) 
{ 
    for(edge2 in edges) 
    { 
     if (testIntersect(edge1,edge2)) return true; 
    } 
} 
return false;