Menemukan koordinat batas dari set koordinat titik tertentu?

18

Diberikan seperangkat koordinat, Bagaimana kita menemukan koordinat batas.
mengatur koordinat <== Gambar 1
Mengingat koordinat dalam set di atas, Bagaimana saya bisa mendapatkan koordinat pada batas merah. Batas adalah poligon yang dibentuk oleh koordinat input untuk simpul, sedemikian rupa sehingga memaksimalkan area.

Saya sedang mengerjakan aplikasi yang mencari properti dalam jarak 'x' dari sebuah kota . Apa yang saya miliki adalah:

  1. Koordinat semua properti.
  2. Satu set koordinat untuk setiap kota (saya punya satu koordinat untuk setiap zip. Dan karena sebagian besar kota memiliki lebih dari satu zip, Setiap kota memiliki satu set koordinat)

Alasan saya meminta area maksimum adalah agar saya tidak membuat poligon seperti di bawah ini:

poligon bengkok <== Gambar 2

Yang saya butuhkan adalah algoritma untuk menghasilkan set koordinat untuk batas. Algoritme yang memungkinkan saya menghasilkan koordinat batas untuk Gambar 1 .

algorithm polygon-creation vertices convex-hull Khaja Minhajuddin
sumber
1
kemungkinan duplikat Concave Hull: Definisi, Algoritma, dan Solusi Praktis
Ian Turton
4
Tidak, bukan duplikat, ini lambung cembung, bukan cekung
Nicklas Avén
1
Apakah Anda mencari kode, referensi teoretis, atau solusi di lingkungan perangkat lunak spesifik yang ada?
WolfOdrade
1
@Khaja Tidak, Anda tidak ingin memaksimalkan area, Anda ingin meminimalkannya di antara semua poligon cembung yang mengandung titik-titik. (Satu-satunya cara untuk memaksimalkan area adalah dengan menggunakan seluruh dunia sebagai poligon yang mengandung.)
whuber
1
@whuber Ya, sekarang saya mengerti maksud Anda, saya ingin poligon cembung dengan area minimal. Tujuan utama saya adalah melakukan pencarian kedekatan. Cara kami ingin pencarian kedekatan kami bekerja adalah: Di kota tertentu (convex hull), jika kita mencari rumah (setiap rumah memiliki koordinat) dalam jarak "x" mil, itu akan memberi saya semua rumah yang berada di dalam convex hull atau berada pada jarak ortogonal kurang dari "x" mil
Khaja Minhajuddin

Jawaban:

21

Ada banyak algoritma untuk menyelesaikan masalah ini ( Wikipedia "Convex_hull_algorithms" ):

  • Pembungkus kado alias Jarvis march - O (nh): Salah satu algoritma paling sederhana. Ini memiliki kompleksitas waktu O (nh), di mana n adalah jumlah poin dalam himpunan, dan h adalah jumlah poin dalam lambung. Dalam kasus terburuk kompleksitasnya adalah O (n2).
  • Graham scan - O (n log n): Algoritme sedikit lebih canggih, tetapi jauh lebih efisien. Jika titik sudah diurutkan berdasarkan salah satu koordinat atau dengan sudut ke vektor tetap, maka algoritma membutuhkan waktu O (n). [ kode semu ]
  • QuickHull: Seperti algoritma quicksort, ia memiliki kompleksitas waktu yang diharapkan dari O (n log n), tetapi dapat berubah menjadi O (nh) = O (n2) dalam kasus terburuk. [ deskripsi bergambar ]
  • Membagi dan menaklukkan - O (n log n): Algoritma ini juga berlaku untuk kasus tiga dimensi.
  • Rantai monoton - O (n log n): Varian dari pemindaian Graham yang mengurutkan titik secara leksikografis berdasarkan koordinatnya. Ketika input sudah disortir, algoritma membutuhkan waktu O (n).
  • Algoritma hull cembung inkremental - O (n log n)
  • Marriage-before-conquest - O (n log h): Algoritme sensitif-keluaran yang optimal.
  • Algoritma Chan - O (n log h): Algoritme sensitif-output optimal yang lebih sederhana.
underdark
sumber
Terima kasih telah mendaftar @underdark ini ... pilih yang mana?
Marin
3

Yang Anda inginkan adalah lambung cembung. Di PostGIS ada fungsi (sebenarnya GEOS) yang memberi Anda convex hull, ST_ConvexHull (geometri) .

Di wikipedia ada banyak info tentang lambung cekung.

Nicklas Avén
sumber
1

Jika Anda menginginkan algoritma untuk melakukan ini (daripada paket yang dapat melakukannya) maka saya pikir Anda perlu melakukan triangulasi data; atau pada dasarnya mendefinisikan garis dari setiap titik ke setiap titik lainnya. Kemudian, mulai dari (katakanlah) titik dengan nilai Y tertinggi, lacak rute di luar mengikuti garis yang terhubung dengan sudut / bantalan eksterior terkecil.

Anda akan dapat mempercepat pelacakan dengan membuang garis berpotongan terlebih dahulu. Batas eksternal tidak akan memiliki persimpangan.

btw - FME akan melakukan ini juga dengan transformator ConvexHullAccumulator atau ConvexHullReplacer!

Tandai Irlandia
sumber
1

Jika Anda tertarik untuk melihat algoritma yang ada yang diimplementasikan dalam kode, NetTopologySuite memiliki algoritma untuk melakukan ini

Lihat ConvexHull.cs

Kebetulan NTS dan banyak perpustakaan lainnya terbungkus dalam proyek keren bernama DotSpatial, ditemukan di sini

WolfOdrade
sumber