0 Dan jika ada definisi perimeter non berpotongan satu set..."/>

Apakah ada algoritma untuk menemukan lambung yang hampir cembung dengan sudut toleransi?

9

Saya ingin tahu apakah ada algoritma yang memberikan satu set titik o dan sudut menghitung cembung-lambung jika sudutnya dan diberi α > 0 menghitung amplop yang mengikuti lebih dekat "perimeter".α=0α>0

Ilustrasi efek $ ukuran alpha $

Dan jika ada definisi perimeter non berpotongan satu set poin, dalam hal ini poligon yang dihasilkan ketika besar.α

Pandangan lain dari masalah tersebut adalah menemukan algoritma yang dapat diparameterisasi untuk mencari solusi perimeter minimum (convex-hull) dan untuk α = 1 (dinormalisasi) area minimum polyline yang melingkupi semua titik.α=0α=1

algorithms computational-geometry naufraghi
sumber
Sudahkah Anda melihat konsep set yang sangat cembung ?
Deathbreath
α
αα
Saya bermaksud sebagai sudut algoritma diizinkan untuk menjauh dari lambung cembung. Dan tidak, saya tidak berpikir itu akan mengurangi kompleksitasnya.
naufraghi

Jawaban:

3

Anda dapat menyelidiki apa yang disebut alpha-hull , misalnya: paket CRAN , Wikipedia pada bentuk alpha :
       masukkan deskripsi gambar di sini
      [Gambar dari tautan ini .]

Alfa-lambung memiliki sifat geometris yang sangat bagus, dan telah banyak dipelajari, tetapi masih belum sesuai dengan tujuan Anda.

Joseph O'Rourke
sumber
Terima kasih, alfa-bentuk sangat menarik, mereka memiliki superset dari properti yang saya cari (saya hanya tertarik pada satu amplop), dan implementasinya tidak sebanding dengan cembung-lambung. Saya akan menunggu lebih lama jika seseorang dapat menyarankan sesuatu yang lebih sederhana, jika tidak saya akan menerima jawaban ini.
naufraghi
1

α

α

Kami ingin memikirkan struktur data yang akan membuat menemukan titik yang ditentukan menjadi efisien. Satu ide adalah menghitung kotak batas untuk setiap segmen dan memeriksanya terhadap daftar poin yang diurutkan.

hardmath
sumber