Intersecció de rectes

En matemàtiques, i més concretament en geometria euclidiana, la intersecció de dues rectes pot ser el conjunt buit, un punt, o una recta. Distingir aquests casos i trobar el punt d'intersecció té utilitat, per exemple, en l'àmbit de la computació gràfica, la planificació de moviment, i la detecció de col·lisions.

Intersecció de rectes

En geometria euclidiana tridimensional, si dues rectes no són al mateix pla, hom diu que les rectes es creuen, i no tenen cap punt d'intersecció. Si les rectes pertanyen al mateix pla, hi ha tres possibilitats: si coincideixen (és a dir, no són rectes diferents) tenen un nombre infinit de punts en comú (coincideixen en tots els seus punts); si són rectes diferents però tenen el mateix pendent, hom diu que les rectes són paral·leles i no tenen cap punt en comú; altrament tenen un sol punt sol d'intersecció.

Les característiques distintives de la geometria no euclidiana són el nombre i la localització de les possibles interseccions entre dues rectes, i el nombre de possibles rectes sense interseccions (rectes paral·leles) respecte una recta donada.

Intersecció de dues rectesModifica

Una condició necessària perquè dues rectes es tallin és que pertanyin al mateix pla; és a dir, que no siguin rectes que es creuen. Aquesta condició és equivalent a què el tetràedre amb vèrtexs a dos dels punts d'una recta i dos dels punts en l'altra sigui degenerat, en el sentit de tenir volum zero. Per a la forma algebraica d'aquesta condició, vegeu l'article Rectes que es creuen#Comprovació.

Donats dos punts sobre cada rectaModifica

Considerem primer la intersecció de dues rectes L1 i L₂ en un espai bidimensional, on la recta L1 està definida per dos punts diferents (x1, y1) i (x₂, y₂), i la recta L₂ està definida per dos punts diferents (x₃, y₃) i (x₄, y₄).[1]

La intersecció P de les rectes L1 i L₂ es pot definir utilitzant determinants.

 


 

Els determinants es poden reescriure com:

 

Cal notar que el punt d'intersecció està definit per a les rectes infinitament llargues determinades pels punts, i no pels segments de recta entre els punts, i es pot produir un punt d'intersecció més enllà de les longituds dels segments de recta. Per tal de trobar la posició de la intersecció dins respecte als segments de recta, es poden definir rectes L1 i L₂ en termes dels paràmetres de Bézier de primer grau:

 

(on t i u són nombres reals). El punt d'intersecció de les rectes es troba amb un dels valors següents de t o u:

 


 

amb:

 

El punt d'intersecció estarà a l'interior del primer segment de recta si 0 ≤ t ≤ 1, i a l'interior del segon segment de recta si 0 ≤ u ≤ 1. Aquestes desigualtats es poden demostrar sense haver de dividir per t, la qual cosa permet una determinació ràpida de l'existència de qualsevol intersecció de segment de recta abans de calcular-ne el punt exacte.[2]

Quan les dues rectes són paral·leles o coincidents, el denominador és zero:

 

Si les rectes són gairebé paral·leles, aleshores un algorisme computacional podria trobar problemes numèrics a l'hora d'implementar la solució descrita anteriorment: el reconeixement d'aquesta condició pot requerir una comprovació aproximada en una aplicació pràctica. Una aproximació alternativa seria rotar els segments de recta per tal que un d'ells sigui horitzontal, i d'aquí es pot trobar fàcilment la solució de la forma paramètrica girada de la segona recta.

Donades les equacions de les rectesModifica

Les coordenades x i y del punt d'intersecció de dues rectes (que no siguin verticals) es pot trobar de manera senzilla emprant les següents substitucions i manipulacions algebraiques.

Hom suposa primer que les dues rectes tenen equacions y = ax + c i y = bx + d, on a i b són els pendents de les rectes, i c i d són les ordenades a l'origen de les rectes. En el punt on les dues rectes s'intersecten (en cas que es tallin), les dues coordenades y són iguals, i per tant hom pot establir la següent igualtat:

ax + c = bx + d

Es pot manipular algebraicament aquesta expressió per tal de trobar el valor de x:

ax - bx = d - c

i, per tant,

 

Per trobar la coordenada y, tot el que cal és substituir el valor de x a qualsevol de les dues equacions de les rectes; per exemple, a la primera:

 

En conclusió, el punt d'intersecció és

 

Cal notar que si a = b llavors les dues rectes són paral·leles. Si, a més, cd, les rectes són diferents i no hi ha cap intersecció; altrament, les dues rectes són idèntiques.

Coordenades homogèniesModifica

Si s'utilitzen coordenades homogènies, es pot determinar de manera senzilla el punt d'intersecció de dues rectes definides implícitament. En dues dimensions, tot punt es pot definir com una projecció d'un punt en tres dimensions, donat per una terna ordenada (x, y, w). La conversió de coordenades tridimensionals a coordenades bidimensionals és (x', y') = (x/w, y/w). Es poden convertir punts bidimensionals a les seves coordenades homogènies si es defineixen com a (x, y, 1).

Suposi's que hom vol trobar la intersecció de dues rectes infinites en l'espai bidimensional, definides per a1x + b1y + c1 = 0 i ax + by + c₂ = 0. Es poden representar aquestes dues rectes en coordenades de la recta com U1 = (a1, b1, c1) i U1 = (a1, b1, c1).

Llavors la intersecció P' de les dues rectes ve simplement donat per[3]

 

Intersecció de n rectesModifica

Existència i expressió per a la interseccióModifica

En dues dimensionsModifica

En dues dimensions, és gairebé segur que més de dues rectes no s'intersecten en un sol punt. Per tal de determinar si ho fan i, en cas afirmatiu, trobar el punt d'intersecció, hom pot escriure l'equació i-sima (i = 1, ..., n) com  , i disposar aquestes equacions en forma matricial com a

 

on la i-sima fila de la matriu A de dimensió n × 2 és  , w és el vector de dimensió 2 × 1 (x, y)T, i l'i-sim element del vector columna b és bi. Si A té columnes independents, el seu rang és 2. Aleshores existeix una solució de l'equació matricial (i per tant un punt d'intersecció de les n rectes) si i només si el rang de la matriu ampliada (A | b) també és 2. El punt d'intersecció, si existeix, ve donat per

 

on Ag és la pseudoinversa de Moore-Penrose de A (que té la forma indicada perquè A té rang columna complet). Alternativament, hom pot trobar la solució mitjançant la resolució simultània de dues equacions independents qualssevol. Però si el rang de A només és 1, llavors:

  • si el rang de la matriu ampliada és 2, llavors no hi ha cap solució
  • si el rang de la matriu ampliada és 1, llavors totes les rectes són coincidents

En tres dimensionsModifica

El procediment anterior es pot estendre de manera trivial al cas tridimensional. En dimensió 3 o superior, també és cert que és gairebé segur que dues rectes no s'intersecten; si un parell de rectes no es tallen, hom diu són rectes que es creuen. Però si existeix una intersecció, hom pot trobar-ne el punt de la manera següent.

En tres dimensions, una recta es pot representar per la intersecció de dos plans, cadascun dels quals té una equació de la forma  . Així, un conjunt de n rectes es pot representar per 2n equacions, considerant el vector de coordenades tridimensionals w = (x, y, z)T:

 

on A té ara dimensió 2n × 3 i b té dimensió 2n × 1. Anàlogament al cas anterior, existeix un únic punt d'intersecció si i només si A té rang columna complet i la matriu ampliada (A | b) no, i el punt únic d'intersecció (si existeix) ve donat per

 

Punt més proper a rectes que no s'intersequenModifica

En dimensió 2 o superior, hom pot trobar un punt que sigui el més proper a dues o més rectes, en el sentit de mínims quadrats.

En dues dimensionsModifica

En el cas de dimensió 2, primer es representa la recta i com un punt pi sobre la recta, i es defineix un vector normal unitari   perpendicular a aquesta recta. És a dir, si x1 i x₂ són punts de la recta 1, llavors sigui p1 = x1, i sigui

 

que és el vector unitari al llarg de la recta, rotat 90 graus.

Cal observar que la distància des d'un punt x a la recta   ve donada per

 

i que el quadrat de la distància des d'un punt x a una recta és

 

La suma dels quadrats de les distàncies a diverses rectes és la funció de pèrdua:

 

Es pot reescriure com:

 

Per trobar-ne el mínim, cal diferenciar amb respecte a x i igualar el resultat al vector nul:

 

de tal manera que

 

i per tant

 

En tres dimensionsModifica

Encara que  no està ben definit en dimensió superior a 2, es pot generalitzar a qualsevol dimensió si s'observa que  és la matriu (simètrica) amb tots els valors propis unitaris llevat del valor propi 0 en la direcció de la recta, la qual cosa indueix una seminorma sobre la distància entre pi i un altre punt que dona la distància a la recta. En un nombre de dimensions qualsevol, si   és un vector unitar al llarg de la recta i-sima, llavors

  esdevé  

on I és la matriu identitat, i per tant[4]

 

ReferènciesModifica

  1. «Weisstein, Eric W. "Line-Line Intersection." From MathWorld». A Wolfram Web Resource.
  2. Antonio, Franklin. Kirk. Graphics Gems III. Academic Press, Inc., 1992, p. 199-202. ISBN 0-12-059756-X. 
  3. Birchfield, Stanley. «Homogeneous coordinates». robotics.stanford.edu, 23-04-1998.
  4. Traa, Johannes. «Least-Squares Intersection of Lines», 2013. Arxivat de l'original el 2018-11-23. [Consulta: 27 abril 2019].

Vegeu tambéModifica

Enllaços externsModifica