algorithm - 如何确定 2D 中的可见性

Question

我正在开发一个 AI 沙箱，我想计算每个生物体可以看到的内容。

规则是从实体的角度简单地隐藏形状边缘后面的内容。图片说明一切:

alt text http://img231.imageshack.us/img231/2972/shadows.png

我需要它作为人工智能的输入，或者以图形方式在它移动时为特定实体显示它......

有什么好点子吗？

Answer 1

这不是最快的算法，但它会生成一个多边形，可能对您的 AI 的进一步分析有用:

1. 对于每条线段，计算实体与两个端点之间的角度。
2. 按角度对点进行排序。
3. 围绕 360°“扫描”，跟踪哪些线段与扫描线相交。当您越过段的起点时，将该段添加到集合中；当您越过段结束点时，您将从集合中删除该段。
4. 最近的线段形成一个可见的多边形。多边形是三角形 strip 的并集。

我知道这个解释不是很好，但我有 an online demo here你可以玩它来了解它是如何工作的。将其扩展到与圆圈一起使用可能还不错(著名的遗言)。