높이 맵 생성 알고리즘?
https://stackoverflow.com/questions/557496
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
인터넷을 둘러보고 있었는데이 특정 문제에 대한 완벽한 알고리즘을 찾을 수 없었습니다.
우리 고객은이 이미지에서 보여줄 수있는 각 지점과 함께 포인트와 가중치 데이터가 있습니다.
가중치 http://chakrit.net/files/stackoverflow/so_heightmap_points.png
그 중에는 "높이 맵"또는 이러한 지점과 그 가중치 값으로부터 일종의 지형 데이터를 생성 할 수있는 GIS 프로그램이 있지만 시간이 지남에 따라 변할 것이므로 우리는 이 높이 맵을 자동 생성하기위한 고유 한 도구를 만듭니다.
지금까지 나는 거리에서 가장 가까운 데이터 포인트까지 각 픽셀의 무게를 계산하려고 노력했습니다. Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2) 데이터 포인트의 색상에 무게와 거리 계수를 적용하여 해당 특정 픽셀의 결과 그라디언트 색상을 생성합니다.
heightmap 결과 http://chakrit.net/files/stackoverflow/so_heightmap_result.png
데이터 포인트의 특정 구성에는 여전히 문제가 있으며 알고리즘은 데이터 포인트가 많을 때 다각형 이미지를 생성합니다. 이상적인 결과는 타원과 비슷하고 다각형처럼 보일 것입니다.
다음은 Gradient Ascent에 대한 Wikipedia Article의 이미지 중 하나가 원하는 결과를 보여줍니다.
산 http://chakrit.net/files/stackoverflow/so_gradient_descent.png
그라디언트 상승 알고리즘은 내 관심이 아닙니다. 내가 관심있는 것; 가중치가있는 데이터 포인트가 제공되는 데이터 포인트가 제공되는 첫 번째 그림에서 원래 기능을 계산하는 알고리즘입니다.
나는 토폴로지 수학에서 수업을 들지 않았지만 미적분학을 할 수 있습니다. 나는 무언가를 놓치고 있다고 생각하고 그 Google 검색 상자에 무엇을 입력 해야하는지 오히려 길을 잃었습니다.
포인터가 필요합니다.
감사!
해결책
당신이 찾고있는 것은 표면 보간입니다.
이를 위해 일부 제품이 존재합니다 (여기에 있습니다 하나)
결과 기능/스플라인/기타 수학적 구조는 높이 맵을 공급하기 위해 필요한 해상도로 조사 할 수 있습니다.
보간 기능
Sqrt((x1 - x2) ^ 2 + (y1 - y2) ^ 2)
비슷하다 역 거리 가중 임의의 필터를 적용하고 다른 많은 데이터 포인트를 폐기하는 것을 제외한 방법.
이러한 기술의 대부분은 합리적인 수의 샘플과 값을 뒷받침하는 '지형과 같은'행동에 의존합니다.
무게를 높이 샘플로 사용하고 두 번째 링크에서 간단한 셰퍼드의 방법을 시도하는 것이 좋습니다 (시작할 픽셀을 필터링하지 마십시오). 이 비율의 샘플의 색상은 포인트를 색칠합니다. 예제 이미지와 같이 높이를 표시하거나 검은 색으로 윤곽선을 추가하려면 강도 (간단한 RGB 공간에서 그레이 스케일을 대략 말하면)를 사용하십시오.
다른 팁
이 문제는 표면에서 보이는 것만 큼 쉽지 않습니다. 당신의 문제는 두 영역의 경계의 양쪽이 같은 높이를 가져야한다는 것입니다. 즉, 주어진 픽셀의 높이는 가장 가까운 이웃 이상에 의해 결정됩니다.
내가 올바르게 이해하면 최소한 두 개의 알고리즘 (및 세 번째 전문 용어)이 필요합니다.
이것을 올바르게하려면 비행기를 Voronoi Tesselation.
당신은 아마도 사용하고 싶을 것입니다 KD-Tree 가장 가까운 이웃을 찾는 데 도움이됩니다. O (n^2)를 복용하는 대신 O (N Log (N))로 가져옵니다 (추가 된 이점은 Voronoi 지역 생성 단계가 높이 계산 단계에서 작동하기에 충분히 빠르다는 것입니다).
이제 가장 가까운 이웃 I에 각 지점을 인덱싱하는 2 차원 맵이 있으므로 맵의 모든 x, y 지점을 가로 질러 걸어 가야합니다.
주어진 지점 X, Y에 대해 먼저 가장 가까운 이웃 I를 잡고 목록에 붙인 다음 Voronoi 다이어그램에서 모든 연속 영역을 수집하십시오. 쉬운 방법은 사용하는 것입니다 홍수 채우기 이 지역의 모든 지점을 찾으려면 국경을 둘러보고 다른 정체성을 모으십시오.
가장 가까운 이웃 의이 목록을 사용하면 이제 올바르게 보간 할 수 있습니다! (보간 체계에 대한 다른 답변을 참조하십시오).
불규칙한 데이터의 2 차원 보간에 대한 알고리즘에 대한 정보를 요청했습니다. 이는 매우 복잡한 영역입니다. 당신은 당신이 arcgis를 가지고 있다고 말하기 때문에, i 강력하게 조언합니다 당신은 보간합니다 자동으로 내장을 사용하여 Arcgis에서 특징 자동 계산의 경우. 나는 그것이 될 것이라고 확신한다 훨씬 쉽습니다 자신의 보간 알고리즘을 작성하는 것보다. 나는 Arcgis의 자동화를했는데, 그것은 매우 간단합니다.
자신만의 보간 코드를 작성하는 경우 (가장 먼저 말하지 말라고 조언합니다. 첫 번째는 각각 고유 한 플러스와 마이너스가있는 여러 가지가 있으므로 적절한 알고리즘을 선택하는 것입니다. 다음은 우수한 보간 도구에 대한 도움으로 구겨진 조언입니다. 서퍼 (BTW는 매우 쉽게 자동화 할 수 있습니다). 더 많은 알고리즘이 있습니다. 이것들은 내가 시도한 것입니다.
- Kriging 보다 유연한 방법 중 하나이며 거의 모든 유형의 데이터 세트를 그리드에 넣는 데 유용합니다. 대부분의 데이터 세트를 사용하면 기본 선형 바리오 그램으로 Kriging이 매우 효과적입니다. 일반적 으로이 방법을 가장 자주 추천합니다. Kriging은 대부분의 데이터 세트에 적합한 맵을 생성하기 때문에 기본 그리드딩 방법입니다. 더 큰 데이터 세트의 경우 Kriging이 느리게 진행될 수 있습니다. Kriging은 데이터의 Z 범위를 넘어 그리드 값을 외삽 할 수 있습니다.
- 역 거리 가중치 빠르지 만 데이터 포인트 주위에 동심 윤곽의 "황소 눈"패턴을 생성하는 경향이 있습니다. 전력까지의 역 거리는 데이터 범위를 넘어 Z 값을 외삽하지 않습니다. 간단한 역 거리 가중 알고리즘은 구현하기 쉽지만 느려집니다.
- 선형 보간을 통한 삼각 측량 빠릅니다. 작은 데이터 세트를 사용하면 선형 보간을 통한 삼각 측량은 데이터 포인트 사이에 뚜렷한 삼각형면을 생성합니다. 선형 보간을 통한 삼각 측량은 데이터 범위를 넘어 Z 값을 외삽하지 않습니다.
- 셰퍼드의 방법 전원까지의 역 거리와 유사하지만 특히 스무딩 팩터가 사용될 때 "황소 눈"패턴을 생성하는 경향이 없습니다. 셰퍼드의 방법 데이터의 Z 범위를 넘어 값을 추정 할 수 있습니다.
알고리즘을 구현하려면 : 인터넷 검색을 시도하거나 다른 답변 중 일부의 링크를 따라갈 수 있습니다. 보간을 포함한 오픈 소스 GIS 패키지가 있으므로 C ++를 통해 포위를 좋아하는 경우 알고리즘을 추출 할 수 있습니다. 또는 이 책 David Watson은 까다 롭고 샘플 코드는 Spaghetti Basic입니다. 그러나, 내가 듣는 것에서, 그것은 가장 좋은 일입니다. Stack Overflow의 다른 사람이 더 잘 알고 있다면, 믿을 수 없으므로 나를 수정하십시오.
가중치가있는 데이터 포인트가 제공되는 데이터 포인트가 제공되는 첫 번째 그림에서 원래 기능을 계산하는 알고리즘입니다.
있을 수있다. 단일 포인트로 시작하면 항상 원으로 끝나지 만 데이터 포인트를 가중치하고이를 고려하면 이미지에서와 같이 원을 타원으로 낭비 할 수 있습니다.
다각형으로 끝나는 이유는 계산에서 개별 기능을 사용하고 있기 때문입니다. 먼저 가장 가까운 색상을 찾은 다음 색상을 결정합니다.
대신 삼각형에 그 지점을 둘러싸는 세 가지 데이터 포인트의 거리와 무게를 기반으로 한 점에 대한 색상을 할당하는 그라디언트 알고리즘을 살펴 봐야합니다.
그라디언트 알고리즘
그것은 당신이 표시하려는 내용에 달려 있습니다. 단순한 알고리즘은 다음과 같습니다.
각 픽셀에 대해 :
- 이 픽셀을 둘러싼 가장 작은 삼각형을 형성하는 세 가지 점을 찾으십시오.
이 지점을 각 데이터 포인트까지의 무게와 거리에 영향을받는 색상 (HSV 색상 시스템)으로 설정하십시오.
pixel.color = datapoint[1].weight * distance(pixel, datapoint[1]) * datapoint[1].color + datapoint[2].weight * distance(pixel, datapoint[2]) * datapoint[2].color + datapoint[3].weight * distance(pixel, datapoint[3]) * datapoint[3].color
여기 +를 사용하고 있지만 응용 프로그램에 적합한 '평균'알고리즘을 결정해야합니다.
-아담
표면 보간은 어렵고 수학적 문제 인 것 같습니다. 더 저렴한 또 다른 방법은 다음과 같습니다.
For each pixel:
For each point:
pixel.addWeight(weight(point, pixel))
def addWeight(w):
totalweight += w
numberofweights += 1
weight = totalweight / numberofweights
예제 중량 기능 :
def weight(point, pixel):
return point.weight * 1/(1 + sqrt((point.x - pixel.x)^2 + (point.y - pixel.y)^2))
그것은 무차별적인 힘 접근 방식이지만 간단합니다.
나는 얼마 전에 Winamp AVS에서 이와 같은 것을 구현했습니다. 각 데이터 포인트에서 역 제곱 거리를 계산하는 "Metaballs"유형 접근법을 사용하여 각 데이터 포인트에서 SQRT를 피하기 위해 (예 : 1.0까지), 2D 그리드의 각 지점에 대한 해당 거리의 합계를 취합니다. 이것은 매끄럽게 다양한 색상/높이 맵을 제공합니다.
코드를보고 싶다면 내에서 "글로 니"사전 설정 J10 AVS 팩.
편집 : 바로 그것을 보면서 나는 그것을 더 예쁘게 보이게하기 위해 다른 재즈를 추가했습니다. 가장 중요한 부분은 다음과 같습니다.
d1=s/(sqr(px1-rx)+sqr(py1-ry));
d2=s/(sqr(px2-rx)+sqr(py2-ry));
d3=s/(sqr(px3-rx)+sqr(py3-ry));
d4=s/(sqr(px4-rx)+sqr(py4-ry));
d5=s/(sqr(px5-rx)+sqr(py5-ry));
d6=s/(sqr(px6-rx)+sqr(py6-ry));
d=d1+d2+d3+d4+d5+d6;
6 포인트의 합계를 차지합니다. 빨간색, 녹색 및 파란색 출력 값에 대한 다른 모든 것은 더 예쁘게 보이게하는 것입니다. 6 포인트는 그리 많지 않지만 새로운 일 때 (~ 20fps) 400MHz 기계에서 320x200 그리드에서 실시간으로 실행하려고했습니다. :)
빨간색 =, 녹색 = 및 파란색 = ... 라인을 빨간색 = d로 교체하십시오. 등 ... 내가 의미하는 바를보기 위해. 모든 예쁘게 사라지고 데이터 포인트 주위에 매끄럽게 다양한 멍청한 멍청한 회색의 이미지가 남아 있습니다.
또 다른 편집 : "S"라고 말하는 것을 잊어 버렸습니다. 모든 포인트의 공유 중량은 각 점을 변경하여 각 점에 가중치를 개인화합니다. 예를 들어 D1 = 2/(...) 및 D2 = 1/(.. .)는 D1에 D2보다 D1을 두 배나 높게 제공합니다. D1 = 2/max (..., 1.0)와 같은 내용으로 바닥의 표현식을 캡처하여 포인트의 상단을 부드럽게하여 중간에 무한대에서 정점에 도달하지 않도록 할 수도 있습니다. :)
답의 혼란에 대해 죄송합니다 ... 코드 예제를 게시하는 것이 충분할 것이라고 생각했지만 검사시 코드는 혼란스럽고 읽기가 어렵습니다. :(
나는 이것이 꽤 오래된 질문이라는 것을 알고 있지만, 비슷한 문제를 해결하려고 노력하면서 그것을 우연히 발견했습니다.
오픈 소스 프로젝트가 있습니다 서리 이는 이러한 유형의 기능을 정확히 구현합니다.
당신은 그거 뭔가를 찾고 있습니다 블렌더 전화 ""대사" (링크가있는 Wikipedia 기사, 예시). 이런 식으로 생각하십시오 :
당신의 물체는 땅에서 튀어 나오는 원뿔입니다. 그것들은 모두 포물선이며 무게는 그들이 얼마나 멀리 떨어져 있는지 알려줍니다. 대안으로, 그것들을 모두 같은 높이로 만들고 그에 따라 포물선의 "평평"을 조정하므로, 무게가 큰 무게로 인해 무게가 낮 으면 무게가 날카 로워지면 날카 로워집니다. 어쩌면 어느 정도까지도.
나는 당신이 이것을 구현하고 그것이 어떻게 보이는지 보는 것이 좋습니다.
다음으로, 결과에 따라 천이나 고무 시트를 걸어야합니다. 천은 일정량으로 뻗어 있으며 일반적으로 중력으로 인해 매달려 있습니다. 원뿔은 그것을 유지합니다.
원뿔의 중심에 가까이있는 한 Z 좌표는 원뿔 표면의 위치 일뿐입니다. 원뿔 중심을 떠날 때 중력이 내려 가기 시작하고 다른 원뿔의 영향이 자랍니다.
