"Line of Sight" for a vertex on polygon to all other polygon vertices

Question

I'm having trouble trying to find all vertices on polygons that are visible from a given vertex on a polygon. So far I've had limited success with what I've written.

I can generate the rays to visible vertices, but only if my origin point is not on a vertex using the following:

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.

This is the last approach I've tried. I'm sure this way is horrible, if someone could point me in the right direction so can make it less horrible I'd appreciate it.

Answer 1

That's quite some code you got there to analyze, especially without comments. However, this question made me curious about the topic, so I read a bit about it and toyed around with it using scanlines and a brute-force check against all line segments of the scene. Interesingly it turned out very well and performing. Maybe it helps you to see how I did it:

• create lines (walls) which consist of a start and an end vector (any line with any angle will do)
• create scan lines around the view point
• hit-test the scan lines against all lines in the scene
• for each intersecting point find the one that's closest to the view point
• connect all intersecting points

It was rather easy to do, especially when you use vector calculation.

It looks like this on youtube.

Screenshot:

with the scanlines (blue) visible:

But please bear in mind that this is only brute-force test against all line segments. Of course there's room for optimization like e. g. calculating the distance of all segments against the view point, clipping the segments, etc. Take a look at @kubuzetto's answer.

If this is what you're looking for, you can find the source at this gist. The logic and relevant for you is in Algorithm.java.

Additional info, since your code contains the word "enemyLine" which makes me think you need it for a game: When you simply sum up all your intersection points and divide them by the number of scanlines and move to the target, you'll automatically get movement like this.

Answer 2

This interactive tutorial might be of help:

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