java - "Line of Sight"多边形上的顶点到所有其他多边形顶点

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;
}

Full code here, please don't laugh.

这是我尝试过的最后一种方法。我敢肯定这种方式很糟糕，如果有人能为我指出正确的方向，那么我将不胜感激。

Answer 1

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

• 创建由起始 vector 和结束 vector 组成的线(墙)(任何角度的线都可以)
• 围绕视点创建扫描线
• 针对场景中的所有线对扫描线进行 HitTest
• 对于每个相交点，找到最接近视点的那个
• 连接所有相交点

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

看起来like this on youtube .

截图:

扫描线(蓝色)可见:

但请记住，这只是针对所有线段的暴力测试。当然还有像e这样的优化空间。 G。计算所有线段相对于视点的距离，剪裁线段等。看看@kubuzetto 的回答。

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

附加信息，因为你的代码包含单词“enemyLine”，这让我觉得你需要它来玩游戏:当你简单地总结所有的交点并将它们除以扫描线的数量并移动到目标时，你会自动获得类似 this 的运动.