Clasa a 8-a lecția 8 - 11 nov 2015

From Algopedia
Jump to navigationJump to search

Reprezentarea unui punct în memoria calculatorului

Coordonate carteziene

Fie un punct O, numit origine și două drepte perpendiculare (Ox și Oy), orientate. Acestea formează un sistem cartezian de coordonate.

Putem calcula coordonatele unui punct P într-un sistem cartezian astfel: Ducem proiecțiile Px și Py punctului P pe dreptele Ox respectiv Oy și măsurăm distanțele de la origine la proiecții. În plus, ținând cont de orientarea dreptelor Ox și Oy, atribuim un semn celor două distanțe. Acestea formează coordonatele carteziene ale punctului P.

Putem stoca în memoria calculatorului un punct în coordonate carteziene astfel:

struct Punct {
  double x;
  double y;
};

Coordonate polare

Fie un punct O, numit origine și o dreaptă orientată Ox. Acestea formează un sistem polar de coordonate.

Putem calcula coordonatele unui punct P într-un sistem polar astfel: Calculăm distanța r de la punctul O la punctul P. Calculăm unghiul (măsurat în radiani) dintre dreapta Ox și dreapta OP, ținând cont de semiplan și admițând și unghiuri obtuze. Astfel, unghiul poate varia între -PI și PI.

Putem stoca în memoria calculatorului un punct în coordonate polare astfel:

struct PunctPolar {
  double r;
  double alpha;
};

Pentru o ilustrare grafică: [1]

Conversia de la coordonate carteziene la coordonate polare

Cunoscând coordonatele carteziene (x, y) ale unui punct P putem calcula coorodnatele sale polare (r, alpha) astfel: Pentru calcularea distanței r se poate folosi teorema lui Pitagora.

r = sqrt(x * x + y * y)

Pentru calcularea unghiului alpha vom folosi un funcție predefinită în limbajul de programare C (atan2), care calculează arctangena (inversa tangentei) pantei dreptei OP, ținând cont de cadranul în care se află punctul P.

Putem implementa transformarea din coordonate carteziene în coordonate polare astfel:

PunctPolar convertesteLaPolare(Punct c) {
  PunctPolar p;
  p.r = sqrt(c.x * c.x + c.y * c.y);
  p.alpha = atan2(c.y, c.x);
  return p;
}

Conversia de la coordonate polare la coordonate carteziene

Cunoscând coordonatele polare (r, alpha) ale unui punct P putem calcula coorodnatele sale carteziene (x, y) folosindu-ne de definițiile funcțiilor trigonometrice într-un dreptunghi de ipotenuză r. Astfel:

x = r * cos(alpha)
y = r * sin(alpha)

Putem implementa transformarea din coordonate polare în coordonate carteziene astfel:

Punct convertesteLaCarteziene(PunctPolar p) {
  Punct c;
  c.x = p.r * cos(p.alpha);
  c.y = p.r * sin(p.alpha);
  return c;
}

Unghiuri

Măsurarea unghiurilor

Unghiurile se pot măsura în grade sau în radiani. Cele două măsurători sunt direct proporționale și, prin definiție:

0 grade = 0 radiani
180 de grade = PI radiani

Astfel, putem converti gradele în radiani și radianii în grade astfel:

grade = radiani / PI * 180
radiani = grade / 180 * PI

Putem face conversii între grade și radiani astfel:

double convertesteLaGrade(double radiani) {
  return radiani / M_PI * 180;
}

double convertesteLaRadiani(double grade) {
  return grade / 180 * M_PI;
}

Unghiul format de 3 puncte

Fie 3 puncte A, O și B. Pentru a calcula unghiul u(AOB) format de acestea, ne vom baza de unghiurile alfaA și alfaB formate de dreptele OA respectiv OB cu dreapta Ox.

dif = |alpha(A) - alpha(B)|
u(AOB) = dif, dacă 0 <= dif <= PI
       = 2 * PI - dif, dacă PI < dif <= 2 * PI

Putem calcula unghiul format de 3 puncte astfel:

double unghi(Punct A, Punct O, Punct B) {
  double alphaA = atan2(A.y - O.y, A.x - O.x);
  double alphaB = atan2(B.y - O.y, B.x - O.x);
  double dif = fabs(alphaA - alphaB);
  if (dif > M_PI)
    dif = 2 * M_PI - dif;
  return dif;
}

Unghiul format de 2 drepte

Fie două drepte d1 și d2 cu coeficienții a1, b1 și c1 respectiv a2, b2 și c2. Ducem dreptele e1 și e2 paralele cu d1 respectiv d2 prin punctul de origine O. Unghiul dintre d1 și d2 este congruent cu unghiul dintre e1 și e2. Unghiul dintre e1 și e2 este congruent cu unghiul dintre perpendicularele f1 și f2 pe e1 respectiv e2 care trec prin punctul de origine O. Considerăm două puncte p1 și p2 ce aparțin perpendicularelor f1 și f2. Unghiul format de punctele p1, O și p2 este congruent cu unghiul dintre perpendicularele f1 și f2. Punctele p1 și p2 pot fi alese (ușor) de coordonate (a1, b1) și (a2, b2).

Putem calcula unghiul format de 2 drepte astfel:

double unghi(Dreapta d1, Dreapta d2) {
  double u = unghi({d1.a, d1.b}, {0, 0}, {d2.a, d2.b});
  if (u > M_PI / 2)
    u = M_PI - dif;
  return u;
}

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));

  Triunghi t1 = {p11, p23, p32};
  assert(egale(ariaHeron(t1), ariaDeterminant(t1)));
  assert(egale(ariaHeron(t1), ariaInaltime(t1)));
  Triunghi t2 = {p11, p32, p23};
  assert(sensTriunghi(t1) == -sensTriunghi(t2));
  Punct poligon1[] = {p11, p13, p33, p31};
  assert(egale(ariaPoligonConvex(poligon1, poligon1 + 4), 4));
  Punct poligon2[] = {p11, p13, p33, p31, p22};
  assert(egale(ariaPoligon(poligon2, poligon2 + 5), 3));
  Punct puncte[] = {p11, p12, p21, p22, p23, p32, p33};
  MultimePuncte multime = {7, puncte};
  multime = infasuratoareConvexa(multime);
  assert(multime.n == 6);
  for (int i = 0; i < multime.n; i++) {
    //printf("%.0lf %.0lf\n", multime.puncte[i].x, multime.puncte[i].y);
    assert(sensTriunghi({multime.puncte[i],
      multime.puncte[(i + 1) % multime.n],
      multime.puncte[(i + 2) % multime.n]}) > 0);
    Dreapta d = obtineDreapta(multime.puncte[i],
        multime.puncte[(i + 1) % multime.n]);
    for (int j = 0; j < 7; j++) {
      assert(semiplan(d, puncte[j]) <= 0);
    }
  }

  PunctPolar polar12 = convertesteLaPolare(p12);
  assert(egale(polar12.r, sqrt(5)));
  assert(egale(polar12.alpha, acos(1 / sqrt(5))));
  assert(egale(convertesteLaCarteziene(polar12).x, p12.x));
  assert(egale(convertesteLaCarteziene(polar12).y, p12.y));
  assert(egale(convertesteLaRadiani(convertesteLaGrade(1)), 1));
  assert(egale(convertesteLaGrade(convertesteLaRadiani(1)), 1));
  assert(egale(unghi(p32, p22, p23), PI / 2));
  assert(egale(unghi(obtineDreapta(p11, p22), obtineDreapta(p21, p32)), 0));

  return 0;
}

Temă

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