java - "Línea de visión" para un vértice en el polígono a todos los demás vértices poligonales

javafx geometry

Question

Tengo problemas para encontrar todos los vértices en polígonos visibles desde un vértice dado en un polígono. Hasta ahora he tenido un éxito limitado con lo que he escrito.

Puedo generar los rayos en vértices visibles, pero solo si mi punto de origen no está en un vértice usando lo siguiente:

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

El código completo aquí, por favor no te rías.

Este es el último enfoque que he probado. Estoy seguro de que este camino es horrible, si alguien pudiera señalarme en la dirección correcta para que sea menos horrible, lo agradecería.

Answer 1

Este tutorial interactivo puede ser de ayuda:

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

Answer 2

Es todo un código que tienes que analizar, especialmente sin comentarios. Sin embargo, esta pregunta me hizo sentir curiosidad sobre el tema, así que leí un poco al respecto y jugué con ella utilizando líneas de exploración y una verificación de fuerza bruta contra todos los segmentos de línea de la escena. Curiosamente, resultó muy bien y funcionó. Tal vez te ayude a ver cómo lo hice:

• crea líneas (paredes) que consisten en un inicio y un vector final (cualquier línea con cualquier ángulo servirá)
• crear líneas de escaneo alrededor del punto de vista
• prueba las líneas de escaneo contra todas las líneas de la escena
• para cada punto de intersección, encuentre el más cercano al punto de vista
• conectar todos los puntos de intersección

Fue bastante fácil de hacer, especialmente cuando usa el cálculo vectorial.

Se ve así en youtube .

Captura de pantalla:

con las líneas de exploración (azul) visibles:

Pero tenga en cuenta que esta es solo una prueba de fuerza bruta contra todos los segmentos de línea. Por supuesto, hay espacio para la optimización, como por ejemplo, calcular la distancia de todos los segmentos frente al punto de vista, recortar los segmentos, etc. Eche un vistazo a la respuesta de @ kubuzetto.

Si esto es lo que estás buscando, puedes encontrar la fuente en este momento . La lógica y relevante para usted está en Algorithm.java.

Información adicional, ya que su código contiene la palabra "enemyLine" que me hace pensar que lo necesita para un juego: cuando simplemente suma todos los puntos de intersección y los divide por el número de líneas de exploración y se mueve al objetivo, automáticamente obtener movimiento como este .