불규칙한 모양의 다각형의 "시각적"중심을 찾는 가장 빠른 방법은 무엇입니까?
문제
나는 불규칙한 형태의 다각형의 시각적 중심 인 포인트를 찾아야합니다. Visual Center에 의해, 나는 다각형의 넓은 영역의 중심에있는 것처럼 보이는 지점을 의미합니다. 응용 프로그램은 다각형 안에 레이블을 넣는 것입니다.
내부 버퍼링을 사용하는 솔루션은 다음과 같습니다.
이것이 사용될 경우 버퍼를 찾는 효과적이고 빠른 방법은 무엇입니까? 다른 방법이 사용되는 경우, 이것이 바로 그런가?
정말 힘든 다각형의 좋은 예는 거대한 두꺼운 U (Arial Black 또는 충격 또는 일부 글꼴로 작성)입니다.
해결책
다각형을 이진 이미지로 변환 할 수 있다면 이미지 처리 분야에 존재하는 기초를 사용할 수 있습니다. 블록의 빠른 골격 알고리즘은 이진 이미지를 나타냅니다.
그러나 이산화 오류와 추가 작업으로 인해 일반적인 경우에는 실제로 합리적이지 않습니다.
그러나 아마도 유용하다고 생각할 수도 있습니다.
편집 : 아마도 다각형에 포함 된 가장 큰 원의 중심 인 포인트를 찾고 싶을 것입니다. 그것은 항상 관찰 된 센터에있는 것은 아니지만 대부분의 시간은 아마도 예상 결과를 제공 할 것이며, 약간 병리학적인 경우에만 완전히 꺼져 있습니다.
다른 팁
나는 Mapbox에서 이것에 대한 아주 좋은 해결책을 찾았습니다. 폴리 라벨. 전체 소스는 그들의 소스에서 사용할 수 있습니다 github 도.
본질적으로 T Austin이 말한대로 다각형의 시각적 중심을 찾으려고 노력합니다.
특정 세부 사항은 이것이 실용적인 해결책 일 수 있음을 시사합니다.
불행히도 [이상적인 솔루션]을 계산하는 것은 복잡하고 느립니다. 문제에 대한 게시 된 솔루션은 제한된 Delaunay 삼각 측량 또는 직선 골격을 전처리 단계로 계산해야합니다. 둘 다 느리고 오류가 발생하기 쉽습니다.
유스 케이스의 경우 정확한 솔루션이 필요하지 않습니다. 우리는 더 빠른 속도를 얻기 위해 약간의 정밀도를 기꺼이 거래 할 의향이 있습니다. 우리가지도에 레이블을 배치 할 때, 수학적으로 완벽한 것보다 밀리 초로 계산하는 것이 더 중요합니다.
그러나 사용에 대한 빠른 메모. 소스 코드는 상자 밖에서 JavaScript에 적합하지만 "정상적인"다각형과 함께 이것을 사용하려면 여기의 함수가 취할 때 빈 배열로 래핑해야합니다. GeojsonPolygons 정상적인 다각형이 아니라 즉
var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);
다각형의 각 모서리의 중심 위치 (x, y)를 계산합니다. 각 모서리의 끝 위치 간의 차이를 찾아서이를 수행 할 수 있습니다. 각 차원에서 각 센터의 평균을 취하십시오. 이것은 다각형의 중심이 될 것입니다.
중심 방법은 이미 여러 번 제안되었습니다. 나는 이것이 프로세스 (그리고 다각형이있는 다른 많은 유용한 트릭)를 매우 직관적으로 설명하는 훌륭한 자료라고 생각합니다.
http://paulbourke.net/geometry/polygonmesh/centroid.pdf
또한 간단한 UI 레이블을 배치하려면 다각형의 경계 상자 (다각형에서 모든 정점의 가장 낮고 가장 높은 X 및 Y 좌표로 정의 된 사각형)의 경계 상자를 계산하고 중심을 가져 오는 것으로 충분할 수 있습니다.
{
x = min_x + (max_x - min_x)/2,
y = min_y + (max_y - min_y)/2
}
이것은 중심을 계산하는 것보다 약간 빠르며, 이는 실시간 또는 임베디드 애플리케이션에 중요 할 수 있습니다.
또한 다각형이 정적 인 경우 (형식이 변경되지 않음) BB 센터 / 질량 계산의 중심 (예 : 다각형의 첫 번째 정점과 관련하여)의 결과를 데이터 구조에 저장하여 최적화 할 수 있습니다. 다각형.
나는 이것이 가장 빠르다고 말하지는 않지만 다각형 내부에 포인트를 줄 것입니다. 계산 직선 골격. 당신이 찾고있는 요점은이 골격에 있습니다. 예를 들어 경계 상자의 중앙까지 정상 거리가 가장 짧은 것을 선택할 수 있습니다.
다각형 (내부에 맞는 가장 큰 원)의 "Incircle"을 찾은 다음 그 중앙에 라벨을 중심으로하는 것은 어떻습니까? 시작할 수있는 몇 가지 링크가 있습니다.
http://www.mathopenref.com/polygonincircle.html
https://nrich.maths.org/discus/messages/145082/144373.html?1219439473
이것은 모든 다각형에서 완벽하게 작동하지 않을 것입니다. C처럼 보이는 다각형은 다소 예측할 수없는 지점에 레이블이 있습니다. 그러나 장점은 레이블이 항상 다각형의 견고한 부분과 겹칠 것입니다.
당신이 연결 한 논문의 요점 (매우 흥미로운 문제, btw)을 이해한다면,이 "내부 버퍼링"기술은 가장자리에서 산에 의해 용해되는 설탕 조각에서 문제의 모양을 모델링하는 것과 다소 유사합니다. . (예 : 버퍼 거리가 증가함에 따라 원래 모양이 줄어든다) 마지막 비트는 레이블을 배치하기에 이상적인 장소입니다.
안타깝게도 알고리즘에서 이것을 달성하는 방법은 분명하지 않습니다 ....
다각형을 다시 정점에 부러 뜨린 다음 가장 큰 볼록한 선체를 찾기 위해 함수를 적용한 다음 그 볼록한 선체에서 중심을 찾으면 "명백한"센터와 밀접하게 일치한다고 생각합니다.
정점이 주어진 가장 큰 볼록한 선체 찾기 : 간단한 다각형 단락을보십시오.
중심을 찾기 위해 볼록한 선체의 정점을 평균화하십시오.
순진한 센터 (경계 상자의)에 레이블을 놓은 다음 로컬 다각형 가장자리와 라벨의 BB의 교차점을 기반으로 움직일 수 있습니까? 교차 가장자리의 정상을 따라 움직이고 여러 모서리가 교차하면 정상을 합산하여 움직임을 요약합니까?
여기서 추측; 이런 종류의 문제에서 나는 성능이 그다지 걱정하지 않는 한, 반복적으로 해결하려고 노력할 것입니다.
지금 당장 정교화하거나 테스트 할 시간은 많지 않지만 기회를 얻을 때 더 많은 노력을 기울일 것입니다.
중심을 주요 방법으로 사용하십시오. 중심이 다각형 내에 있는지 확인하십시오. 그렇지 않다면 선을 그립니다 ~을 통해 가장 가까운 지점과 다각형의 반대편. 다각형 안에있는 해당 라인의 중간 점에 라벨을 놓으십시오.
중심에 가장 가까운 지점은 상당히 넓은 지역으로 묶일 가능성이 높기 때문에 이것이 Kyralessa의 소문과 유사한 결과를 줄 수 있다고 생각합니다. 물론, 구멍이있는 다각형이 있다면 이것은 구멍이 뚫릴 수 있습니다. 이 경우, 불일치는 아마도 훨씬 더 공정 할 것입니다. 반면에, 그것은 일반적인 경우에 대한 (빠른?) 중심 방법으로 기본적으로 기본적으로.
이 문제는 균일 한 밀도를 가정하면 "질량 중심"을 찾는 것과 유사 할 것입니다.
편집 : 다각형에 "구멍"이 있으면이 방법이 작동하지 않습니다.
토목 공학에 사용되는 질량 중심 (또는 중심) 방법을 사용할 수 있습니다. 여기 Wikipedia의 유용한 링크가 있습니다.