[algorithm] 2D 다각형의 면적은 어떻게 계산합니까?
2D 공간에서 자체 교차하지 않는 일련의 점을 가정 할 때 결과 다각형의 면적을 결정하는 효율적인 방법은 무엇입니까?
참고로 이것은 숙제가 아니며 나는 코드를 찾고 있지 않습니다. 내 자신의 방법을 구현하는 데 사용할 수있는 설명을 찾고 있습니다. 점 목록에서 일련의 삼각형을 가져 오는 것에 대한 아이디어가 있지만 볼록 및 오목 다각형과 관련된 가장자리 사례가 많이 있다는 것을 알고 있습니다.
답변
다음은 표준 방법 인 AFAIK입니다. 기본적으로 각 정점 주변의 외적을 합산합니다. 삼각 측량보다 훨씬 간단합니다.
(x, y) 꼭지점 좌표의 목록으로 표시된 다각형이 주어진 Python 코드, 마지막 꼭지점에서 첫 번째 꼭짓점으로 암시 적으로 래핑됩니다.
def area(p):
return 0.5 * abs(sum(x0*y1 - x1*y0
for ((x0, y0), (x1, y1)) in segments(p)))
def segments(p):
return zip(p, p[1:] + [p[0]])
David Lehavi는 다음과 같이 설명합니다.이 알고리즘이 작동하는 이유를 언급 할 가치가 있습니다. 함수 −y 및 x에 대한 Green의 정리 를 적용한 것입니다 . 면적계가 작동 하는 방식과 정확히 일치 합니다. 더 구체적으로:
위의 공식 =
integral_over_perimeter(-y dx + x dy) =
integral_over_area((-(-dy)/dy+dx/dx) dy dx) =
2 Area
답변
외적은 고전적입니다.
수행해야 할 이러한 계산이 무궁무진 한 경우 곱셈이 절반으로 줄어드는 다음 최적화 된 버전을 사용해보십시오.
area = 0;
for( i = 0; i < N; i += 2 )
area += x[i+1]*(y[i+2]-y[i]) + y[i+1]*(x[i]-x[i+2]);
area /= 2;
명확성을 위해 배열 첨자를 사용합니다. 포인터를 사용하는 것이 더 효율적입니다. 좋은 컴파일러가 당신을 위해 그것을 할 것이지만.
다각형은 “닫힌”것으로 간주됩니다. 즉, 첫 번째 점을 아래 첨자 N이있는 점으로 복사합니다. 또한 다각형에 짝수의 점이 있다고 가정합니다. N이 짝수가 아니면 첫 번째 점의 추가 사본을 추가하십시오.
이 알고리즘은 고전적인 교차 곱 알고리즘의 두 번의 연속적인 반복을 풀고 결합하여 얻습니다.
두 알고리즘이 수치 정밀도와 관련하여 어떻게 비교되는지 잘 모르겠습니다. 내 인상은 곱셈이 뺄셈의 정밀도 손실을 복원하는 경향이 있기 때문에 위의 알고리즘이 고전적인 알고리즘보다 낫다는 것입니다. GPU와 마찬가지로 부동 소수점을 사용하도록 제한되면 상당한 차이를 만들 수 있습니다.
편집 : “삼각형 및 다각형 영역 2D 및 3D” 는 훨씬 더 효율적인 방법을 설명합니다.
// "close" polygon
x[N] = x[0];
x[N+1] = x[1];
y[N] = y[0];
y[N+1] = y[1];
// compute area
area = 0;
for( size_t i = 1; i <= N; ++i )
area += x[i]*( y[i+1] - y[i-1] );
area /= 2;
답변
이 페이지 는 공식이
다음과 같이 단순화 할 수 있습니다.
몇 가지 용어를 작성하고의 공약수에 따라 그룹화 xi하면 평등을보기가 어렵지 않습니다.
최종 합산은 n대신 곱셈 만 필요하므로 더 효율적 입니다 2n.
def area(x, y):
return abs(sum(x[i] * (y[i + 1] - y[i - 1]) for i in xrange(-1, len(x) - 1))) / 2.0
저는 여기 에서 Joe Kington으로부터이 단순화를 배웠습니다 .
NumPy가있는 경우이 버전이 더 빠릅니다 (매우 작은 어레이를 제외하고 모두) :
def area_np(x, y):
x = np.asanyarray(x)
y = np.asanyarray(y)
n = len(x)
shift_up = np.arange(-n+1, 1)
shift_down = np.arange(-1, n-1)
return (x * (y.take(shift_up) - y.take(shift_down))).sum() / 2.0
답변
다른 제약 조건이없는 점 집합이 반드시 다각형을 고유하게 정의하는 것은 아닙니다.
따라서 먼저이 지점에서 만들 다각형을 결정해야합니다. 볼록 껍질일까요? http://en.wikipedia.org/wiki/Convex_hull
그런 다음 면적을 삼각 측량하고 계산합니다. http://www.mathopenref.com/polygonirregulararea.html
답변
삼각형 영역을 확장하고 삼각형 영역을 합산하려면 볼록 다각형이 있거나 다각형과 교차하는 다른 모든 지점에 선을 생성하지 않는 지점을 선택하면 작동합니다.
일반적인 비교 차 다각형의 경우 a와 b가 서로 “다음”인 벡터 (기준점, 점 a), (기준점, 점 b)의 외적을 합산해야합니다.
순서대로 다각형을 정의하는 점 목록이 있다고 가정합니다 (순서는 점 i 및 i + 1이 다각형의 선을 형성 함).
합계 (외적 ((점 0, 점 i), (점 0, 점 i + 1)) for i = 1 to n-1.
그 외적의 크기를 취하면 표면적이 있습니다.
이것은 좋은 참조 점을 선택하는 것에 대해 걱정할 필요없이 오목한 다각형을 처리합니다. 다각형 내부에 있지 않은 삼각형을 생성하는 세 점은 다각형 내부에있는 삼각형의 반대 방향을 가리키는 외적을 가지므로 영역이 올바르게 합산됩니다.
답변
다각형의 면적을 계산하려면
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry1#polygon_area
int cross(vct a,vct b,vct c)
{
vct ab,bc;
ab=b-a;
bc=c-b;
return ab.x*bc.y-ab.y*bc.x;
}
double area(vct p[],int n)
{
int ar=0;
for(i=1;i+1<n;i++)
{
vct a=p[i]-p[0];
vct b=p[i+1]-p[0];
area+=cross(a,b);
}
return abs(area/2.0);
}
답변
또는 윤곽 적분을 수행하십시오. Stokes의 정리를 사용하면 면적 적분을 등고선 적분으로 표현할 수 있습니다. 작은 가우스 구적법과 밥은 당신의 삼촌입니다.
