Dari waktu ke waktu saya harus membuat buku peta untuk menunjukkan tempat menarik. Langkah pertama untuk membuat halaman, menggunakan mesh biasa:
Saya tidak suka solusinya karena a) ada beberapa halaman dengan titik tunggal (mis. Halaman 25) duduk di tepi dan b) terlalu banyak halaman.
Masalah pertama mudah diperbaiki dengan menggunakan kode, - pindahkan persegi panjang dari luas halaman ke pusat sejauh mana poin-poin yang relevan:
Saya masih tidak suka, itu terlihat sangat ramai karena jumlah halaman tetap sama. Ingat, semuanya akhirnya menjadi halaman kertas A3 aktual dalam banyak salinan laporan!
Jadi saya sudah memasak kode yang mengurangi jumlah halaman. Dalam contoh ini dari 45 hingga 34.
Saya tidak yakin apakah ini hasil terbaik yang bisa dicapai,
Apa strategi terbaik (kode semu, publikasi, pustaka Python) untuk mengacak titik-titik untuk meminimalkan jumlah persegi panjang ukuran yang diberikan untuk menangkap semua titik? Tentunya, seseorang menemukannya dalam teori permainan, seni militer atau industri perikanan
Ini adalah pembaruan untuk pertanyaan awal:
Ini menunjukkan tingkat nyata dan ukuran halaman yang dibutuhkan:
Zoom lebih dekat menampilkan 10 dari 164 halaman:
Ukuran persegi panjang dapat berubah begitu tetap dalam batas, yaitu lebih kecil baik-baik saja.
Jawaban:
Ini bukan jawabannya, saya hanya berpikir saya memposting solusi Python bagi mereka yang tertarik:
menerapkannya akhir-akhir ini untuk perencanaan survei:
MEMPERBARUI:
Tampaknya untuk beberapa pola berurusan dengan poin 'menyimpang' terlebih dahulu adalah cara untuk pergi. Saya telah menggunakan kulit 'cembung lambung' untuk mengidentifikasi mereka, gagasan whuber, tidak dapat menemukan pos, maaf.
sumber
Ini terlihat seperti versi geometris dari Masalah Cakupan Maksimum yang terkait erat dengan Masalah Set Penutup , dan keduanya adalah NP-Lengkap.
Jadi untuk mengatasinya, seseorang bisa menggunakan pendekatan. Saya akan mencoba algoritma berikut dan tampaknya berfungsi dengan baik. Meskipun karena kompleksitas masalah, kami tidak dapat menemukan jawaban terbaik.
implementasi algoritma ini, hanya untuk lingkaran, ada di sini: http://jsfiddle.net/nwvao72r/3/
sumber