二維範圍三角形的搜索樹

Question

我想實現2D RANGE TREES以有效地在O（logn^2）中搜索三角形內的給定點。

爲了使事情更容易，我想搜索沒有給定的點位於直角三角形，兩邊平行於x-y軸並且兩邊相同。因此，ABC的頂點座標將是A（a，b），B（a + d，b），C（a，b + d），它是一個直角三角形，AB，AC與X ，Y軸。

我知道我能做到這一點有效地利用2D範圍內的樹木。（KD樹O（開方（N））是緩慢的，搜索的每個點分別是太慢）

誰能告訴我如何實現/解釋算法2D範圍樹來測試哪些點位於上面類型的三角形內？

Answer 1

請參考CGAL圖書館或此人的項目code和report。

此外，contest仍在進行中，請不要在此處尋求幫助，直到比賽結束。