Difference between revisions of "Clasa a 8-a lecția 6 - 28 oct 2015"

From Algopedia
Jump to navigationJump to search
 
Line 269: Line 269:
 
b' = a
 
b' = a
  
 
+
a' = -b
 +
a  = b'
 +
------ (*)
 +
a * a' = -b * b'
 
</pre>
 
</pre>
  

Latest revision as of 10:01, 11 January 2016

Punctul

Reprezentare în memoria calculatorului

Vom stoca coordonatele carteziene ale punctului (ordonata - x și abscisa - y).

struct Punct {
  double x;
  double y;
};

Distanța dintre două puncte

Vom folosi teorema lui Pitagora și vom obține formula:

double distanta(Punct p1, Punct p2) {
  return sqrt((p1.x - p2.x) * (p1.x - p2.x) +
      (p1.y - p2.y) * (p1.y - p2.y));
}

Dreapta

O dreaptă este unic determinată de două puncte distincte. Pe baza coordonatelor celor două puncte putem determina ecuația dreptei.

Ecuația dreptei

Ecuația dreptei este o egalitate în care apar două necunoscute (x și y) cu proprietatea că mulțimea soluțiilor perechilor de numere (x, y) coincide cu coordonatele tuturor punctelor de pe dreaptă.

Ecuația dreptei determinată de două puncte

Se dau două puncte p1 și p2 de coorodonate (x1, y1) și (x2, y2). Fie (x, y) un punct de pe dreapta determinată în mod unic de punctele p1 și p2. Atunci, folosind asemănarea triunghiurilor (ca în desenul [1]) obținem ecuația:

(x - x1) / (x2 - x1) = (y - y1) / (y2 - y1)

(x - x1) * (y2 - y1) = (y - y1) * (x2 - x1)

x * y2 - x * y1 - x1 * y2 + x1 * y1 = y * x2 - y * x1 - y1 * x2 + y1 * x1

x * y2 - x * y1 - x1 * y2 + x1 * y1 - y * x2 + y * x1 + y1 * x2 - y1 * x1 = 0

x * (y2 - y1) + y * (x1 - x2) + y1 * x2 - x1 * y2 = 0

Introducând substituțiile:

a = y2 - y1
b = x1 - x2
c = y1 * x2 - x1 * y2

ajungem la forma generală a ecuației dreptei:

a*x + b*y + c = 0

Reprezentarea în memoria calculatorului

Vom stoca o dreaptă prin valorile coeficienților a, b și c ale ecuației sale:

struct Dreapta {
  double a;
  double b;
  double c;
};

Pe care le vom calcula astfel:

Dreapta obtineDreapta(Punct p1, Punct p2) {
  Dreapta d;
  d.a = p2.y - p1.y;
  d.b = p1.x - p2.x;
  d.c = p1.y * p2.x - p1.x * p2.y;
  return d;
}

Interpretarea ecuației dreptei

Pentru a testa dacă un punct p aparține unei drepte d, înlocuim x și y din ecuația dreptei cu coordonatele punctului p.

bool egale(double a, double b) {
  if (a > 0)
    return (1 - 1e-8) * b <= a && a <= (1 + 1e-8) * b;
  else
    return (1 - 1e-8) * b >= a && a >= (1 + 1e-8) * b;
}

bool punctApartineDreptei(Dreapta d, Punct p) {
  return egale(d.a * p.x + d.b * p.y + d.c, 0);
}

Semiplanele determinate de o dreaptă

Orice dreaptă d (cu ceficienții a, b și c) împarte planul în două semiplane. Vom distinge între ele numindu-le semiplanul pozitiv și semiplanul negativ.

Putem determina dacă un punct p (de coordonate x și y) se află în semiplanul pozitiv sau în semiplanul negativ calculând semnul expresiei:

a*x + b*y + c

astfel:

int semiplan(Dreapta d, Punct p) {
  if (egale(d.a * p.x + d.b * p.y + d.c, 0)) {
    return 0;
  } else if (d.a * p.x + d.b * p.y + d.c < 0) {
    return -1;
  } else {
    return 1;
  }
}

Panta unei drepte

Fie două puncte p1 și p2 de coordonate x1 și y1 respectiv x2 și y2 aparținând unei drepte d. Spunem că panta m dreptei d este:

m = (y2 - y1) / (x2 - x1)

Folosind formulele de calcul ale coeficienților a și b:

a = y2 - y1
b = x1 - x2

putem deduce că:

m = -a / b

Putem calcula panta unei drepte astfel:

double panta(Dreapta d) {
  return -d.a / d.b;
}

Paralelismul a două drepte

Două drepte d1 și d2 cu coeficieții a1, b1 și c1 respectiv a2, b2 și c2 sunt paralele dacă au aceeași pantă, adică:

-a1 / b1 = -a2 / b2

a1 / b1 = a2 / b2

a1 * b2 = a2 * b1

Putem verifica dacă două drepte sunt paralele astfel:

bool suntParalele(Dreapta d1, Dreapta d2) {
  return egale(d1.a * d2.b, d2.a * d1.b);
}

Coincidența a două drepte

Două drepte coincid dacă și numai dacă conțin aceleași puncte. Două drepte conțin aceleași puncte dacă și numai dacă soluțiile ecuațiilor lor coincid. Soluțiile a două ecuații coincid dacă și numai dacă sunt echivalente. Două ecuații sunt echivalente dacă și numai dacă înmulțind una dintre ele cu un număr real r o obținem pe cealaltă.

Astfel, pentru a verifica dacă două drepte d1 și d2 cu coeficienții a1, b1, c1 respectiv a2, b2, și c2 coincid este suficient să verificăm dacă:

a1 / a2 = b1 / b2 = c1 / c2

Mai mult, dacă cele două ecuații sunt în formă canonică atunci:

a1 / a2 = b1 / b2 = c1 / c2 = 1 sau -1

iar semnul raportului dă "sensul" dreptei, care determină semnele semiplanelor.

Putem verifica dacă două drepte coincid astfel:

bool coincid(Dreapta d1, Dreapta d2) {
  return egale(d1.a * d2.b, d1.b * d2.a) &&
      egale(d1.a * d2.c, d1.c * d2.a);
}

Forma canonică a ecuației dreptei

Ecuația unei drepte d poate fi înmulțită cu orice număr real r diferit de 0 și astfel obținem o altă ecuație cu aceeași mulțime a soluțiilor. Altfel spus, înmulțind coeficienții ecuației dreptei (a, b și c) cu același număr real r obținem coeficienții unei ecuații ce desemnează aceeași dreaptă d.

De aceea, dacă pentru coeficienții a, b și c ai unei drepte d alegem r astfel:

r = 1 / sqrt(a * a + b * b)

și îi înmulțim prin r, aceștia vor respecta condiția suplimentară:

a * a + b * b = 1

Putem aduce o dreaptă la forma sa canonică astfel:

struct DreaptaCanonica : public Dreapta {};

DreaptaCanonica obtineFormaCanonica(Dreapta d) {
  double r = 1 / sqrt(d.a * d.a + d.b * d.b);
  DreaptaCanonica dPrim;
  dPrim.a = d.a * r;
  dPrim.b = d.b * r;
  dPrim.c = d.c * r;
  return dPrim;
}

Distanța de la un punct la o dreaptă

Fie d o dreaptă cu coeficienții ecuației în formă canonică a, b și c și p un punct de coordonate x și y.

Distanța de la punctul p la dreapta d este dată de formula:

|a*x + b*y + c|

Putem calcula distanța de la un punct la o dreaptă astfel:

double distanta(DreaptaCanonica d, Punct p) {
  return fabs(d.a * p.x + d.b * p.y + d.c);
}

Paralela unei drepte care trece printr-un punct

Fie d o dreaptă cu coeficienții ecuației a, b și c și p un punct de coordonate x și y.

Dreapta d' paralelă cu d care trece prin punctul p are coeficienții:

a' = a
b' = b
c' = - a*x - b*y

Putem calcula dreapta d' astfel:

Dreapta paralelaPrin(Dreapta d, Punct p) {
  d.c = -d.a * p.x - d.b * p.y;
  return d;
}

Perpendicularitatea a două drepte

Fie d1 și d2 două drepte cu coeficienții a1, b1, c1 și a2, b2 și c3. Spunem că d1 și d2 sunt perpendiculare dacă și numai dacă:

m1 * m2 = -1

-a1 / b1 * -a2 / b2 = -1

a1 / b1 * a2 / b2 = -1

a1 / b1 = -b2 / a2

a1 * a2 = -b1 * b2

Putem calcula dacă două drepte d1 și d2 sunt paralele astfel:

bool suntPerpendiculare(Dreapta d1, Dreapta d2) {
  return egale(d1.a * d2.a, -d1.b * d2.b);
}

Perpendiculara unei drepte care trece printr-un punct

Fie d o dreaptă cu coeficienții ecuației a, b și c și p un punct de coordonate x și y.

Dreapta d' perpendiculară pe d care trece prin punctul p are coeficienții:

a' = -b
b' = a
c' = -a'*x - b'*y

Deoarece perpendicularitatea este satisfăcută de primele două relații:

a' = -b
b' = a

a' = -b
a  = b'
------ (*)
a * a' = -b * b'

Iar a teria relație garantează că punctul p aparține dreptei d':

c' = -a'*x - b'*y

a'*x + b'*y + c' = 0

Putem calcula dreapta d' astfel:

Dreapta perpendicularaPrin(Dreapta d, Punct p) {
  Dreapta dPrim;
  dPrim.a = -d.b;
  dPrim.b = d.a;
  dPrim.c = -dPrim.a * p.x - dPrim.b * p.y;
  return dPrim;
}

Intersecția a două drepte

Fie d1 și d2 două drepte cu coeficienții a1, b1, c1 și a2, b2 și c3. Spunem că d1 și d2 nu se intersecteză dacă sunt paralele. Spunem că d1 și d2 se intersectează într-o infinitate de puncte dacă coincid. Spunem că d1 și d2 se intersectează într-un singur punct p de coorodonate x și y. Perechea de valori x și y reprezintă soluția sistemului liniar determinat cu două ecuații și două necunoscute:

a1*x + b1*y + c1 = 0 | * b2
a2*x + b2*y + c2 = 0 | * b1

b2*a1*x + b2*b1*y + b2*c1 = 0
b1*a2*x + b1*b2*y + b1*c2 = 0
-----------------------------(-)
(b2*a1 - b1*a2)*x + (b2*c1 - b1*c2) = 0

x = -(b2*c1 - b1*c2) / (b2*a1 - b1*a2)
x = (b1*c2 - b2*c1) / (b2*a1 - b1*a2)


Similar:
a1*x + b1*y + c1 = 0 | * a2
a2*x + b2*y + c2 = 0 | * a1

a2*a1*x + a2*b1*y + a2*c1 = 0
a1*a2*x + a1*b2*y + a1*c2 = 0
-----------------------------(-)
(a2*b1 - a1*b2)*y + (a2*c1 - a1*c2) = 0

y = -(a2*c1 - a1*c2) / (a2*b1 - a1*b2)
y = (a2*c1 - a1*c2) / (b2*a1 - b1*a2)

Putem calcula punctul p astfel:

Punct intersectia(Dreapta d1, Dreapta d2) {
  Punct p;
  p.x = (d1.b * d2.c - d2.b * d1.c) / (d2.b * d1.a - d1.b * d2.a);
  p.y = (d2.a * d1.c - d1.a * d2.c) / (d2.b * d1.a - d1.b * d2.a);
  return p;
}

Testare

Pentru a testa codul de mai sus am scris următoarea funcție main():

int main(void) {
  Punct p11 = {1, 1}, p12 = {1, 2}, p13 = {1, 3};
  Punct p21 = {2, 1}, p22 = {2, 2}, p23 = {2, 3};
  Punct p31 = {3, 1}, p32 = {3, 2}, p33 = {3, 3};
  assert(egale(distanta(p11, p22), sqrt(2)));
  Dreapta d1 = obtineDreapta(p11, p22);
  assert(punctApartineDreptei(d1, p33));
  assert(!punctApartineDreptei(d1, p23));
  assert(semiplan(d1, p23) == -semiplan(d1, p32));
  assert(semiplan(d1, p23) == -semiplan(d1, p32));
  DreaptaCanonica d1prim = obtineFormaCanonica(d1);
  assert(egale(d1prim.a * d1prim.a + d1prim.b * d1prim.b, 1));
  assert(coincid(d1, d1prim));
  Dreapta d2 = obtineDreapta(p21, p32);
  assert(suntParalele(d1, d2));
  Dreapta d3 = obtineDreapta(p11, p31);
  assert(!suntParalele(d1, d3));
  assert(egale(distanta(d1prim, p21), sqrt(2) / 2));
  Dreapta d4 = paralelaPrin(d1, p21);
  assert(punctApartineDreptei(d4, p32));
  assert(!punctApartineDreptei(d4, p33));
  Dreapta d5 = obtineDreapta(p12, p21);
  assert(suntPerpendiculare(d1, d5));
  assert(!suntPerpendiculare(d1, d2));
  Dreapta d6 = perpendicularaPrin(d1, p21);
  assert(punctApartineDreptei(d6, p12));
  assert(!punctApartineDreptei(d6, p22));
  assert(!punctApartineDreptei(d6, p13));
  Punct pi = intersectia(d1, d6);
  assert(egale(pi.x, 1.5));
  assert(egale(pi.y, 1.5));

  return 0;
}

Temă

Pentru data viitoare veți avea de rezolvat următoarele probleme: