Clasa a 8-a lecția 7 - 4 nov 2015

From Algopedia
Revision as of 09:21, 18 January 2016 by Dan (talk | contribs) (→‎Înfășurătoarea convexă a unei mulțimi de puncte)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Triunghiul

Reprezentarea în memoria calculatorului

Vom stoca un triunghi prin cele trei puncte care îl determină:

struct Triunghi {
  Punct A;
  Punct B;
  Punct C;
};

Calculul ariei (cu formula lui Heron)

Formula lui Heron pentru calculul ariei unui triunghi cu vârfurile A, B și C este:

a = BC
b = AC
c = AB
p = (a + b + c) / 2
Aria = sqrt((p - a) * (p - b) * (p - c) * p)

Putem calcula aria folosind formula lui Heron astfel:

double ariaHeron(Triunghi t) {
  double a = distanta(t.B, t.C);
  double b = distanta(t.A, t.C);
  double c = distanta(t.A, t.B);
  double p = (a + b + c) / 2;
  return sqrt((p - a) * (p - b) * (p - c) * p);
}

Calculul ariei (cu determinant)

Formula de calcul a ariei unui triunghi cu vârfurile A, B și C cu ajutorul unui determinant este:

    | A.x A.y 1 |
D = | B.x B.y 1 |
    | C.x C.y 1 |
Aria = |D| / 2

Putem calcula aria cu ajutorul determinantului astfel:

double determinant(Triunghi t) {
  return t.A.x * t.B.y
      + t.B.x * t.C.y
      + t.C.x * t.A.y
      - t.C.x * t.B.y
      - t.A.x * t.C.y
      - t.B.x * t.A.y;
}

double ariaDeterminant(Triunghi t) {
  return fabs(determinant(t)) / 2;
}

Calculul ariei (cu înălțimea)

Formula pentru calculul ariei unui triunghi cu vârfurile A, B și C cu ajutorul înălțimii este:

Aria = AB * dist(C, AB) / 2

Putem calcula aria cu ajutorul înățimii astfel:

double ariaInaltime(Triunghi t) {
  return distanta(t.A, t.B) * distanta(obtineFormaCanonica(obtineDreapta(t.A, t.B)), t.C) / 2;
}

Sensul punctelor unui triunghi

Cele trei puncte ale unui triunghi pot fi date în sens trigonometric sau în sensul acelor de ceasornic.

Putem determina sensul în care sunt date în două feluri:

  • cu semnul determinantului;
  • cu semnul semiplanului mărginit de dreapta formată de primele două puncte și care îl conține pe al treilea.

Putem afla sensul punctelor unui triunghi astefel:

int sensTriunghi(Triunghi t) {
  if (determinant(t) < 0) {
    return -1;
  } else {
    return 1;
  }
}

Poligonul

Reprezentarea în memoria calculatorului

Vom stoca un poligon prin lista punctelor care îl determină.

Calculul ariei unui poligon convex

Un poligon convex cu N vârfuri poate fi partiționat în N-2 triunghiuri astfel:

(1,2,3), (1,3,4), (1,4,5), ..., (1,i,i+1), ..., (1, N-1, N)

Folosindu-ne de această triangulare (sau de o alta) putem calcula aria poligonului adunând ariile triunghiurilor din triangulare.

Putem implementa aria unui poligon convex astfel:

double ariaPoligonConvex(Punct* primul, Punct* dupaUltimul) {
  double aria = 0;
  Punct p1 = *primul;
  Punct *pi;
  for (pi = primul + 1; pi + 1 != dupaUltimul; pi++) {
    aria += ariaDeterminant({p1, *pi, *(pi + 1)});
  }
  return aria;
}

Calculul ariei unui poligon oarecare

Pentru calculul ariei unui poligon concav ne vom folosi de aceeași triangulare dar vom observa că suma ariilor triunghiurilor va fi mai mare decât aria poligonului, deoarece va conține suprafețe exterioare poligonului.

Totuși, uitându-ne cu atenție, vom vedea că dacă vom ține cont de sensul triunghiurilor și vom aduna ariile triunghiurilor care au același sens cu sensul poligonului și vom scădea ariile triunghiurilor care au sens contrar cu sensul poligonuli vom obține exact aria poligonului.

Mai mult, această abordare funcționează și pentru poligoanele convexe.

Putem implementa aria unui poligon oarecare astfel:

double ariaPoligon(Punct* primul, Punct* dupaUltimul) {
  double aria = 0;
  Punct p1 = *primul;
  Punct *pi;
  for (pi = primul + 1; pi + 1 != dupaUltimul; pi++) {
    aria += determinant({p1, *pi, *(pi + 1)});
  }
  return fabs(aria) / 2;
}

Înfășurătoarea convexă a unei mulțimi de puncte

Dându-se o mulțime de puncte în plan, să se determine un poligon convex de arie minimă care conține toate punctele din mulțime în interior, pe laturi sau în vârfuri.

Se observă că, în plus, acest poligon convex are și perimetrul minim.

Devine evident că, pentru a minimiza aria, unele dintre punctele din mulțimea inițială vor ajunge să definească vârfurile poligonului-înfășurătoare.

Algoritmul de calcul al înfășurătorii convexe este următorul:

1. În vectorul P, se sortează toate punctele Pi crescător, după coorodonata X.
2. Fie o stivă S, inițial vidă.
3. Se adaugă în stivă primele două puncte din vectorul P.
4. Pentru fiecare punct Pi (3 <= i <= N):
5.   Se adaugă în stivă punctul Pi
6.   Cât timp în stivă se află cel puțin 3 puncte iar sensul triunghiului determinat de acestea este unul anume
7.     Se scoate penutimul punct din stivă
8. În stivă avem jumătate din punctele de pe înfășurătoare (cele de deasupra sau de dedesupt în funcție de sensul ales)
9. Se inversează vectorul P
10.Se repetă pașii 2-7 pentru a determina și a doua jumătate a punctelor de pe înfășurătoare.

Putem implementa înfășurătoarea convexă a unei mulțimi de puncte astfel:

struct MultimePuncte {
  int n;
  Punct* puncte;
};

int compararePuncte(const void* arg1, const void* arg2) {
  if (((Punct*)arg1)->x == ((Punct*)arg2)->x &&
      ((Punct*)arg1)->y == ((Punct*)arg2)->y) {
    return 0;
  } else if (((Punct*)arg1)->x < ((Punct*)arg2)->x ||
      (((Punct*)arg1)->x == ((Punct*)arg2)->x &&
      ((Punct*)arg1)->y < ((Punct*)arg2)->y)) {
    return -1;
  } else {
    return 1;
  }
}

MultimePuncte deal(MultimePuncte in) {
  int i;
  int dimStiva = 0;
  Punct* stiva = (Punct*)malloc(sizeof(Punct) * in.n);
  stiva[dimStiva++] = in.puncte[0];
  stiva[dimStiva++] = in.puncte[1];
  for (i = 2; i < in.n; i++) {
    stiva[dimStiva++] = in.puncte[i];
    while (dimStiva >= 3 &&
        sensTriunghi(Triunghi{stiva[dimStiva - 3],
        stiva[dimStiva - 2], stiva[dimStiva - 1]}) <= 0) {
      dimStiva--;
      stiva[dimStiva - 1] = stiva[dimStiva];
    }
  }
  return MultimePuncte{dimStiva, stiva};
}

MultimePuncte inverseaza(MultimePuncte in) {
  int i;
  for (i = 0; i < in.n - i - 1; i++) {
    Punct tmp = in.puncte[i];
    in.puncte[i] = in.puncte[in.n - i - 1];
    in.puncte[in.n - i - 1] = tmp;
  }
  return in;
}

MultimePuncte infasuratoareConvexa(MultimePuncte in) {
  if (in.n >= 3) {
    int i;
    Punct* outPuncte = (Punct*)malloc(sizeof(Punct) * in.n);
    for (i = 0; i < in.n; i++) {
      outPuncte[i] = in.puncte[i];
    }
    MultimePuncte out = MultimePuncte{in.n, outPuncte};
    qsort(outPuncte, in.n, sizeof(Punct), compararePuncte);
    MultimePuncte jos = deal(out);
    out = inverseaza(out);
    MultimePuncte sus = deal(out);
    out.n = 0;
    for (i = 0; i < jos.n - 1; out.n++, i++) {
      out.puncte[out.n] = jos.puncte[i];
    }
    for (i = 0; i < sus.n - 1; out.n++, i++) {
      out.puncte[out.n] = sus.puncte[i];
    }
    free(jos.puncte);
    free(sus.puncte);
    return out;
  } else {
    return in;
  }
}

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);
    }
  }
  return 0;
}

Temă

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