Mendeteksi dua jenis poligon yang hampir sederhana

Saya tertarik pada kerumitan dalam memutuskan apakah poligon non-sederhana yang diberikan hampir sederhana, dalam salah satu dari dua pengertian formal yang berbeda: lemah sederhana atau tidak menyilang sendiri . Karena istilah-istilah ini tidak dikenal secara luas, izinkan saya mulai dengan beberapa definisi.

$P$ $p_0, p_1, p_2, \dots, p_{n-1}$ $p_i$ $p_i p_{i+1\bmod n}$
Poligon sederhana jika semua $n$ simpul berbeda dan ujung-ujungnya berpotongan hanya pada titik akhirnya. Secara ekivalen, poligon adalah sederhana jika itu adalah homeomorfik untuk sebuah lingkaran dan setiap sisi memiliki panjang positif. Secara umum, bagaimanapun, simpul dan tepi poligon dapat berpotongan sewenang-wenang, atau bahkan bertepatan. ¹
Pertimbangkan dua jalur poligonal dan yang persimpangannya merupakan subpath umum dari keduanya (mungkin satu titik). Kita mengatakan bahwa dan lintas jika endpoint mereka alternatif pada batas lingkungan dari umum subpath . Poligon adalah penyilangan diri jika memiliki dua subpath penyeberangan dan non-penyilangan diri . ² $A$ $B$ $A$ $B$ $A(0), B(0), A(1), B(1)$ $A\cap B$
Poligon lemah sederhana jika itu adalah batas urutan poligon sederhana, atau setara, jika ada gangguan kecil sembarang dari simpul yang membuat poligon sederhana. Setiap poligon sederhana yang lemah bersifat non-self crossing; Namun, beberapa poligon yang tidak bersilangan tidak sederhana.

Sebagai contoh, perhatikan enam poin $a,b,p,q,x,y$ ditunjukkan di bawah ini.

masukkan deskripsi gambar di sini

Poligon $abpqyz$ sederhana; lihat gambar kiri.
poligon $papbpqyqzq$ sangat sederhana; gambar tengah menunjukkan poligon sederhana terdekat. Namun, poligon ini tidak sederhana, karena dikunjungi $p$ tiga kali.
poligon adalah self-crossing, karena subpath dan cross. Lihat sosok yang tepat untuk intuisi. $papbpqzqyq$ $bpqz$ $yqpa$
Akhirnya, poligon (yang dua kali di sekitar poligon tengah) adalah non-self-crossing, tetapi tidak sederhana sederhana. Secara intuitif, angka balik poligon ini adalah , sedangkan angka balik setiap poligon sederhana harus . (Bukti formal memerlukan beberapa analisis kasus, sebagian karena angka balik sebenarnya tidak terdefinisi dengan baik untuk poligon dengan sudut !) $papbpqyqzqpapbpqyqzq$ $\pm 2$ $\pm 1$ $0^\circ$

Pembaruan (13 Sep): Pada gambar di bawah ini, poligon adalah non-self-crossing dan telah berbalik nomor 1 , tetapi tidak sederhana sederhana. Poligon dapat dikatakan memiliki beberapa penyeberangan sub- jalan yang tidak sederhana , tetapi tidak memiliki penyeberangan sub- jalan yang sederhana . (Saya katakan "bisa dibilang" karena tidak jelas bagaimana cara mendefinisikan ketika dua jalan yang tidak sederhana berjalan!) $abcabcxyzxpqrxzyx$

Jadi akhirnya, inilah pertanyaan saya yang sebenarnya:

Seberapa cepat kita dapat menentukan apakah poligon yang diberikan adalah non-self-crossing?
Seberapa cepat kita dapat menentukan apakah poligon yang diberikan sederhana sederhana?

Masalah pertama dapat diselesaikan dalam waktu sebagai berikut. Karena ada simpul, ada subpath vertex-ke-vertex ; kita dapat menguji apakah subpath tertentu sederhana dalam waktu (dengan kekerasan). Untuk setiap pasangan sub-simpul vertex-ke-vertex sederhana, kita dapat menguji apakah mereka melintasi dalam waktu . Tetapi ini bukan algoritma terbaik. $O(n^5)$ $n$ $O(n^2)$ $O(n^2)$ $O(n)$

Saya tidak tahu apakah masalah kedua dapat diselesaikan dalam waktu polinomial. Saya pikir saya dapat dengan cepat menghitung angka balik yang terdefinisi dengan baik untuk sembarang poligon non-sederhana (kecuali penyatuan ujung-ujung poligon hanya jalan, dalam hal ini poligon harus sederhana sederhana); lihat jawaban saya di bawah ini. Namun, contoh poligon baru di atas menyiratkan bahwa non-self-crossing dan balik nomor 1 tidak menyiratkan lemah sederhana.

Kita bisa menentukan apakah poligon yang diberikan adalah sederhana di waktu dengan memeriksa setiap sepasang tepi untuk persimpangan, atau waktu menggunakan algoritma sweepline standar, atau bahkan di waktu menggunakan algoritma triangulasi Chazelle. (Jika input poligon tidak sederhana, algoritma triangulasi apa pun akan melempar pengecualian, infinite-loop, atau menghasilkan output yang bukan triangulasi yang valid.) Tetapi tidak satu pun dari algoritma ini yang menyelesaikan masalah yang saya tanyakan. $O(n^2)$ $O(n\log n)$ $O(n)$

¹ Branko Grünbaum. Poligon: Meister benar dan Poinsot salah tetapi menang . Beiträge zur Algebra und Geometrie 53 (1): 57–71, 2012.

² Lihat, misalnya: Erik D. Demaine dan Joseph O'Rourke. Algoritma Lipat Geometris: Tautan, Origami, Polyhedra . Cambridge University Press, 2007.

ds.algorithms cg.comp-geom polygon Jeffε
sumber

Saya tidak mengerti mengapa orang akan memilih-turun pertanyaan ini ?!

Kaveh

Saya mungkin benar-benar salah paham terhadap pertanyaan, dan jadi mungkin ini tidak masuk akal, tetapi bagi saya tampaknya cara Anda menghitung simpul berarti bahwa pertanyaan kedua perlu waktu eksponensial. Biarkan saya jelaskan: Dalam contoh terakhir Anda, Anda menggunakan simpul yang sama beberapa kali. Tampaknya mudah untuk membuat grafik di mana ada sejumlah siklus unik yang eksponensial.

Joe Fitzsimons

Jika input Anda adalah poligon yang diberikan seperti dalam contoh Anda, maka mungkin bagi input untuk menjadi eksponensial dalam jumlah simpul tanpa pernah mengulangi siklus. Jika grafik berisi contoh grafik Anda (2 dan 3) sebagai subgraph, maka ia memiliki siklus yang non-persimpangan dan siklus yang persimpangan. Akibatnya, Anda perlu membaca seluruh string untuk memastikan Anda tidak memiliki siklus persimpangan (yang mungkin atau mungkin belum termasuk). Ini membutuhkan waktu eksponensial dalam

dalam kasus terburuk.

n

$n$

Joe Fitzsimons

@ JoFitzsimons: Input hanyalah urutan titik (yaitu, pasangan bilangan real), yang tidak perlu berbeda. Ukuran input

adalah panjang urutan ini, bukan jumlah titik unik.

n

$n$

Jeffε

@ Kaveh: Mungkin terlalu abstrak / terspesialisasi? Terlalu banyak kata? Seharusnya aku menyebutkan poinnya Ga, Ka, Naa, Taa, Tin, Khat ?

Jeffε

Jawaban:

Sepertinya pertanyaan pertama memiliki algoritma (meskipun ini juga kemungkinan tidak optimal). Dengan asumsi bahwa ada persimpangan, kunci untuk menemukan tampaknya bahwa tepi-tepi yang harus ditemukan adalah yang langsung berada di kedua sisi subpath umum. Oleh karena itu, kami melihat semua pasangan tepi yang berurutan. Ada angka kuadrat dari ini. Jika kita menemukan sepasang pasang tepi dengan simpul dan sedemikian rupa sehingga ujung dan adalah sama, maka kita mengikuti subpath umum ke ujung dan memeriksa tepi yang meninggalkannya. Jika mereka membentuk persimpangan dengan $O(n^3)$ $abc$ $def$ $bc$ $ef$ dan , maka kita selesai, kalau tidak kita pergi ke pasangan berikutnya. Mengikuti subpath umum paling banyak merupakan operasi linear-waktu, sehingga keseluruhan algoritma adalah . $ab$ $de$ $O(n^3)$

Analisis ini mungkin tidak ketat karena jumlah kali jalan bawah-panjang umum linear yang akan diikuti tidak linier dalam jumlah pasangan berpasangan. Seharusnya hanya ada jumlah yang konstan. Demikian pula, jika panjang subpath umum terpanjang adalah konstan, maka kita baik-baik saja dalam hal jumlah waktu mengikuti subpath umum. Saya berharap bahwa kasus terburuk muncul ketika ada satu subpath dengan panjang yang umum untuk $O(\sqrt{n})$ setapak. Lalu adainteraksi dan di setiap interaksi $O(\sqrt{n})$ $O(n)$ tepian diikuti. Jadi meski begitu, jumlah tepi yang diikuti adalah, dan terikat disediakan oleh jumlah pasangan. Jadi saya akan menebak bahwa batas sebenarnya untuk algoritma ini adalah. $O(\sqrt{n})$ $o(n^2)$ $O(n^2)$

Chris Gray
sumber

"Mengikuti jalan setapak bersama paling banyak adalah operasi linear-waktu ..." Apakah ini benar? Ingatlah bahwa subpath tidak identik. Satu mungkin melipat bolak-balik di sepanjang gambar yang lain. Bahkan, bahkan tidak jelas (bagi saya) ketika Anda tahu Anda sudah selesai.

Pat Morin

Poin bagus. Apakah mungkin, sebagai langkah preprocessing, untuk meletakkan poligon dalam semacam bentuk standar? Kami akan menghilangkan jalan yang langsung terlipat pada diri mereka sendiri, serta simpul yang collinear dengan tetangga terdekat mereka. Maka kalimat yang Anda kutip akan lebih baik didefinisikan - subpath umum terdiri dari tepi yang memiliki simpul yang sama, dan Anda tahu bahwa Anda selesai karena Anda menekan simpul yang berbeda. Membuktikan bahwa jawabannya tetap sama dalam poligon dalam bentuk standar seharusnya tidak terlalu sulit.

Chris Gray

@ ChrisGray: Mungkin, tapi tidak semudah yang Anda sarankan. Jika gambar

adalah pohon, maka secara rekursif menghilangkan semua switchback akhirnya mengurangi

ke satu titik.

P

$P$

P

$P$

Jeffε

Ya, Anda benar, gagasan itu tidak akan berhasil. Angka paling kanan yang Anda berikan di atas akan dikurangi menjadi satu titik.

Chris Gray

Saya berencana untuk membiarkan hadiah berakhir; setengah poin akan secara otomatis diberikan kepada jawaban ini.

Jeffε

Atas saran Pat Morin, inilah ide saya untuk menghitung angka balik. Maaf jika ini agak ceroboh; Saya masih berjuang dengan notasi setan. Selain itu, komentar Pat terhadap jawaban Chris mengungkapkan bahwa saya telah mengabaikan beberapa kasus penting yang merosot. Tapi saya akan memposting ini di sini kalau-kalau orang lain merasa berguna.

Untuk setiap indeks , misalkan menunjukkan sudut eksternal yang ditandatangani pada titik ; ini adalah sudut berlawanan arah jarum jam dan , dinormalisasi ke kisaran $i$ $\theta(p_i) = \theta(p_{i-1}, p_i, p_{i+1})$ $p_i$ $\overrightarrow{p_{i-1}p_i}$ $\overrightarrow{p_ip_{i+1}}$ . (Semua indeks aritmatika secara implisit mod .) The Jumlah balik dari didefinisikan sebagai $-\pi \le \theta_i \le \pi$ $n$ $P$ Mari saya sebut titikamemacujikainternal yangsudut disama dengan. Sudut eksternalpada taji tidak didefinisikan dengan baik; itu bisaatau. Lebih umum, jumlah belokandidefinisikan dengan baik jika dan hanya jikatidak memiliki taji (dan tidak ada simpul berulang

T u r n (P) = \frac{1}{2 π} \sum_{i = 0}^{n - 1} θ (p_{i}) .

$Turn(P) = \frac{1}{2\pi} \sum_{i=0}^{n-1} \theta(p_i).$

p_{i}

$p_i$

p_{i}

$p_i$

0

$0$

θ_{i}

$\theta_i$

π

$\pi$

- π

$-\pi$

P

$P$

P

$P$

). Tidak sulit untuk membuktikan bahwa

adalah bilangan bulat jika didefinisikan dengan baik; khususnya,

jika

adalah poligon sederhana.

p_{i} = p_{i + 1}

$p_i=p_{i+1}$

T u r n (P)

$Turn(P)$

T u r n (P) = \pm 1

$Turn(P) = \pm 1$

P

$P$

Sekarang anggaplah mengandung berjalan dari bentuk , di mana dan jalan adalah kebalikan dari jalan . Maka adalah taji; panggilan yang akar dari . Dalam hal ini, izinkan saya mendefinisikan sudut eksternal pada sebagai berikut: $P$ $p\mathord\to r\mathord\leadsto s\mathord\leadsto r\mathord\to q$ $p\ne q$ $r\mathord\leadsto s$ $s\mathord\leadsto r$ $s$ $r$ $s$ $s$ (Tetapi bagaimana jika ? Sebagaimana Pat amati, ini benar-benar dapat terjadi. Mungkin ada semacam cara rekursif untuk mendefinisikan

\tilde{θ} (s) = π \cdot s g n θ (p, r, q) = {\begin{cases} π & if θ (p, r, q) > 0 \\ - π & if θ (p, r, q) < 0 \end{cases}

$\tilde\theta(s) = \pi \cdot \mathop{sgn}\theta(p, r, q) = \begin{cases} \pi & \text{if } \theta(p, r, q) > 0\\ -\pi & \text{if } \theta(p, r, q) < 0 \end{cases}$ $\theta(p,r,q)=0$ $\tilde\theta(s)$ bahkan dalam hal ini, tetapi saya tidak tahu apa itu.)

$P$ $n$ $\tilde{P}$ $P$ $\tilde{s}$ $\tilde{P}$ $P$ $\tilde{P}$ $P$ $\tilde{s}$ $r\mathord\leadsto s$ $\theta(\tilde{s})$ $\tilde\theta(s)$

$P$ $r\mathord\leadsto s\mathord\leadsto r$ $r$ $s$ $P$ $r\mathord\leadsto s$

$\tilde\theta(p_i) = \theta(p_i)$ $p_i$ $\widetilde{Turn}(P) = \sum_i\tilde\theta(p_i)/2\pi = Turn(\tilde{P})$ , which must be $\pm 1$ if $P$ is weakly simple.

I'm no longer confident that $\widetilde{Turn}(P)$ can be computed in linear time. The main difficulty is that the walk $r\mathord\leadsto s$ can itself contain spurs. The naive algorithm that finds the root of each spur by brute force actually takes $\Theta(n^2)$ time in the worst case; consider an $n$ -gon that has a subwalk of length $\Omega(n)$ that simply alternates between two points.

Jeffε
sumber