計算多邊形的最小圓環

Question

我曾在iOS上工作過，並有一個帶地理座標的多邊形，如（-27.589846,151.982112）（ - 27.590174,151.983045）（ - 27.590773,151.982680）（ - 27.590602,151.981908）。

我想找出它的外圓incircle：center and radius？

有沒有辦法做到這一點？

謝謝？

Answer 1

，你可以用它來確定非自相交多邊形的中心：

#include <iostream> 

struct Point2D 
{ 
    double x; 
    double y; 
}; 

Point2D compute2DPolygonCentroid(const Point2D* vertices, int vertexCount) 
{ 
    Point2D centroid = {0, 0}; 
    double signedArea = 0.0; 
    double x0 = 0.0; // Current vertex X 
    double y0 = 0.0; // Current vertex Y 
    double x1 = 0.0; // Next vertex X 
    double y1 = 0.0; // Next vertex Y 
    double a = 0.0; // Partial signed area 

    // For all vertices except last 
    int i=0; 
    for (i=0; i<vertexCount-1; ++i) 
    { 
     x0 = vertices[i].x; 
     y0 = vertices[i].y; 
     x1 = vertices[i+1].x; 
     y1 = vertices[i+1].y; 
     a = x0*y1 - x1*y0; 
     signedArea += a; 
     centroid.x += (x0 + x1)*a; 
     centroid.y += (y0 + y1)*a; 
    } 

    // Do last vertex 
    x0 = vertices[i].x; 
    y0 = vertices[i].y; 
    x1 = vertices[0].x; 
    y1 = vertices[0].y; 
    a = x0*y1 - x1*y0; 
    signedArea += a; 
    centroid.x += (x0 + x1)*a; 
    centroid.y += (y0 + y1)*a; 

    signedArea *= 0.5; 
    centroid.x /= (6.0*signedArea); 
    centroid.y /= (6.0*signedArea); 

    return centroid; 
} 

int main() 
{ 
    Point2D polygon[] = {{0.0,0.0}, {0.0,10.0}, {10.0,10.0}, {10.0,0.0}}; 
    size_t vertexCount = sizeof(polygon)/sizeof(polygon[0]); 
    Point2D centroid = compute2DPolygonCentroid(polygon, vertexCount); 
    std::cout << "Centroid is (" << centroid.x << ", " << centroid.y << ")\n"; 
} 

要獲得半徑，然後確定中心之間的距離，每個頂點，並挑選規模最大的一次！