我想实现 2D RANGE TREES 以在 O( logn^2 ) 中有效地搜索三角形内的给定点。
为了使事情更容易，我想搜索位于直角三角形中的给定点，其中两侧平行于 xy 轴对齐并且两侧相同。因此，ABC 的顶点坐标为 A(a,b) , B(a+d,b) , C(a,b+d) 并且它是一个直角三角形并且 AB,AC 平行于 X， Y轴分别。
我知道我可以使用 2D 范围树有效地做到这一点。（kd 树 O(sqrt(n)) 很慢，单独搜索每个点太慢）
谁能告诉我如何实现/解释算法 2D 范围树来测试哪些点位于三角形类型的上方？