7

我发现GeneralPathJava中的类只提供了检查一个点是否在一般路径内的方法(具体来说,一个带有直线段的多边形)。有人知道如何有效地检查一个点是否在一般路径的边界上吗?

谢谢

虚拟解决方案 1:我们可以定义一个半径为 $\epsilon$ 的圆($\epsilon$ 是一个非常小的正实值)。然后,我们检查圆上足够数量的点,看看它们中的一个/一些是否落入一般路径。然而,这种虚拟方法可能需要大量的计算工作,这不是非常理想的。

虚拟解决方案 2:我们可以计算从点(在边界上)到多边形每一边的距离。如果最小距离足够小,则该点在边界上;否则,它不是。同样,这种方法仍然是计算密集型的。

4

2 回答 2

4

我还没有遇到图书馆方法......或解决问题的盆栽解决方案。我认为原因是这个问题根本不可能完全解决。

该类继承了一个从GeneralPath调用的方法。如果您查看 javadoc,您将看到该对象将路径建模为一系列直线段。该方法采用如下指定的参数:getPathIteratorShape2DPathIteratorgetPathIteratorflatness

“平面度 - 用于逼近曲线段的线段允许偏离原始曲线上任何点的最大距离。”

现在,如果您正在查看的形状由直线段组成,那么路径迭代器很有可能会为您提供这些线段。但是如果形状有曲线段,那么线段只是一个近似值。如果你不知道确切的边界是什么,显然不可能测试一个点是否正好在边界上。

即使假设线段精确地模拟了真实曲线,您仍然存在这样的问题(除了特殊情况),真实曲线上的大多数点无法使用 Java 原始数据类型(int、double 等)精确表示。因此,“精确性”再次存在问题。

我认为你能希望的最好的结果是测试你的点是否在边界的某个小增量内......并选择一个flatness小于该增量的值,迭代路径线段,并测试切向距离每个段的点。

注意:如果你做flatness的非常小,你可以预期必须测试大量的线段。在坚持使用 GeneralPath API 的同时,我认为没有任何方法可以解决这个计算问题。


如果您将问题限制为真正的(即直边)多边形,那么您只需要迭代线段,并为每一个测试看看从点到线的距离是否小于某个合适的 epsilon。 这个维基百科条目给你数学。请注意,这里的准确性仍然是一个问题......

您没有非常昂贵的计算,但计算准确的平方根并不是免费的,对于 N 边多边形,您必须最多执行 N 次。

做得比那更好(即变得比 更好O(N))将是困难的。但是,如果多边形是固定的,并且您要针对它测试大量点,那么您可以考虑使用预先计算的四叉树数据结构来进行解析。预先计算四叉树会很昂贵,但如果 N 足够大,测试一个点会更便宜。(大致O(log(1/epsilon))是在最坏的情况下,而不是O(N)平均情况。一个点离边界越远,答案就越便宜。)

但正如我所说,四叉树只会在有限的情况下有所帮助......

于 2012-11-27T03:39:50.487 回答
1

您可以使用描边路径。BasicStroke有方法

public Shape createStrokedShape(Shape s)

所以只需定义粗线BasicStroke,获取描边形状并检查描边是否Shape包含您的点。

于 2012-11-27T06:39:22.003 回答