0

这是一个很难用语言解释的问题，尽管我很容易在脑海中捕捉到它。如果我在下面的解释不清楚，请告诉我。

假设用户正在二维表面上绘图。他们正在用鼠标或手写笔绘制曲线。只是为了清楚定义，我会说曲线由起点（最初放下触控笔的点）、中间点（触控笔拖过的点）和终点组成（最后一点，用户将触控笔从表面抬起）。

如何检测用户曲线是否创建了一些封闭的形状？ 例如，如果你模糊你的眼睛并看下面的图（'.' 表示曲线上的点，'0' 表示不在曲线上的点），第一个确实创建了一个封闭的空间，第二个没有.

0000000000000000
0000..0000000000
000.00.000000000
00.000.000000000
00.00.0000000000
000...0000000000
0000000000000000

000.000000000000
0000.00000000000
00000.0000000000
00000...00000000
0000000.00000000
00000000.0000000
0000000000000000

此外，给定某个点 (x1,y1)，我如何确定该点是在封闭空间的内部还是外部？

4

3 回答 3

1

对于你的第二个问题：

经典的方法是从 x1,y1 画一条线到屏幕的边缘，看看这条线有多少次与你的多边形相交。如果数字是奇数，它在形状内，如果它是偶数，那么它在外面。方法和单点边缘存在问题，但我相信您可以在线找到解决方案/修复。

于 2010-12-06T21:35:53.833 回答
1

我给 Assaf +1，但另一种方法是做一些填充，然后检查是否有任何点留在原来的颜色。计算线交叉对于矢量图可能更容易 - 洪水填充方法可能更适用于位图图形。

于 2010-12-06T21:51:06.580 回答
0

1）要检测路径是否形成循环，您可以将点转换为图形。您需要定义自己的启发式方法来确定哪些点由边连接（例如，所有相邻点都可以定义为由边连接。或者，如果您的点按特定顺序生成，则连续点可以通过边缘连接）。一旦你有了你的图表，你可以用谷歌搜索循环检测算法，看看它是否会产生循环。

2）要确定哪些点是封闭的，您可以获取构成循环的点并使用它们来定义多边形。然后谷歌搜索“多边形中的点”算法并测试一定范围内的所有点。

于 2010-12-06T21:30:17.837 回答