불규칙한 모양의 다각형의 "시각적"중심을 찾는 가장 빠른 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/1203135

문제

나는 불규칙한 형태의 다각형의 시각적 중심 인 포인트를 찾아야합니다. Visual Center에 의해, 나는 다각형의 넓은 영역의 중심에있는 것처럼 보이는 지점을 의미합니다. 응용 프로그램은 다각형 안에 레이블을 넣는 것입니다.

내부 버퍼링을 사용하는 솔루션은 다음과 같습니다.

https://web.archive.org/web/20150708063910/http://proceedings.esri.com/library/userconf/proc01/professional/papers/pap388/p388.htm

이것이 사용될 경우 버퍼를 찾는 효과적이고 빠른 방법은 무엇입니까? 다른 방법이 사용되는 경우, 이것이 바로 그런가?

정말 힘든 다각형의 좋은 예는 거대한 두꺼운 U (Arial Black 또는 충격 또는 일부 글꼴로 작성)입니다.

도움이 되었습니까?

해결책

다각형을 이진 이미지로 변환 할 수 있다면 이미지 처리 분야에 존재하는 기초를 사용할 수 있습니다. 블록의 빠른 골격 알고리즘은 이진 이미지를 나타냅니다.

그러나 이산화 오류와 추가 작업으로 인해 일반적인 경우에는 실제로 합리적이지 않습니다.

그러나 아마도 유용하다고 생각할 수도 있습니다.

편집 : 아마도 다각형에 포함 된 가장 큰 원의 중심 인 포인트를 찾고 싶을 것입니다. 그것은 항상 관찰 된 센터에있는 것은 아니지만 대부분의 시간은 아마도 예상 결과를 제공 할 것이며, 약간 병리학적인 경우에만 완전히 꺼져 있습니다.

다른 팁

나는 Mapbox에서 이것에 대한 아주 좋은 해결책을 찾았습니다. 폴리 라벨. 전체 소스는 그들의 소스에서 사용할 수 있습니다 github 도.

본질적으로 T Austin이 말한대로 다각형의 시각적 중심을 찾으려고 노력합니다.

enter image description here

특정 세부 사항은 이것이 실용적인 해결책 일 수 있음을 시사합니다.

불행히도 [이상적인 솔루션]을 계산하는 것은 복잡하고 느립니다. 문제에 대한 게시 된 솔루션은 제한된 Delaunay 삼각 측량 또는 직선 골격을 전처리 단계로 계산해야합니다. 둘 다 느리고 오류가 발생하기 쉽습니다.

유스 케이스의 경우 정확한 솔루션이 필요하지 않습니다. 우리는 더 빠른 속도를 얻기 위해 약간의 정밀도를 기꺼이 거래 할 의향이 있습니다. 우리가지도에 레이블을 배치 할 때, 수학적으로 완벽한 것보다 밀리 초로 계산하는 것이 더 중요합니다.

그러나 사용에 대한 빠른 메모. 소스 코드는 상자 밖에서 JavaScript에 적합하지만 "정상적인"다각형과 함께 이것을 사용하려면 여기의 함수가 취할 때 빈 배열로 래핑해야합니다. GeojsonPolygons 정상적인 다각형이 아니라 즉 

var myPolygon = [[x1, y1], [x2, y2], [x3, y3]];
var center = polylabel([myPolygon]);

어때요 :

다각형의 중심이 다각형 내부에 있으면 다음을 사용하십시오.

1) 다각형을 동일한 영역의 두 반쪽으로 나누는 다각형을 통해 중심에서 선을 확장

2) "시각적 중심"은 선이 주변에 닿는 가장 가까운 지점과 다음 지점이 중심에서 멀어지는 방향으로 주변을 자르는 지점 사이의 절반입니다.

설명하기위한 몇 가지 사진이 있습니다.

enter image description here

enter image description here

다각형의 각 모서리의 중심 위치 (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의 유용한 링크가 있습니다.

http://en.wikipedia.org/wiki/center_of_mass

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top