边界内还是边界外？如何发现？

havano · 发表于 2006-6-3 19:38:08

让我们假设你有一个绘图层，它有一堆闭合的(有时是部分重叠的)实体，如闭合的2D折线、圆弧等。现在，您要找出给定的XY坐标是否在至少一个绘图图元的包围区内。
你们中有谁能想出一种方法来执行此任务(这种方法将在大量坐标中重复，因此最好是快速的)？

本帖以下内容被隐藏保护；需要你回复后，才能看到！

游客，如果您要查看本帖隐藏内容请回复

Bryco · 发表于 2006-6-4 11:05:44

请参阅http://softsurfer.com/Archive/algorithm_0103/algorithm_0103.htm，以获得不使用射线方法的充分理由。公式包含在C++中，因此转换并不总是那么简单。

havano · 发表于 2006-6-4 12:12:33

谢谢布莱科。我想到了一种射线法。首先，找到图层上所有几何体的边界框，然后，用水平/垂直线或光线扫描此边界框区域，并使用intersectwith查找几何体边界的位置。当然可以使用这种方法，但速度很慢。当扫描射线击中实体的边缘并因此仅返回一次命中（或奇数次命中）时。

DaveW · 发表于 2006-6-6 20:45:34

仅供参考，
我在编码方面有点笨拙……好吧，一个非常糟糕的黑客，但无论如何，我也遇到过类似的问题
在处理复杂的展开三维实体时，我发现了一种解决方案：
获取底部区域
在xy平面上多次剖切实体
向下移动所有区域
，将它们全部合并
分解新区域
运行pedit

MickD · 发表于 2006-6-6 20:58:06

对algo的一个非常基本的描述，但您也可以尝试循环通过每个多边形边，计算该点是在左侧（-）还是右侧（+）
如果您的闭合多边形环是顺时针的，并且您的点“在”内部，则所有检查都将返回正数
对于边缘上或非常接近边缘的点，这也需要模糊因子。该算法也适用于凹多边形
另一种选择是使用托管包装器并使用内置有这些函数的几何体类（想到曲面）。