二维范围三角形的搜索树

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仍在进行中，请不要在此处寻求帮助，直到比赛结束。