niedziela, 15 września 2013

Liczenie pola powierzchni wielokąta nieforemnego

Ostatnio musiałem napisać funkcję, która liczy pole powierzchni dowolnego wielokąta nieforemnego na podstawie współrzędnych wierzchołków. Straciłem trochę czasu na znalezienie prostego i uniwersalnego algorytmu, więc podzielę się moim znaleziskiem.

Jest to metoda analityczna obliczania pola powierzchni ze współrzędnych wzorami Gaussa.
Metoda analityczna bazuje na punktach o znanych współrzędnych. Do wyznaczenia pola powierzchni wzorami Gaussa musimy znać współrzędne wierzchołków wielokąta.

Pole P wieloboku obliczamy ze wzoru (wystarczy jeden - oba dają ten sam wynik) Gaussa:
 P = \frac{1}{2}\left| \sum\limits_{i=1}^n {X_i(Y_{i+1}-Y_{i-1}})\right| = \frac{1}{2}\left| \sum\limits_{i=1}^n {Y_i(X_{i-1}-X_{i+1}})\right|

gdzie: 
P - to wyliczane pole powierzchni
n -to liczba wierzchołków wielokąta
i = to współrzędne i-tego wierzchołka (wierzchołki numerowane są kolejno od 1 do n, poczynając od dowolnego z nich).

zakłada się przy tym, że:
X_0=X_n, Y_0=Y_n\;
X_{n+1}=X_1, Y_{n+1}=Y_1\;

Wartość bezwzględna we wzorze jest konieczna, gdyż przy zmianie kierunku numeracji wierzchołków wielokąta, zmienia się znak sum po prawej stronie. Ponadto sumy te mają zawsze przeciwne znaki.

I na koniec przykład implementacji w języku C:

#include <stdio.h>

typedef struct {
    int x;
    int y;
} point_t;

double liczPow(point_t *punkty, size_t N){
    size_t i;
    double pow;
    for (i=0;i<N;i++){
        if (i==0) {
            pow += punkty[i].x*(punkty[N-1].y-punkty[i+1].y);
        } else if (i==(N-1)){
            pow += punkty[i].x*(punkty[i-1].y-punkty[0].y);
        } else {
            pow += punkty[i].x*(punkty[i-1].y-punkty[i+1].y);
        }
    }

    if (pow < 0){
        pow = -pow;
    }

    pow /= 2;
    return pow;
}

int main(void) {
    point_t punkty[] = {
        {2,1},
        {5,2},
        {7,5},
        {4,7}
    };

    int N = sizeof(punkty)/sizeof(point_t);

    double powierzchnia = liczPow(punkty,N);

    printf("Powierzchnia: %f\n",powierzchnia);

    return 0;

}

Unikanie błędów programując w C - #2 Makra vs funkcje inline

Nie używaj makr parametryzowanych (makrodefinicji) jeśli można napisać funkcję inline, która wykona to samo zadanie.

//Nie rób tak:
#define MAX(A,B) ((A) > (B) ? (A) : (B))
// jeśli możesz zrobić tak:
inline int max(int a, int b)

Powód: Przy używaniu dyrektywy preprocesora #define jest dużo związanych z nią zagrożeń a w szczególności gdy są to makra parametryzowalne. Ważne jest odpowiednie (najczęściej w dużej ilości) użycie nawiasów (tak jak w przykładzie powyżej), ale nie wyeliminuje przypadkowego użycia inkrementacji jak np. MAX(i++,j++), która zwiększy zmienne o 2 zamiast o 1 jak to na pierwszy rzut oka wygląda.
Inne ryzyko nadużycia makr to porównanie liczb ze znakiem i bez (wspominałem o tym w poprzednim odcinku) lub jakiekolwiek porównania z liczbami zmiennoprzecinkowymi.