我需要一种计算点与多边形边界距离的方法。
该多边形由多个路径组成,可以是凹形的,带有空洞,但不能自交,并且有很多顺时针排序的点(10000+)。 我发现了一些现有解决方案,但它们需要对每个多边形边缘测试点,这不够高效。
以下是生成的可视结果(绿色为正,红色为负):
遗憾的是,当该点与多个边缘处于相同距离时(例如角落),该方法无效。
我尝试添加条件,如果一个点在所有边的外部,则它在多边形外部,但这并不能解决内部问题,反之亦然。
我无法理解这个问题... 如果有人感到好奇,这个想法是之后使用一些着色器来生成这样的图像:
- 如果点在多边形外部,距离将为正数
- 如果点在多边形内部,距离将为负数
该多边形由多个路径组成,可以是凹形的,带有空洞,但不能自交,并且有很多顺时针排序的点(10000+)。 我发现了一些现有解决方案,但它们需要对每个多边形边缘测试点,这不够高效。
以下是生成的可视结果(绿色为正,红色为负):
所以我尝试了以下方法:
将多边形的边放入四叉树中
为了计算距离,需要找到最接近该点的边,并根据该点位于边的哪一侧改变符号。遗憾的是,当该点与多个边缘处于相同距离时(例如角落),该方法无效。
我尝试添加条件,如果一个点在所有边的外部,则它在多边形外部,但这并不能解决内部问题,反之亦然。
我无法理解这个问题... 如果有人感到好奇,这个想法是之后使用一些着色器来生成这样的图像:
编辑
为了澄清问题,这里是在拐角处出现的问题的近距离照片:
- 对于区域A中的所有点,最近的线段是S1,因此没有问题
- 对于区域E中的所有点,最近的线段是S2,因此也没有问题
- 区域B、C和D中的所有点与S1和S2的距离相同
- 区域B中的点位于S1的外侧和S2的内侧
- 区域D中的点位于S1的内侧和S2的外侧
- 区域C中的点位于两个线段的外侧
有人可能认为一个点必须在两个线段的内侧才能被视为“在内部”。这解决了角度小于180°的问题,但是对于角度大于180°的问题则恰好相反。
更糟糕的是,两个或更多的角落可以共享相同的位置(例如第一张图中低部的四路口)...