矢量绘图应用程序如何做到这一点？

在Illustrator中，您可以拖动一个矩形并选择其中的所有对象。它超越了边界框测试，因为它确保了它触及多边形的实际部分。那么它如何有效地做到这一点？如果要检查是否多边形P的任何部分是一个矩形R内（AC或C++实现将是优选的）矢量绘图应用程序如何做到这一点？

由于

来源

2010-08-11 jmasterx

它是否选择完全在矩形内的所有对象？如果是这样，那么你可以快速修剪二维“质心”或任何你认为是中心的东西，我想。虽然我不完全明白这个问题。看起来像一个边界框仍然可以提供帮助。此外，有多少物体应该足够快地工作？它可以限制在100,1000,10000等还是没有限制？ – 2010-08-11 02:31:35

请您详细说明一下，输入和输出是什么？另外，'ensres'是什么意思？ – 2010-08-11 02:32:16

输入=矩形和封闭曲线列表。输出=与矩形相交的曲线。 Ensres =确保。 – Potatoswatter 2010-08-11 02:34:45

，则可以做到这一点：

如果任何顶点的P在R内，则返回TRUE;
如果R的任何顶点都在P之内，则返回TRUE;
如果P（相邻顶点之间的线）的任何边与R的边相交，则返回TRUE。
否则，返回FALSE。

来源

2010-08-11 02:42:00 caf

这看起来像一个函数？谢谢 – jmasterx 2010-08-11 02:46:18

@Jex：那么，你将需要的基元是一个点包围盒测试和一个线段相交测试（第一个是简单的，第二个很容易搜索）。测试一个点是否位于多边形内是最难的部分 - 一种方法是测试从多边形的点到边界框的一条直线与多边形的边缘交叉偶数次还是奇数次。 – caf 2010-08-11 02:53:15

我在聚一个点，并指向矩形一，我想所有剩下的就是找到一个交点。谢谢 – jmasterx 2010-08-11 02:59:42

您也可以只是构造矩形与对象的交集（像Illustrator这样的程序已经有很多其他用途的函数）并检查它是否为非空。更高效的算法可用（请参阅caf的答案），但我的优点是不需要额外的代码。

来源

2010-08-11 05:50:56

矢量绘图应用程序如何做到这一点？

回答

相关问题