Étant donné l'équation à 4 lignes d'un quadrilatère convexe, comment puis-je trouver la coordonnée du coin 4?

Question

J'ai quatre équations de ligne y = mx + b et il y a 6 points d'intersection.

On sait que ces lignes forment un quadrilatère convexe.

Comment puis-je trouver quelle intersection forme le quadrilatère (de préférence dans l'ordre)?

Answer 1

Première Concave QUAD:

Le 6ème point d'intersection doit être aussi dans 1) j'oublie simplement attirer là.

1. calculer tous les points d'intersection et de les associer à des lignes

   l1: p2,p5,p6 
   l2: p1,p4,p6 
   l3: p1,p2,p3 
   l4: p3,p4,p5 
   

   l moyens ligne et p moyens de point d'intersection

2. déterminer si le point est bord seulement ou également du milieu

   donc le point central est si vous avez un autre point de chaque côté de la ligne il appartient. En d'autres termes, si vous convertissez le point en sa position de paramètre (ou la distance par rapport à un point de départ), le point central se trouve entre les deux autres distances. Le paramètre vous obtenez directement/distance tout calcul d'intersection, mais au cas où vous ne vous pouvez utiliser ceci:

   t(p) = dot(p-A,B-A) 
   

   où A,B sont extrémités de ligne, p est interrogé point d'intersection et t(p) est sa « distance » scalaire de A .

   donc savoir quels des points sont front uniquement e et qui sont d'âge moyen m:

   l1: e2,e5,m6 
   l2: e1,e4,m6 
   l3: e1,m2,e3 
   l4: e3,m4,e5 
   

   maintenant si un point quelconque est au moins une fois du milieu, alors il est en partie du milieu, si elle est, il est bord alors seulement bord et si elle est moyenne alors seulement il est milieu:

   edge: p1,p3,p5 
   partial: p2,p4 
   middle: p6 
   

3. construction polygone

   Donc les points de contour que nous devons utiliser. Les points partiels que nous sautons (car ils se trouvent sur la ligne déjà utilisée) et enfin nous utilisons également le point du milieu. Nous savons que notre polygone sera:

   (p1,p3,p5) + (p6) 
   

   Maintenant, nous devons trouver où le point central concave p6 ira. Il y a 3 combinaisons:

   e1,m6,e3,e5 
   e1,e3,m6,e5 
   e1,e3,e5,m6 
   

   nous savons que m6 appartiennent à l1,l2 et l1,l2 a également p2,p5,p1,p4 à partir de laquelle sont des points de pointe seulement: e1,e5 de sorte que le m6 sera placé entre eux de sorte que la bonne solution est:

   e1,e3,e5,m6 
   

maintenant Convex QUAD:

si nous profitons de # 1, # 2 alors pour former un quad convexe, nous devons utiliser les points intermédiaires et intermédiaires et choisir l'un des points de bord purs. Sélectionnez celui qui n'appartient pas à la ligne avec le point central pur. Nous devons donc utiliser:

(p2,p4) + (m6) + one_from(e1,e3,e5) 

le m6 n'est pas Appartenant à l3,l4 donc nous avons besoin de trouver bord appartenant à la fois ce qui est e3 si

(p2,p4) + (m6) + (e3) 

Maintenant, nous avons juste besoin de trouver l'ordre. point central et le point de bord ne seront pas près eux-mêmes si vous avez 2 solutions:

p2,m6,p4,e3 
    p2,e3,p4,m6 

Les deux sont corrects ils sont juste inverse d'eux-mêmes (règle d'enroulement polygone Différend) afin que vous puissiez choisir celui que vous avez besoin sur la base z coordonnées de produit croisé de deux sommets voisins quelconques.

Answer 2

résoudre des systèmes d'équations linéaires pour chaque paire de lignes

y = m[i] * x + b[i] 
    y = m[j] * x + b[j] 

où m [i], b [i] sont les coefficients de i-ième ligne et obtenir (x, y) pour intersection.

S'il y a exactement 6 intersections (pas de lignes parallèles, pas de dégénérescence), alors chaque ligne a trois points d'intersection dans la rangée. Deux intersections sont "externe" et une (moyenne) est "intérieure", donc il y a trois points internes et trois externes.

Il semble que le quadrilatère convexe contienne toujours tous les trois points internes, de sorte que nous pouvons séparer les points internes et obtenir le quatrième point correspondant.

Par exemple, si les lignes sont désignées par A, B, C, D, et les intersections AB, AC, CD sont interne, puis quatrième point est intersection BD (B et D sont uniques dans la liste d'intersection)

PS Notez que le formulaire d'équation de ligne y=mx+b ne convient pas pour toutes les lignes possibles (pas pour les lignes verticales), il est donc préférable d'utiliser more general form comme A*x + B*y + C = 0 ou autre.