使用 Python 获取畅通区域
Using Python to get unblocked area
我有一个比较复杂的问题。假设我有下面的形状。您可以将红点想象成一个人，将大多边形内的尖头形状想象成障碍物。我的目标是计算大多边形内的人的总视野，即多边形面积减去红色阴影面积。
我想写一个函数，它接收人的坐标、障碍物的有序顶点坐标和大多边形的有序顶点坐标，以及 returns畅通无阻的视野区域。
我尝试了很多东西，我知道鞋带算法，但我能想出的唯一方法是通过 monte carlo。我能否获得有关以封闭形式计算面积的更智能和有效方法的提示？
第一个任务是获取人的两个极端视线。
一个简单的暴力检查。我怀疑是否有更好的方法，除非您需要在每一帧进行这种计算。 （见下文 (a)）。
计算每个顶点的线 person-to-obstacle_vertex 的角度（相对于 X 轴或其他）。
找出最低值和最高值。如果障碍物可能以某种方式绕着人弯曲，这可能会很棘手。
所以你可以计算每对视线的角度（组合问题），并得到最大角度。对于此作业，请使用点积。
第二个任务是获取阴影区域的面积。
你需要得到视线和外多边形的两个交点。然后建立两个交叉点之间的多边形顶点列表。将这些交叉点添加到该列表中。
面积可以计算为三角形面积的总和，即从人到每条边（该列表中的两个点）的面积。虽然您拥有所有坐标，但更简单的方法是使用鞋带算法。
(a) 如果障碍物有数千个顶点并且人连续移动，我会尝试减少要检查的对数。你可以维护一个 shown/hidden 顶点列表，当人移动时检查最后两个使用的顶点和它们的邻居，直到你得到一对新的结束顶点。
我认为找到 "Visibility polygon" 即可解决您的问题。
https://en.wikipedia.org/wiki/Visibility_polygon
您可以使用 https://karlobermeyer.github.io/VisiLibity1/ 库来计算可见区域。
我有一个比较复杂的问题。假设我有下面的形状。您可以将红点想象成一个人，将大多边形内的尖头形状想象成障碍物。我的目标是计算大多边形内的人的总视野，即多边形面积减去红色阴影面积。
我想写一个函数，它接收人的坐标、障碍物的有序顶点坐标和大多边形的有序顶点坐标，以及 returns畅通无阻的视野区域。
我尝试了很多东西，我知道鞋带算法，但我能想出的唯一方法是通过 monte carlo。我能否获得有关以封闭形式计算面积的更智能和有效方法的提示？
第一个任务是获取人的两个极端视线。
一个简单的暴力检查。我怀疑是否有更好的方法，除非您需要在每一帧进行这种计算。 （见下文 (a)）。
计算每个顶点的线 person-to-obstacle_vertex 的角度（相对于 X 轴或其他）。
找出最低值和最高值。如果障碍物可能以某种方式绕着人弯曲，这可能会很棘手。
所以你可以计算每对视线的角度（组合问题），并得到最大角度。对于此作业，请使用点积。
第二个任务是获取阴影区域的面积。
你需要得到视线和外多边形的两个交点。然后建立两个交叉点之间的多边形顶点列表。将这些交叉点添加到该列表中。
面积可以计算为三角形面积的总和，即从人到每条边（该列表中的两个点）的面积。虽然您拥有所有坐标，但更简单的方法是使用鞋带算法。
(a) 如果障碍物有数千个顶点并且人连续移动，我会尝试减少要检查的对数。你可以维护一个 shown/hidden 顶点列表，当人移动时检查最后两个使用的顶点和它们的邻居，直到你得到一对新的结束顶点。
我认为找到 "Visibility polygon" 即可解决您的问题。 https://en.wikipedia.org/wiki/Visibility_polygon
您可以使用 https://karlobermeyer.github.io/VisiLibity1/ 库来计算可见区域。