java - 确定线是否完全在path2d形状内(在java中)

Question

我正在寻找最简单/最快(计算上)的方法来确定形状(更具体地说是 GeneralPath 对象)是否包含任何给定的线段(类型为 Line2D.Double)。

GeneralPath 有方法来确定是否包含点或矩形，但不包含一条线(我可以找到)。该线可能是倾斜的，所以我不能只建模一个非常薄的矩形。线上的一个点肯定会在形状内部，但我需要检查线段的其余部分。因此，我还可以检查该线是否与任何边界边缘相交，但我不确定在给定形状和线的情况下它看起来会如何。

Answer 1

您的 GeneralPath 是否包含直线段或二次或贝塞尔曲线段？这很重要。直线的算法是最简单的:

迭代路径中的所有点。如果两个连续点位于该线的相对两侧，则可能存在交叉点。然后，您需要检查线段端点相对于潜在交叉点是否位于形状内部或外部，这是通过求解两点(直线和由两个连续点形成的直线)的交点并查看是否获得的结果包含在您的线段中。

不幸的是，弯曲路径可以有两个连续的点，它们之间有一个括号形状“)”，您的线可以穿过它们，同时仍将可迭代点保持在同一侧。如果您可以获得具有两个端点和一个(双)控制点的格式，形成一个边界三角形(四边形)，您可以获得简单的解决方案(因为保证曲线适合形成的三角形/四边形内部)通过三/四个点，只要线不与三角形/四边形相交，就可以了)。不幸的是，这也有一个丑陋的部分 - 如果直线确实与三角形/四边形相交，则无法保证任何结果，并且必须仔细检查。作为一个双重不幸，除了归一化坐标系和求解零之外，我不知道其他技术。这是我在书中查找的东西，但我似乎找不到(或者等到另一张漂亮的 SO 海报出现)。

...实际上，由于形状的曲率属性在旋转下是不变的，对于更仔细的检查部分，您只需旋转曲线点(无论是3还是4)即可轴对齐。然后做你的瘦长方形技巧。这可能不是最干净的，但却是最明显的技巧。

想一想，为什么不首先对所有点进行旋转呢？整个相交问题是旋转不变的。这将节省大量代码。只需将线轴对齐，将变换应用于形状，然后执行您厚颜无耻的矩形技巧。