我发现 Java 中的 GeneralPath 类只提供了检查点是否在一般路径内的方法(具体来说，具有直线段的多边形 ).有人知道如何高效检查一个点是否在一般路径的边界上吗？
谢谢
虚拟解决方案 1: 我们可以定义一个半径为 $\epsilon$ 的圆($\epsilon$ 是一个非常小的正实数值)。然后，我们检查圆上足够多的点，看看其中一个/一些是否落入一般路径。然而，这种虚拟方法可能需要相当大的计算量，这不是很理想。
虚拟解决方案 2: 我们可以计算点(在边界上)到多边形每一边的距离。如果最小距离足够小，则该点在边界上；否则，它不是。同样，此方法仍然需要大量计算。
最佳答案
我还没有遇到过库方法……或问题的解决方案。我认为原因是这个问题根本不可能准确解决。
GeneralPath 类从 Shape2D 继承了一个名为 getPathIterator 的方法。如果查看 javadoc，您会看到 PathIterator 对象将路径建模为一系列直线段。 getPathIterator 方法接受一个 flatness 参数，指定如下:
"flatness - the maximum distance that the line segments used to approximate the curved segments are allowed to deviate from any point on the original curve."
现在，如果您正在查看的形状由直线段组成，则路径迭代器很有可能会为您提供这些直线段。但是如果形状有曲线段，那么线段只是一个近似值。如果您不知道确切的边界是什么，显然不可能测试一个点是否正好在边界上。
即使假设线段完全模拟真实曲线，您仍然会遇到问题(特殊情况除外)，真实曲线上的大多数点无法使用 Java 基本数据类型(int、double 等)准确表示).因此，“准确性”再次成为问题。
我认为最好的办法是测试你的点是否在边界的某个小增量范围内......然后选择一个小于该增量的 flatness 值，迭代路径线段，并测试点到每段的切线距离。
注意:如果您使 flatness 非常小，您可能需要测试大量的线段。在坚持使用 GeneralPath API 的同时，我认为没有任何方法可以解决这个计算问题。
如果您将问题限制为真实(即直边)多边形，那么您只需要迭代线段，并针对每个线段进行测试，看看点到线的距离是否小于某个合适的 epsilon . This Wikipedia entry给你数学。请注意，这里的准确性仍然是一个问题......
您的计算成本并不高，但计算准确的平方根并不是免费的，对于 N 边多边形，您最多需要执行 N 次计算。
做得更好(即比 O(N) 更好)将很困难。但是，如果多边形是固定的并且您要针对它测试大量点，那么您可以考虑使用预计算的四叉树数据结构来进行解析。预先计算四叉树会很昂贵，但如果 N 足够大，测试 a a 点会更便宜。 (在最坏的情况下大约是 O(log(1/epsilon))，而不是平均 O(N)。并且一个点离边界越远，答案越便宜。)
但正如我所说，四叉树只会在有限的情况下提供帮助......
关于java - 在 Java 中，如何判断一个点是否在 GeneralPath 的边界上？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13576753/