경로를 커버하기 위해 타일을 선택하는 알고리즘은 무엇입니까?

Question

지도에서 세그먼트 경로/경로가 있고 소프트웨어가 경로를 완전히 커버하기 위해 서버에서 이미지를 요청해야합니다. 서버에 대한 이미지 요청은 직사각형 영역 (기본 방향으로 정렬)에 대해서만 가능합니다. 경로의 경계 사각형에 대해 하나의 큰 이미지를 요청하기 만하면 특히 긴 경로의 경우 매우 큰 이미지를 다운로드하는 경우가 많습니다. 특히 길고 굴곡이 많은 경로의 경우 몇 가지 작은 이미지 요청으로 나누는 것이 좋습니다.

하지만 난 이것에 대한 좋은 알고리즘을 찾는 데 어려움을 겪고 있습니다. 누구든지 관련 알고리즘이나 백서 또는 유용 할만한 것을 알고 있습니까? 제안? 이 이미지는 단어에서 내가 할 수있는 것보다 문제가 더 나은 설명 : 당신은 당신이 모든 세부 사항을 가지고 있다고 확신

This image explains the problem and challenges

Answer 1

있습니까? 내가 익숙한 시스템에서 정보를 사용할 수있는 영역이 바둑판 식으로 배열되어 있기 때문에 임의의 지리적 영역이 아닌 타일 만 요청할 수 있습니다. 다양한 크기의 타일을 사용할 수 있지만 더 작은 영역을 다루는 타일은 세부 사항을 제공하므로 타일 크기를 선택하는 것은 사용자가 다루려는 영역에 의존하지 않고 표시하려는 세부 수준에 달려 있습니다. 데이터를 제공하는 기본 시스템이 타일 기반이라면 통신 트래픽을 최적화하지는 않더라도 정확한 타일 영역을 요청하여 편리하게 사용할 수 있습니다. 또한 타일 선택을 단순화합니다. 원하는 디테일을 결정한 다음 표시 할 영역을 커버하는 데 필요한 모든 타일을 요청할 수 있습니다.

실제로 질문 한 문제로 돌아가서, 일정한 기울기가있는 한 개의 직선을 고려하십시오. 지도를 지정된 너비의 세로 스트립으로 자르면 각 스트립에는 제공해야하는 사각형이 포함되어 있으므로 줄의 위와 아래에 항상 100 마일의 영역을 표시 할 수 있습니다. 그래서 사각형 너비가 주어진다면 필요한 사각형 높이를 계산할 수 있습니다. 직사각형 너비가 주어지면 필요한 사각형의 수를 산출 할 수 있으므로 비용을 결정하는 두 가지 사항, 즉 직사각형의 수와 직사각형의 전체 면적이 달라집니다. 일반적으로 직사각형을 전송하는 비용은 대략 직사각형 당 일정한 비용이며 직사각형의 영역과 함께 증가하는 가변 비용입니다. 이러한 비용을 평가하는 한 가지 방법은 다양한 크기의 직사각형을 전송하는 데 필요한 데이터의 양을 측정하고 직선을 그 크기에 맞추는 것입니다. 다양한 직사각형 너비에 대한 비용을 계산하는 방법을 고려할 때, 가장 효율적인 너비를 산출하기 위해 1 차원 숫자 최소화 루틴을 사용합니다. 한 가지 예는 https://en.wikipedia.org/wiki/Golden_section_search입니다.

Answer 2

귀하의 문제는 내가 그 가정거야 그래서 몇 가지 세부 사항이 결여되어

1. 이 폭과 높이가 어떤 형태의 화면에 간다, 그래서 그 지역에 필요한 최소한의 덮여 경로를 따라 이동할 때 화면에 의해.
2. 요청 수는 전송되는 데이터 양만큼 중요하지 않습니다.

그럼 당신이 할 수있는 것은 분단하고 정복하는 것입니다. 당신은 둘러싼 사각형으로 시작합니다. 각 단계에서 다음과 같은 경우를 알 수 있습니다.

1. 사각형이 하나의 세그먼트에서 관심 영역 내에 있습니다. 즉, 사각형에 다운로드하려는 픽셀 만 포함되어 있습니다.
2. 직사각형이 관심 영역 외부에 있습니다.
3. 관심 영역과 일부 중복됩니다.
4. 일부 중복되지만 사각형이 충분히 작습니다. 사각형이 완전히 또는 밖으로 다음은 쉽게 경우 아웃 경우가에서 무시되는 경우

는 사각형을 요청합니다. 중복이 있지만 사각형이 작 으면 (사례 4) 계산을 쉽게하기 위해 다운로드 할 수 있습니다. 픽셀로 내려갈 수는 있지만 과장 될 수 있습니다.

까다로운 경우는 일부 겹침이 있고 사각형이 큰 경우입니다. 이 경우 사각형을 4 개의 작은 것들 (각면을 따라 절반)으로 나누고 4 개의 작은 것들을 재귀 적으로 호출합니다. 하나의 작은 최적화 : 알고리즘이 4 개의 작은 것들 모두를 완전히 가져 오는 것으로 결정하면, 작은 것들 4 개 대신 큰 것을 가져와야합니다.

포함 겹침을 결정하려면 경로의 각 부분을 가져올 수 있으며 각각에 대해보기 사각형을 각 끝에 배치하고 해당 모서리를 연결하고 볼록 선체를 가져옵니다. 그런 다음 볼록 선체와 테스트 할 직사각형의 교차점/겹침을 계산합니다.

이것은 약간 복잡해 보이지만 모퉁이의 경우 (매우 작은 경로 세그먼트 또는 자체 교차 경로 같은)를 잘 다루어야합니다.