Bagaimana cara menghitung kotak pembatas dari banyak lapisan dalam lat / long?

Saya menulis aplikasi untuk menguji kinerja semua jenis layanan peta, terutama AGS 9.x, AGS 10, dan WMS 1.x.

Bagian dari aplikasi melibatkan pembuatan kotak pembatas acak untuk permintaan individu, dalam cakupan penuh layanan. Bagian ini berfungsi dengan baik untuk sistem koordinat geografis dan yang diproyeksikan ketika tingkat layanan sepenuhnya diketahui (misalnya melalui properti FullExtent layanan AGS).

Masalah saya adalah dengan WMS: setiap lapisan dalam respons GetCapabilities dapat menentukan area pembatas di> = 1 CRSs. Beberapa bagian aplikasi perlu mengetahui apakah CRS layanan bersifat geografis atau diproyeksikan, jadi untuk menghapus ambiguitas dalam WMS, saya selalu menggunakan layer LatLonBoundingBox yang selalu ditentukan dan dalam EPSG: 4326. Saya kemudian harus menghitung kotak pembatas layanan penuh berdasarkan pada semua lapisan yang masuk ke permintaan individu (yang diacak). Di sinilah rumit.

Saya tersesat karena untuk setiap kotak pembatas lat / lon, LLx (bujur kiri bawah) bisa menjadi angka yang lebih besar atau lebih kecil daripada URx (bujur kanan atas), tergantung pada meridian mana yang melingkupinya. Setiap kali saya mulai menggambar diagram persegi atau lingkaran, saya pikir saya memiliki pendekatan yang ditemukan, dan kemudian menemukan sebuah kasus yang merusaknya dan otak saya berubah menjadi bubur.

Saya akan terus meronta-ronta sampai berhasil, dan jika saya mendapatkan solusi posting di sini, tapi saya yakin harus ada pendekatan yang diterima dan diuji sepenuhnya yang akan membuat hidup saya lebih mudah. Saya tidak bisa menemukannya sekarang.

Artikel yang direferensikan adalah bijaksana. Namun, saya percaya ada adalah "sederhana dan elegan" solusi: untuk dataset geografis, ada dua jenis kotak bounding. Mereka yang tidak mengangkangi meridian + -180 dapat disimpan dan dicari seperti biasa. Mereka yang mengangkangi meridian + -180 dapat disimpan dalam bentuk semi-komplementer : yaitu, menyimpan rentang garis lintang seperti biasa, tetapi menyimpan kisaran garis bujur yang tidak termasuk dalam kotak (dan beralih sedikit untuk menunjukkan bentuk mana penyimpanan sedang digunakan). Pada dasarnya tidak ada modifikasi yang perlu dilakukan pada indeks geografis atau struktur pohon pencarian; hanya sedikit modifikasi yang diperlukan untuk algoritma pencarian.

Bagaimanapun, inilah solusi untuk pertanyaan itu sendiri.

Saya kira Anda mengantisipasi input menjadi urutan deskriptor kotak pembatas ((LLx, LLy), (URx, URy)) di mana:

• -540 <= LLx, -180 <= URx, LLx <= 180, dan URx <= 180. Juga -90 <= LLy <= URy <= 90.

• sebuah titik di (garis bujur, garis lintang) = (x, y) dianggap terletak di dalam BB jika dan hanya jika

  1. LLy <= y <= URy dan

  2. baik LLx <= x <= URx atau LLx - 360 <= x <= URx.

Untuk output, Anda ingin parameter untuk kotak pembatas terkecil yang berisi gabungan semua input.

Jelas batas-y dari kotak batas minimum (MBR) akan menjadi minimum dan maksimum dari nilai-y. Untuk batas-x, gunakan sapuan garis untuk menemukan celah terbesar .

Berikut deskripsi algoritme. Untuk menggambarkannya, anggap input terdiri dari empat kotak,

((-81,-16),(-77,80)),
((77,-19),(156,5)),
((-149,-45),(-90,81)),
((-69,-85),(-36,-76))

Berikut adalah diagram kotak (merah) dan MBR (hitam) yang pertama, lalu dua yang pertama, lalu tiga yang pertama, lalu semua kotak.

Perhatikan bagaimana pada langkah kedua, kotak-kotak di belahan timur dan barat dikelilingi oleh MBR yang melintasi meridian + -180 derajat, membuatnya tampak sebagai dua kotak terpisah di peta ini. Pada langkah terakhir, MBR itu harus diperluas ke arah timur untuk mengakomodasi kotak kecil antara Amerika Selatan dan Antartika.

1. Ekstrak semua koordinat x kotak, hitung mereka modulo 360 (untuk menempatkannya dalam kisaran -180..180), urutkan mereka naik, dan tambahkan nilai pertama (bertambah 360 derajat) ke ujung untuk membuatnya membungkusnya sekitar:

   -149, -90, -81, -77, -69, -36, 77, 156, 211
   

   (Perhatikan bahwa 211 dan -149 adalah meridian yang sama.)

2. Pikirkan setiap koordinat x sebagai mewakili interval antara koordinat sebelumnya (tetapi tidak termasuk nilai sebelumnya) dan itu. Misalnya, -77 mewakili semua nilai dari -81 hingga -77 tetapi tidak termasuk -81. Untuk masing-masing setelah yang pertama, hitung jumlah kotak yang berisi interval itu.

   1, 0, 1, 0, 1, 0, 1, 0
   

   Sebagai contoh, "1" pertama berarti bahwa satu kotak mencakup interval dari -149 hingga -90. (Ini kotak ketiga.)

   Sebagai pengoptimalan, Anda dapat menghentikan penghitungan segera setelah menemukan kotak apa pun yang mencakup interval x dan beralih ke interval x berikutnya. Kami hanya mencoba menentukan interval mana yang mungkin tidak dicakup oleh kotak apa pun.

3. Hitung perbedaan pertama koordinat x yang diurutkan dalam (1).

    59, 9, 4, 8, 33, 113, 79, 55
   

   Cocokkan ini dengan jumlah cakupan dalam (2). Temukan perbedaan terbesar yang cakupan cakupannya adalah 0. Di sini, itu sama dengan 113, elemen keenam dari array sebelumnya. Ini adalah kesenjangan terbesar dalam garis bujur yang ditinggalkan oleh koleksi kotak.

   (Yang menarik, kemungkinan bahwa maksimum terjadi di lebih dari satu lokasi menunjukkan bahwa solusinya tidak selalu unik! Mungkin ada lebih dari satu MBR untuk satu set kotak. Anda dapat menentukan yang unik dengan menambahkan kondisi tambahan, seperti membutuhkan bahwa jarak rata-rata dalam MBR ke + -180 meridian menjadi sebesar mungkin; untuk menyelesaikan dasi, pilih (katakanlah) solusi paling timur.)

4. Temukan interval yang sesuai: di sini, dari -36 hingga 77. Ini adalah rentang garis bujur yang tidak ada di MBR. Oleh karena itu, ambil komplemennya dalam kisaran -180 hingga 180. Di sini, komplemen adalah dua interval terpisah, satu dari -180 hingga -36 dan yang lain dari 77 hingga 180. Atau, mewakili komplemen sebagai satu persegi panjang yang mungkin mengangkangi + -180 derajat meridian: dari -283 hingga -36 di sini (atau, setara, dari 77 hingga 324).

5. Gunakan min dan maks dari nilai-y untuk sudut MBR.

   ((-283, -85), (-36, 81))