點在多邊形

Question

我試圖做一些SPOJ問題是https://www.spoj.pl/problems/FSHEEP/

我們必須找出如果點在多邊形內。如我們所見，它不是凸多邊形（來自問題的圖像）。

我試圖用維基百科或任何其他網站上描述的Ray Casting算法在O（n * m）時間內解決它。

但是如何在O（n log m）中解決它？ 換句話說，如何在對數時間檢查點是否在多邊形？

乾杯

Answer 1

由於這是一門功課式的問題，我給你的功課式的幫助。經驗法則：無論何時你看到log n，你都應該考慮「binary-something」（搜索，樹等）。當你看到n個記錄時，你應該考慮「排序」。你會驚奇地發現它的工作頻率。你可以在你的big-O限制內對頂點和二進制搜索進行排序嗎？

UPDATE：

我不想讓你掃興：你實際上是在給定的分類順序的多邊形頂點，所以重要的是排序爲你做。您不需要在角度空間中創建區間，使用排序頂點數組的索引作爲區間。

把你的光線從農民身上投射到頂點。如果是順時針，則順時針進行二分搜索。如果是逆時針方向，則進行二進制搜索。兩個頂點和農民形成一個邊界三角形。羊在三角形邊界嗎？

瘋狂懶僞代碼：

if vertex[m] and vertex[0] trivially bound the sheep 
    l=m, r=0 
else 
    l=0, r=m 
    while (r-l > 1) 
    middle = (r-l)/2 
    if vertex[l] and vertex[middle] bound sheep 
     r = middle 
     continue 
    else if vertex[middle] and vertex[r] bound sheep 
     l = middle 
     continue 
    else some_jerk_gave_you_a_sheep_on_a_ray 

check vertex[l],vertex[r],farmer triangle 

二進制搜索是爲O（log M）。三角形檢查是O（1）。迭代n只綿羊會給你O（n）* O（log m）* O（1）= O（n log m）。