three.js 点云场景下怎么高性能的判断点point是否在某个长方体box内

Question

要对几万个点乃至十几万个点以及几十个box做判断，拿到每个box内的点。已有的数据包括各个点的坐标；box欧拉旋转角,各顶点坐标。

想要的效果：

1. 减少每次判断的点数量——找到box附近的点来做计算，而不是全部点遍历。（我想到的做法是把整个点云的点存在各个矩形区域内，按box中心点和尺寸找到各个顶点落在的矩形构成的大矩形区，拿到这个区域的点来计算）
2. 单个点的判断逻辑。（现在的做法是点坐标转到box中心坐标系，判断点坐标是否超过了length/2,height/2,width/2）

大家还有什么好的建议吗？

Answer 1

从你的描述来看，box是有旋转角的，对每个box都可以找到一个对应的外接水平矩形（矩形的4个顶点为{(x1,y1),(x1+w,y1},(x1+w,y1+h),(x1,y1+h)}，以这个外接水平矩形为筛选，可以很快筛选出可能在box内的点范围，既任意点(x,y)要可能在 box内，必有x1<=x<=x1+w and y1<=y<=y1+h ,这样可以很快的减少比较量。如果你的点集提前排序，则可以很快的对每个box先取出可能点集，再进一步计算。

至于对具体点的判断，因为你已经有box的4边线段方程，也有外接矩形的顶点，则对任意点(x,y)，与外接矩形任意顶点连线构成的线段，如果和box的任意边有且只有1个交点，则点在box内，否则在外。