6

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.

Sample Result

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.

Battleroid
  • 861
  • 2
  • 14
  • 30
  • Have you tried any existing libraries to do the job? Maybe something like this: https://code.google.com/archive/p/straightedge/. The task you are solving is relatively complex, and may require a lot of effort, so, unless you are doing it for research purposes, I would suggest you to find something that already does that. – user3707125 Feb 01 '16 at 01:53
  • I'd like to refrain from using existing implementations as this is a portion of a project due in a week unfortunately. This is neat though. – Battleroid Feb 01 '16 at 02:07
  • It's not JavaFX, but the classes that are used there (`Line2D` etc) exist in both APIs, and it's a MCVE with some debugging options (e.g. the option to paint all scanlines) : http://stackoverflow.com/a/23971327/3182664 – Marco13 Feb 15 '16 at 14:30

2 Answers2

5

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:

enter image description here

with the scanlines (blue) visible:

enter image description here

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.

Roland
  • 18,114
  • 12
  • 62
  • 93
  • The fixed scan line count (and thus, a fixed angle between them) may cause problems. For objects in larger distance, sampling errors may appear. Depending on the number of obstacles, there is an alternative: You can create scanlines by taking the lines from the center to all line endpoints, and rotate them by a small "epsilon" in both directions. This may still seem a bit crude, but I used it in http://stackoverflow.com/a/23971327/3182664 and it works quite well. – Marco13 Feb 15 '16 at 14:29
3

This interactive tutorial might be of help:

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

kubuzetto
  • 1,046
  • 1
  • 12
  • 31