3D(또는 n-D) 중심을 계산하는 가장 좋은 방법은 무엇입니까?
https://stackoverflow.com/questions/77936
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
직장에서 프로젝트의 일부로 3D 공간에 있는 점 집합의 중심을 계산해야 합니다.지금은 간단하지만 순진해 보이는 방식으로 다음과 같이 각 점 집합의 평균을 구합니다.
centroid = average(x), average(y), average(z)
어디 x, y 그리고 z 부동 소수점 숫자의 배열입니다.좀 더 정확한 중심을 얻을 수 있는 방법이 있었던 것으로 기억하는데, 그렇게 하기 위한 간단한 알고리즘을 찾지 못했습니다.누구 아이디어나 제안이 있나요?저는 이를 위해 Python을 사용하고 있지만 다른 언어의 예제를 적용할 수도 있습니다.
해결책
여기에서 일반적으로 언급되는 것과는 달리, 포인트 클라우드의 중심을 정의(및 계산)하는 방법에는 여러 가지가 있습니다.첫 번째이자 가장 일반적인 해결책은 이미 귀하가 제안한 것입니다. ~ 아니다 이것에 문제가 있다고 주장합니다.
centroid = average(x), average(y), average(z)
여기서 "문제"는 포인트 분포에 따라 중심점이 "왜곡"된다는 것입니다.예를 들어, 모든 점이 입방체 상자나 다른 기하학적 모양 내에 있지만 대부분이 위쪽 절반에 배치되어 있다고 가정하면 중심점도 해당 방향으로 이동합니다.
대안으로 이를 방지하기 위해 각 차원에서 수학적 중간(극값의 평균)을 사용할 수 있습니다.
middle = middle(x), middle(y), middle(z)
점 수에 크게 신경 쓰지 않고 전역 경계 상자에 더 관심이 있을 때 이 기능을 사용할 수 있습니다. 왜냐하면 이것이 전부이기 때문입니다. 즉 점 주위 경계 상자의 중심입니다.
마지막으로 median (가운데에 있는 요소) 각 차원에서:
median = median(x), median(y), median(z)
이제 이것은 다음과 반대되는 역할을 할 것입니다. middle 실제로 포인트 클라우드의 이상값을 무시하고 중심점을 찾는 데 도움이 됩니다. 기반으로 귀하의 포인트 분배.
"좋은" 중심점을 찾는 더욱 강력한 방법은 각 차원의 상위 및 하위 10%를 무시하고 다음을 계산하는 것입니다. average 또는 median.보시다시피 다양한 방법으로 중심점을 정의할 수 있습니다.아래에서는 이러한 제안을 염두에 두고 2개의 2D 포인트 클라우드의 예를 보여드리겠습니다.
진한 파란색 점은 평균(평균) 중심입니다.중앙값은 녹색으로 표시됩니다.그리고 가운데는 빨간색으로 표시됩니다.두 번째 이미지에서는 제가 이전에 말했던 내용을 정확히 볼 수 있습니다.녹색 점은 포인트 클라우드의 가장 밀도가 높은 부분에 "더 가깝고", 빨간색 점은 포인트 클라우드의 가장 극단적인 경계를 고려하여 더 멀리 떨어져 있습니다.
다른 팁
아니요, 이는 점 모음의 중심에 대한 유일한 공식입니다.위키피디아를 참조하세요: http://en.wikipedia.org/wiki/Centroid
"보다 정확한 중심을 얻는 방법"을 막연하게 언급하셨습니다.어쩌면 이상값의 영향을 받지 않는 중심에 대해 이야기하고 있을 수도 있습니다.예를 들어, 평균 미국의 가계 소득은 아마도 매우 높을 것입니다. 매우 부자들은 평균을 왜곡한다.그들은 "이상치"입니다.그렇기 때문에 통계학자들은 다음과 같은 방법을 사용합니다. 중앙값 대신에.중앙값을 구하는 한 가지 방법은 값을 정렬한 다음 목록의 중간쯤에 있는 값을 선택하는 것입니다.
아마도 이와 유사한 것을 찾고 있을 수도 있지만 2D 또는 3D 포인트를 위한 것입니다.문제는 2D 이상에서는 정렬할 수 없다는 것입니다.자연스러운 순서는 없습니다.그럼에도 불구하고 이상값을 제거하는 방법이 있습니다.
한 가지 방법은 다음을 찾는 것입니다. 볼록한 선체 포인트의.볼록 껍질에는 점 집합의 "외부"에 모든 점이 있습니다.이렇게 하고 선체에 있는 점을 버리면 이상값이 사라지고 남은 점은 보다 "대표적인" 중심을 제공하게 됩니다.이 과정을 여러 번 반복해도 결과는 마치 양파 껍질을 벗기는 것과 비슷합니다.실제로는 "볼록 껍질 벗겨짐"이라고 합니다.
정확도 증가 합산(Kahan 합산)을 사용할 수 있습니다. 그게 당신이 염두에 둔 것이었나요?
잠재적으로 더 효율적:이것을 여러 번 계산하는 경우 두 개의 고정 변수를 유지하여 속도를 상당히 높일 수 있습니다.
N # number of points
sums = dict(x=0,y=0,z=0) # sums of the locations for each point
그런 다음 포인트가 생성되거나 소멸될 때마다 N과 합계를 변경합니다.이는 점이 생성, 이동 또는 파괴될 때마다 더 많은 작업을 수행하면서 계산을 위해 O(N)에서 O(1)로 변경됩니다.
"더 정확한 중심" 저는 중심이 계산된 방식으로 정의되므로 "더 정확한 중심"이 있을 수 없다고 생각합니다.
네, 맞는 공식입니다.
점이 많으면 문제의 대칭성을 활용할 수 있습니다(원통형, 구형, 거울 등).그렇지 않으면 통계를 빌려 임의의 포인트 수를 평균할 수 있으며 약간의 오류가 발생할 수 있습니다.
맞아요.계산하는 것은 중심 또는 평균 벡터입니다.
