3D-Geometrie: Alle Punkte effizient bestimmen, die in einem Kegel liegen

[CyborgBeta]

Habs herausgefunden. Durch den double threshold = a.distance(b) * Math.cos(Math.toRadians(Math.PI / 4 * angle_deg)); wird eine Parabel gebildet, die schon vor B anfängt:

Das ist hier angedeutet durch den in Rot markierten Bereich.

Punkte: A=(500,500) und B=(750,500).

Ich muss also den Threshold anpassen, sodass sich ein Kegel ergibt.

Eine Parabel hat ja die Form: a² + b.

Eine Gerade hätte die Form: a x b + c.

Ich muss also irgendwie von dem Hoch 2 wegkommen.

 

[CyborgBeta]

Ich bin jetzt ganz verwirrt ... So würde die Form stimmen (spitzer Kegel anstatt Parabel), aber nur, wenn alle Punkte genau auf der x-Achse liegen ...

    private static List<Point2D> getPointsInCone(Point2D[] pa, double angle_deg) {
        Point2D a = pa[0];
        Point2D b = pa[1];
        double dist_a_b = a.distance(b);
        List<Point2D> points = new ArrayList<>();
        for (int i = 2; i < pa.length; i++) {
            Point2D c = pa[i];
            double dist_a_c = a.distance(c);
            double dist_b_c = b.distance(c);
            double tan1 = Math.tan(Math.toRadians(angle_deg));
            double tan2 = Math.tan(Math.toRadians(-angle_deg));
            double y = (c.getY() - b.getY()) / (c.getX() - b.getX());
            if (dist_a_c > dist_a_b && y < tan1 && y > tan2) {
                points.add(c);
            }
        }
        return points;
    }

tan entspricht der Steigung von 20° (von angle_deg).

y entspricht der Steigung von der Grade durch B und C.

Kann mich bitte jemand erleuchten?

 

[simpsonsfan]

Kann mich bitte jemand erleuchten?

Du vergisst die Projektion in ein lokales, durch A und B definiertes, Koordinatensystem.
D.h. dein jetziger Code funktioniert dann wenn A_y = B_y und B_x > A_x (weil dein globales Koordinatensystem dann gerade die Richtung des lokalen hat.)
Zur Projektion eines Vektors auf einen anderen nimmt man üblicherweise das Skalarprodukt.

Hast recht, aber bitte dann auch richtige Werte verwenden:

Hast mich erwischt. Statt:

[...] weil 99,2/100>cos(7,58°) ist.

muss es natürlich

[...] weil 99,2/100>cos(7,85°) ist.

heißen. Verflixte Zahlendreher.

 

[CyborgBeta]

Perfekt! Jetzt geht es, ist genau und schnell !!!

    private static List<Point2D> getPointsInCone(Point2D[] pa, double angle_deg) {
        double tan1 = Math.tan(Math.toRadians(angle_deg));
        Point2D a = pa[0];
        Point2D b = pa[1];
        double m_a_b = Math.atan2(b.getY() - a.getY(), b.getX() - a.getX());
        List<Point2D> points = new ArrayList<>();
        for (int i = 2; i < pa.length; i++) {
            Point2D c = pa[i];
            double m_b_c = Math.atan2(c.getY() - b.getY(), c.getX() - b.getX());
            if (Math.abs(m_a_b - m_b_c) < tan1) {
                points.add(c);
            }
        }
        return points;
    }

Eigentlich simple, aber man braucht ein Grundverständnis dafür ...

Nun kann das Thema ad acta gelegt werden.

PS. Ich habe nicht die KI gefragt. 😬

Ergänzung (30. März 2025)

Und in 3D ginge der Spaß auch genau so

https://stackoverflow.com/questions/21483999/using-atan2-to-find-angle-between-two-vectors

 

[simpsonsfan]

Allerdings wird dir das Ding durch die Unstetigkeit von atan2 fehlschlagen, wenn B nahe 180° und C nahe -180° liegt. Den Punkt H hast du in deiner Animation gerade verfehlt, der könnte bspw. ebenfalls fälschlich nicht erkannt werden.
Und ich wüsste ja mal gerne, was genau du vor hast, im 3D als Argumente für atan2 anzugeben. Denn dann muss man eben wieder vorher die Ebene, die durch A, B und C aufgespannt wird bestimmen und entsprechend die Koordinaten darin angeben. Aber ja, im Prinzip gilt "the extension to 3D is straightforward."

Generell empfinde ich lineare Algebra eigentlich als ein sehr anschaubares Feld. Aber klar, ein Grundverständnis sollte man dafür aufbauen, dann weiß man auch, was die grundlegenden Dinge sind, die dann auch in einem beliebigen R^n funktionieren.

 

[CyborgBeta]

@simpsonsfan https://stackoverflow.com/a/32724066:

Das müsste es doch im Prinzip sein.

Und ich wüsste ja mal gerne, was genau du vor hast,

Wie gesagt, eigentlich möchte ich nur den Reiseweg in einem Spiel berechnen.

 

[simpsonsfan]

Du hast von Post 1 an davon geredet, dass das Ganze möglichst effizient sein soll.
Die naheliehenste und einfachste Methode dazu ist eben wirklich, direkt das Skalarprodukt (englisch auch dot product) herzzunehmen, wie bereits in Post #5 vorgeschlagen wurde.

Die Variante, atan2 mit Kreuzprodukt und Skalarprodukt als Argmunten aufzurufen, könnte* grundlegend funktionieren, ist aufwändiger und hat ein Problem an der Unstetigkeit. Ist also objektiv in den meisten Belangen schlechter. Und besser lesbar ist es mMn auch nicht.
Da drängt sich einfach die Frage auf, warum man das hier in diesem Fall tun sollte.

*Obwohl, wie in auch in dem stackoverflow Thread angemerkt, ein positives y-Argument für atan2 lediglich Winkel im Bereich 0 bis Pi erlaubt. Benötigt also nochmal mehr Sonderfälle.