Tags: výpočetní geometrie

Funkce na výpočet plochy polygonu najdete téměř v jakékoliv knihovně pracující s geometrií [osmium, clip]. Na základní škole jste se učili, že obsah trojúhelníku je polovina výšky násobeno základnou. S tímto jednoduchým výrazem se dá udělat opravdu spousta práce a hodí se znát i různé metody výpočtu.

Plocha trojúhelníku

-- 2D

Výpočet z bodů

Potřebujeme alespoň 3 body, tedy a[x0, y0], b[x1, y1], c[x2, y2].

The area is positive if a,b,c are oriented ccw, negative if cw, and zero if the points are collinear.

C kód by vypadal následovně: double AreaTriangle(Point a, Point b, Point c) { return 0.5*(b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]); }

Vypočet z vektoru a diskriminantu

Potřebujeme 2 vektory.

Lineární algebra

/* The text has this: return a[0] * b[1] - a[1] * b[0] + a[1] * c[0] - a[0] * c[1] + b[0] * c[1] - c[0] * b[1]; */

Plocha polygonu

Známe výraz pro vypočet plochy trojúhelníku, následně je snadné nalést obsah polygonu když jej triangularizujeme. Tím se myslí rozdělit mnohoúhelník na trojúhelníky, existuje věta, která říká toto: {{ obsah z sqlite theorem(3) + theorem (4) - triangulace }} Triangularizaci věnujeme celou kapitolu [zde].

A(T) = A(p,a,b) + A(p,b,c) + ...

Nejde vám do hlavy, jak je možné

Konvexní čtyřúhelník

Nekonvexní čtyřúhelník

Function returns the area of the supplied polygon. Depending on orientation, this value may be positive or negative. If Orientation is true, then the area will be positive and conversely, if Orientation is false, then the area will be negative.

C kód by vypadal následovně: It's assumed that the path is closed and does not self-intersect. double Area2(Point a, Point b, Point c) { return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]); } double AreaPoly(const Path p) { // Vertex is linked list double sum = 0; Path a; a = p->next; /* Moving. */ do { sum += Area2(p->v, a->v, a->next->v ); a = a->next; } while ( a->next != p); return 0.5*sum; }

C++ kód by vypadal následovně: double AreaPoly(const std::vector<Vertex> p) { if (p.size() < 3) return 0; double sum = agregate(function() { }, p); return 0.5*sum; }

Area of a Polygon on a Sphere

Kartézský systém souřadnic není jediný. Only a few changes are needed to extend the planar algorithm for use on a sphere.

Orientace

Jednodušší problém nechávám na konec.

bool Orientation(const Path &poly) { return Area(poly) >= 0; }

Sources [1] Some Algorithms for Polygons on a Sphere