"视线",用于多边形上的顶点到所有其他多边形顶点

Question

我无法在多边形上找到从多边形上的给定顶点可见的多边形上的所有顶点.到目前为止,我用我所写的内容取得了有限的成功.

我可以将光线生成到可见顶点,但仅当我的原点不在顶点上时使用以下内容:

private ArrayList<Polyline> getGloballyVisible(Point2D origin, ArrayList<Polygon> polys) {
    ArrayList<Polyline> visible = new ArrayList<>();

    for (Polygon target : polys) {
        ArrayList<Polyline> targetVisibleLines = getVisiblePointsOnPolygon(origin, target);
        ArrayList<Polygon> subTargetPolygons = new ArrayList<>(polys);
        subTargetPolygons.remove(target);
        ArrayList<Polyline> subTargetEdges = getEdges(subTargetPolygons);

        lineCheck: for (Polyline line : targetVisibleLines) {
            for (Polyline enemyLine : subTargetEdges) {
                ArrayList<Point2D> linePoints = toPoints(line.getPoints());
                ArrayList<Point2D> enemyLinePoints = toPoints(enemyLine.getPoints());
                if (linesIntersect(linePoints.get(0), linePoints.get(1), enemyLinePoints.get(0), enemyLinePoints.get(1))) {
                    continue lineCheck;
                }
            }
            visible.add(line);
        }
    }
    return visible;
}

完整的代码在这里,请不要笑.

这是我尝试过的最后一种方法.我确信这种方式很可怕,如果有人能指出我正确的方向,那么可以让它变得不那么可怕我会欣赏它.

Answer 1

这是您要分析的相当多的代码，尤其是没有注释的代码。然而，这个问题让我对这个话题感到好奇，所以我阅读了一些关于它的内容，并使用扫描线和对场景所有线段的蛮力检查来玩弄它。有趣的是，结果非常好，表现也很好。也许它可以帮助您了解我是如何做到的：

• 创建由起点和终点向量组成的线（墙）（任何角度的线都可以）
• 在视点周围创建扫描线
• 针对场景中的所有线对扫描线进行命中测试
• 对于每个相交点，找到最接近视点的那个
• 连接所有相交点

这很容易做到，尤其是当您使用矢量计算时。

在 youtube 上看起来是这样的。

截屏：

扫描线（蓝色）可见：

但请记住，这只是针对所有线段的蛮力测试。当然，还有优化的空间，例如计算所有段与视点的距离、剪辑段等。看看@kubuzetto 的答案。

如果这是您要查找的内容，您可以在此 gist 中找到来源。与您相关的逻辑在 Algorithm.java 中。

附加信息，因为您的代码包含“enemyLine”这个词，这让我觉得您在游戏中需要它：当您简单地总结所有交叉点并将它们除以扫描线的数量并移动到目标时，您将自动像这样得到运动。

Answer 2

这个交互式教程可能会有所帮助：

http://www.redblobgames.com/articles/visibility/