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

[CyborgBeta]

Hallo, ich habe eine Liste mit 3-Punkten (hier sind es zur Vereinfachung nur 26).

Ich möchte nun alle Punkte bestimmen, die in einem bestimmten Kegel liegen.

Dabei beginnt der Kegel mit dem Punkt (AB) und ist nach "links" und nach "rechts" um 10 Grad geöffnet. Der Punkt A stellt dabei immer den Ursprung dar.

Man könnte sich das so vorstellen (zur Vereinfachung nur eine 2D-Zeichnung (und ohne Kantenglättung )):

Gesucht wären hier die Punkte D, G und P.

Gesucht wäre hier der Punkt M.

Es gibt dabei doch bestimmt einen Trick, sodass man zu allen Punkten jeweils nur die Entfernung zu A und B bestimmen muss, oder? Aber wie lautet die Formel?

 

[dms]

Servus,

A) welches deiner Probleme soll denn heute gelöst werden/was wird denn heut wieder ausgesourct
- gibt es etwas Kontext

B) gibts die Kordinaten auch als Daten....?

C) du willst ja nicht eine Lösung sondern eine "effiziente" .. wie sieht denn deine Lösung aus

D.

Die Suchmaschine meine Wahl würde ich so befragen: befindet sich ein Punkt im Volumen eines Körpers
oder zB Wolfram Alpha

Ergänzung (28. März 2025)

Nachtrag ... ich würde das mit Blender machen - und in den Kegel "schauen"

 

[Krik]

Rechnerisch ist das gar nicht so schwer und ist mit der Trigonometrie und Matrizenrechnung aus der Schule machbar.

Zuerst bestimmt man den Abstand der Punkte von der Rotationsachse des Kegels. Da man hier ein senkrechtes Lot auf die Achse fällt, kann man am Schnittpunkt auch bestimmen, wie groß der Kegelradius ist. Und ist der Radius größer als der Abstand zwischen Punkt und Lotpunkt auf der Rotationsachse, dann befindet sich der Punkt innerhalb des Kegels.

Das ist alles eine Kleinigkeit für eine CPU und bei der GPU schon quasi in Hardware gegossen.

 

[CyborgBeta]

@dms Guten Tag, nun sei nicht so zickig ...

Daten:

A=(500, 500)
B=(450, 475)
C=(560, 360)
D=(410, 750)
E=(520, 420)
F=(520, 520)
G=(220, 550)
H=(240, 540)
I=(370, 760)
J=(200, 440)
K=(360, 440)
L=(390, 260)
M=(790, 630)
N=(280, 730)
O=(640, 280)
P=(660, 310)
Q=(640, 760)
R=(300, 300)
S=(280, 630)
T=(230, 220)
U=(590, 340)
V=(350, 310)
W=(710, 400)
X=(310, 290)
Y=(760, 590)
Z=(350, 540)

Gesucht wäre hier nur K.

Aber wie gesagt, das Ganze mit 3D-Koordinaten.

Ergänzung (28. März 2025)

Es geht um ein Weltraum-Spiel, in dem man von Punkt zu Punkt reisen kann, und ich möchte mich in eine feste Richtung vom Ursprung entfernen ... Dabei liegen die infrage kommenden Punkte natürlich nicht genau auf dieser Linie.

 

[Wo bin ich hier]

Hast du schon mal die KI deines Vertrauens gefragt?
ChatGPT spuckt Folgendes aus:

import numpy as np

def is_in_cone(P, A, B, angle_deg):
    v = B - A
    u = P - A

    norm_v = np.linalg.norm(v)
    norm_u = np.linalg.norm(u)

    if norm_u == 0:
        # Punkt P ist identisch mit A → liegt im Kegel
        return True

    cos_theta = np.dot(v, u) / (norm_v * norm_u)
    return cos_theta >= np.cos(np.radians(angle_deg))

# Punkt A: Ursprung des Kegels
A = np.array([0, 0, 0])

# Punkt B: Richtung des Kegels
B = np.array([1, 0, 0])  # Kegel zeigt in x-Richtung

# Kegelöffnung (halber Öffnungswinkel)
angle = 10  # Grad

# 26 Beispielpunkte (Punkte "A" bis "Z")
punkte = [
    np.array([1, 0, 0]),    # direkt auf der Achse
    np.array([2, 0.1, 0]),  # nahe an der Achse
    np.array([2, 0.5, 0]),
    np.array([2, 1, 0]),
    np.array([2, -0.2, 0]),
    np.array([2, -1, 0]),
    np.array([3, 0.5, 0.1]),
    np.array([3, -0.5, -0.1]),
    np.array([3, 1, 1]),
    np.array([1, 1, 1]),
    np.array([1, -1, -1]),
    np.array([0.5, 0.1, 0]),
    np.array([0.5, 1, 0]),
    np.array([-1, 0, 0]),     # hinter dem Ursprung
    np.array([-2, 1, 0]),
    np.array([0, 0, 0]),      # exakt der Ursprung
    np.array([4, 0.2, 0]),
    np.array([4, 2, 0]),
    np.array([4, 0.05, 0]),
    np.array([5, 0.3, 0.2]),
    np.array([5, 1, 1]),
    np.array([5, -0.2, -0.2]),
    np.array([3, 0, 0]),
    np.array([3, 0.1, 0]),
    np.array([3, -0.1, 0]),
    np.array([2, 0.2, 0]),
]

# Punkte im Kegel
punkte_im_kegel = [P for P in punkte if is_in_cone(P, A, B, angle)]
print(punkte_im_kegel)

 

[CyborgBeta]

Danke @Wo bin ich hier , aber ich habe eine einfachere Möglichkeit gefunden, um es zu bestimmen:

    private static TreeMap<Double, String> getPointsInCone(Point2D[] pa) {
        Point2D a = pa[0];
        Point2D b = pa[1];
        double dist_a_b = a.distance(b);
        double threshold = dist_a_b * 1.99;
        System.out.println("threshold = " + threshold);
        TreeMap<Double, String> points = new TreeMap<>(Comparator.reverseOrder());
        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 key = dist_a_b + dist_a_c - dist_b_c;
            if (key >= threshold) {
                points.put(key, String.format("%s=(%d, %d)", (char) ('A' + i), (int) c.getX(), (int) c.getY()));
            }
        }
        return points;
    }

Was mich verwirrt, ist der Threshold-Faktor 1,99 ... Bei meinen bisherigen Versuchen funktionierte es immer, aber ich bräuchte einen Beweis, dass die Methode wirklich immer das richtige Ergebnis zurückgibt ...

Ihr könnt das auch gerne selber mal ausführen, einfach den Seed in Zeile 11 (Random r = new Random(5);) anpassen, wenn andere Beispiele gewünscht sind:

import javax.swing.*;
import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;

public class Cone {
    public static void main(String[] args) {
        Point2D[] pa = new Point2D[26];
        pa[0] = new Point2D.Double(500, 500);
        //pa[1] = new Point2D.Double(450, 475);
        Random r = new Random(5);
        for (int i = 1; i < 26; i++) {
            int x = r.nextInt(61) * 10 + 200;
            int y = r.nextInt(61) * 10 + 200;
            pa[i] = new Point2D.Double(x, y);
        }
        for (int i = 0; i < pa.length; i++) {
            Point2D p = pa[i];
            System.out.printf("%s=(%d, %d)%n", (char) ('A' + i), (int) p.getX(), (int) p.getY());
        }
        Canvas c = new Canvas() {
            @Override
            public void paint(Graphics g) {
                Point2D a = pa[0];
                Point2D b = pa[1];
                Point2D c = getEndpointC(a, b, 350);
                Point2D d = rotateEndpointC(b, c, Math.toRadians(10));
                Point2D e = rotateEndpointC(b, c, Math.toRadians(-10));

                g.setColor(Color.YELLOW);
                g.fillPolygon(new int[]{(int) b.getX(), (int) d.getX(), (int) e.getX()}, new int[]{(int) b.getY(), (int) d.getY(), (int) e.getY()}, 3);
                g.setColor(Color.BLACK);

                g.drawRect(175, 175, 650, 650);

                g.drawLine((int) a.getX(), (int) a.getY(), (int) b.getX(), (int) b.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) c.getX(), (int) c.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) d.getX(), (int) d.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) e.getX(), (int) e.getY());

                g.setColor(Color.BLACK);
                for (int i = 0; i < pa.length; i++) {
                    g.fillOval((int) pa[i].getX() - 2, (int) pa[i].getY() - 2, 4, 4);
                    g.drawString("" + (char) ('A' + i), (int) pa[i].getX(), (int) pa[i].getY() + 15);
                }
            }
        };
        JFrame f = new JFrame();
        f.add(c);
        f.setSize(1000, 1000);
        f.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
        f.setVisible(true);

        for (Map.Entry<Double, String> e : getPointsInCone(pa).entrySet()) {
            System.out.println(e);
        }
    }

    private static Point2D getEndpointC(Point2D a, Point2D b, int length) {
        Point2D a_b = new Point2D.Double((b.getX() - 500) - (a.getX() - 500), (500 - b.getY()) + (500 - a.getY()));
        double len_a_b = Math.sqrt(a_b.getX() * a_b.getX() + a_b.getY() * a_b.getY());
        a_b = new Point2D.Double(a_b.getX() / len_a_b, a_b.getY() / len_a_b);
        Point2D c = new Point2D.Double(a_b.getX() * length, a_b.getY() * length);
        return new Point2D.Double((b.getX() - 500) + c.getX() + 500, 500 - ((500 - b.getY()) + c.getY()));
    }

    private static Point2D rotateEndpointC(Point2D b, Point2D c, double angle) {
        double x = (c.getX() - 500) - (b.getX() - 500);
        double y = (500 - c.getY()) - (500 - b.getY());
        double xNew = x * Math.cos(angle) - y * Math.sin(angle);
        double yNew = x * Math.sin(angle) + y * Math.cos(angle);
        return new Point2D.Double((b.getX() - 500) + xNew + 500, 500 - ((500 - b.getY()) + yNew));
    }

    private static TreeMap<Double, String> getPointsInCone(Point2D[] pa) {
        Point2D a = pa[0];
        Point2D b = pa[1];
        double dist_a_b = a.distance(b);
        double threshold = dist_a_b * 1.99;
        System.out.println("threshold = " + threshold);
        TreeMap<Double, String> points = new TreeMap<>(Comparator.reverseOrder());
        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 key = dist_a_b + dist_a_c - dist_b_c;
            if (key >= threshold) {
                points.put(key, String.format("%s=(%d, %d)", (char) ('A' + i), (int) c.getX(), (int) c.getY()));
            }
        }
        return points;
    }
}

 

[Krik]

Was mich verwirrt, ist der Threshold-Faktor 1,99 ... Bei meinen bisherigen Versuchen funktionierte es immer, aber ich bräuchte einen Beweis, dass die Methode wirklich immer das richtige Ergebnis zurückgibt ...

Von der magischen Zahl mal abgesehen, raffe ich nicht mal, nach welchem Prinzip er hier bestimmt, was im Kegel liegt oder nicht. Wie soll das funktionieren, wenn man nur ein paar Distanzen addiert und subtrahiert? Wo ist die Trigonometrie? Kann man die ganze Berechnung wirklich auf das bisschen Abstandsberechnung kürzen?


Edit:
Je länger ich darüber nachdenke, desto mehr bin ich davon überzeugt, dass diese Lösung nicht funktionieren kann.
Warum ist die Distanz zum Punkt A wichtig? Wenn ich Post #1 richtig verstanden habe, wird der Punkt nur gebraucht, um zusammen mit Punkt B die Rotationsachse der Kegels zu definieren. Ansonsten ist der Punkt und erst recht seine Distanz zu anderen Punkten völlig egal.

 

[CyborgBeta]

Naja, die Überlegung ist, wenn das Ergebnis von dist_a_b + dist_a_c - dist_b_c größer als ein bestimmter Schwellenwert ist, der Punkt C im Kegel liegen muss...

Nur warum der Schwellenwert anscheinend genau 2x dist_a_b beträgt, ist mir ein Rätsel.

 

[ChristianG.]

Bei einem Schwellenwert von 2 wäre der “Kegel” auf eine Gerade geschrumpft. Es sind wohl eher näherungsweise 1+cos(10°) ;-)

Ich hätte aber direkt dist_a_c - dist_b_c > cos(10°) dist_a_b überprüft. Die Distanz nochmal drauf zu addieren erscheint mir persönlich überflüssig.

 

[CyborgBeta]

Danke an alle und insbesondere an @ChristianG.

Es sind wohl eher näherungsweise 1+cos(10°)

Das war wohl der gordische Knoten ...

    private static List<Point2D> getPointsInCone(Point2D[] pa, double angle) {
        Point2D a = pa[0];
        Point2D b = pa[1];
        double dist_a_b = a.distance(b);
        double threshold = Math.cos(angle) * dist_a_b;
        System.out.println("threshold = " + threshold);
        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 key = dist_a_c - dist_b_c;
            if (key > threshold) {
                points.add(c);
                System.out.printf("%s=(%d, %d) key=%f%n", (char) ('A' + i), (int) c.getX(), (int) c.getY(), key);
            }
        }
        return points;
    }

Wobei hier etwas noch nicht stimmt:

Ich habe den Winkel auf +- 25° geändert, und er sagt jetzt, der Punkt U liege auch in diesem Kegel ...

Hier noch einmal der ganze Code:

import javax.swing.*;
import java.awt.*;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.List;

public class Cone {
    public static void main(String[] args) {
        Point2D[] pa = new Point2D[26];
        pa[0] = new Point2D.Double(500, 500);
        pa[1] = new Point2D.Double(600, 350);
        Random r = new Random(3);
        for (int i = 2; i < 26; i++) {
            int x = r.nextInt(61) * 10 + 200;
            int y = r.nextInt(61) * 10 + 200;
            pa[i] = new Point2D.Double(x, y);
        }
        for (int i = 0; i < pa.length; i++) {
            Point2D p = pa[i];
            System.out.printf("%s=(%d, %d)%n", (char) ('A' + i), (int) p.getX(), (int) p.getY());
        }
        Canvas c = new Canvas() {
            @Override
            public void paint(Graphics g) {
                Point2D a = pa[0];
                Point2D b = pa[1];
                Point2D c = getEndpointC(a, b, 350);
                Point2D d = rotateEndpointC(b, c, Math.toRadians(25));
                Point2D e = rotateEndpointC(b, c, Math.toRadians(-25));

                g.setColor(Color.YELLOW);
                g.fillPolygon(new int[]{(int) b.getX(), (int) d.getX(), (int) e.getX()}, new int[]{(int) b.getY(), (int) d.getY(), (int) e.getY()}, 3);
                g.setColor(Color.BLACK);

                g.drawRect(175, 175, 650, 650);

                g.drawLine((int) a.getX(), (int) a.getY(), (int) b.getX(), (int) b.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) c.getX(), (int) c.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) d.getX(), (int) d.getY());
                g.drawLine((int) b.getX(), (int) b.getY(), (int) e.getX(), (int) e.getY());

                g.setColor(Color.BLACK);
                for (int i = 0; i < pa.length; i++) {
                    g.fillOval((int) pa[i].getX() - 2, (int) pa[i].getY() - 2, 4, 4);
                    g.drawString("" + (char) ('A' + i), (int) pa[i].getX(), (int) pa[i].getY() + 15);
                }
            }
        };
        JFrame f = new JFrame();
        f.add(c);
        f.setSize(1000, 1000);
        f.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
        f.setVisible(true);

        for (Point2D p : getPointsInCone(pa, Math.toRadians(25))) {
            System.out.println(p);
        }
    }

    private static Point2D getEndpointC(Point2D a, Point2D b, int length) {
        Point2D a_b = new Point2D.Double((b.getX() - 500) - (a.getX() - 500), (500 - b.getY()) + (500 - a.getY()));
        double len_a_b = Math.sqrt(a_b.getX() * a_b.getX() + a_b.getY() * a_b.getY());
        a_b = new Point2D.Double(a_b.getX() / len_a_b, a_b.getY() / len_a_b);
        Point2D c = new Point2D.Double(a_b.getX() * length, a_b.getY() * length);
        return new Point2D.Double((b.getX() - 500) + c.getX() + 500, 500 - ((500 - b.getY()) + c.getY()));
    }

    private static Point2D rotateEndpointC(Point2D b, Point2D c, double angle) {
        double x = (c.getX() - 500) - (b.getX() - 500);
        double y = (500 - c.getY()) - (500 - b.getY());
        double xNew = x * Math.cos(angle) - y * Math.sin(angle);
        double yNew = x * Math.sin(angle) + y * Math.cos(angle);
        return new Point2D.Double((b.getX() - 500) + xNew + 500, 500 - ((500 - b.getY()) + yNew));
    }

    private static List<Point2D> getPointsInCone(Point2D[] pa, double angle) {
        Point2D a = pa[0];
        Point2D b = pa[1];
        double dist_a_b = a.distance(b);
        double threshold = Math.cos(angle) * dist_a_b;
        System.out.println("threshold = " + threshold);
        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 key = dist_a_c - dist_b_c;
            if (key > threshold) {
                points.add(c);
                System.out.printf("%s=(%d, %d) key=%f%n", (char) ('A' + i), (int) c.getX(), (int) c.getY(), key);
            }
        }
        return points;
    }
}

und ist mit der Trigonometrie und Matrizenrechnung aus der Schule machbar

Jein, soweit ich mich erinnern kann, sind wir in der Schule nicht so weit gegangen. 😬 Mein Abi liegt aber auch schon etwas zurück und nur GK.

 

[simpsonsfan]

Berechne den Winkel zwischen dem Vektor AB und dem Vektor BC. Ist der Winkel kleiner dem Halbwinkel, dann liegt der Punkt im Kegel.
Auf die Orientierung der Vektoren achten und daran denken, dass ein Nullvektor keine Richtung hat.

Winkel zwischen zwei Vektoren ist ganz einfach mit dem Skalarprodukt zu berechnen.

 

[ChristianG.]

Ich habe den Winkel auf +- 25° geändert, und er sagt jetzt, der Punkt U liege auch in diesem Kegel ...

Ohne es rigoros hergeleitet zu haben, würde ich behaupten, dass in deine Methode die Annahme eingeht, dass dist_a_c >> dist_a_b und dist_b_c >> dist_a_b, also die Vektoren AC und BC ungefähr parallel sind.

Exakter und einfacher empfinde ich auch die Variante von @simpsonsfan, wobei ich die Winkel gar nicht vergleichen würde, sondern direkt den Kosinus.

 

[CyborgBeta]

Inzwischen bin ich mir unsicher, ob es sich nicht einfach nur um Rundungsfehler handelt, oder meine Zeichnung nicht genau ist ... Schade, mir gefiel die Idee, nur zwei Abstände berechnen zu müssen und diese zu vergleichen.

 

[CyborgBeta]

Ich habe des Rätsels Lösung gefunden ...

Der Threshold muss sein: double threshold = a.distance(b) * Math.cos(Math.toRadians(Math.PI / 4 * angle_deg));

import javax.swing.*;
import java.awt.*;
import java.awt.event.MouseEvent;
import java.awt.event.MouseMotionAdapter;
import java.awt.geom.Point2D;
import java.util.*;
import java.util.List;
import java.util.Timer;

public class Cone {
private static final int angeles_deg = 10;

public static void main(String[] args) {
Point2D[] pa = new Point2D[26];
pa[0] = new Point2D.Double(500, 500);
pa[1] = new Point2D.Double(500, 600);
Random r = new Random(4);
for (int i = 2; i < 26; i++) {
int x = r.nextInt(61) * 10 + 200;
int y = r.nextInt(61) * 10 + 200;
pa[i] = new Point2D.Double(x, y);
        }
for (int i = 0; i < pa.length; i++) {
            Point2D p = pa[i];
System.out.printf("%s=(%d, %d)%n", (char) ('A' + i), (int) p.getX(), (int) p.getY());
        }
JPanel c = new JPanel() {
@Override
            public void paintComponent(Graphics g) {
g.clearRect(0, 0, 1000, 1000);

Point2D a = pa[0];
Point2D b = pa[1];
Point2D c = getEndpointC(a, b, 350);
Point2D d = rotateEndpointC(b, c, Math.toRadians(angeles_deg));
Point2D e = rotateEndpointC(b, c, Math.toRadians(-angeles_deg));

g.setColor(Color.YELLOW);
g.fillPolygon(new int[]{(int) b.getX(), (int) d.getX(), (int) e.getX()}, new int[]{(int) b.getY(), (int) d.getY(), (int) e.getY()}, 3);
g.setColor(Color.BLACK);

g.drawRect(175, 175, 650, 650);

g.drawLine((int) a.getX(), (int) a.getY(), (int) b.getX(), (int) b.getY());
g.drawLine((int) b.getX(), (int) b.getY(), (int) c.getX(), (int) c.getY());
g.drawLine((int) b.getX(), (int) b.getY(), (int) d.getX(), (int) d.getY());
g.drawLine((int) b.getX(), (int) b.getY(), (int) e.getX(), (int) e.getY());

List<Point2D> pointsInCone = getPointsInCone(pa, angeles_deg);
for (int i = 0; i < pa.length; i++) {
if (pointsInCone.contains(pa[i])) {
g.setColor(Color.RED);
} else {
g.setColor(Color.BLACK);
                    }
g.fillOval((int) pa[i].getX() - 2, (int) pa[i].getY() - 2, 4, 4);
g.drawString("" + (char) ('A' + i), (int) pa[i].getX(), (int) pa[i].getY() + 15);
                }
            }
        };
JFrame f = new JFrame();
        f.add(c);
f.setSize(1000, 1000);
f.setDefaultCloseOperation(WindowConstants.EXIT_ON_CLOSE);
f.setVisible(true);
c.addMouseMotionListener(new MouseMotionAdapter() {
@Override
            public void mouseDragged(MouseEvent e) {
                Point p = e.getPoint();
pa[1] = p;
c.repaint();
            }
        });
new Timer().schedule(new TimerTask() {
@Override
            public void run() {
pa[1] = rotateEndpointC(pa[0], pa[1], Math.toRadians(1));
c.repaint();
            }
}, 10_000, 50);
    }

private static Point2D getEndpointC(Point2D a, Point2D b, int length) {
Point2D a_b = new Point2D.Double((b.getX() - 500) - (a.getX() - 500), (500 - b.getY()) + (500 - a.getY()));
double len_a_b = Math.sqrt(a_b.getX() * a_b.getX() + a_b.getY() * a_b.getY());
a_b = new Point2D.Double(a_b.getX() / len_a_b, a_b.getY() / len_a_b);
Point2D c = new Point2D.Double(a_b.getX() * length, a_b.getY() * length);
return new Point2D.Double((b.getX() - 500) + c.getX() + 500, 500 - ((500 - b.getY()) + c.getY()));
    }

private static Point2D rotateEndpointC(Point2D b, Point2D c, double angle) {
double x = (c.getX() - 500) - (b.getX() - 500);
double y = (500 - c.getY()) - (500 - b.getY());
double xNew = x * Math.cos(angle) - y * Math.sin(angle);
double yNew = x * Math.sin(angle) + y * Math.cos(angle);
return new Point2D.Double((b.getX() - 500) + xNew + 500, 500 - ((500 - b.getY()) + yNew));
    }

private static List<Point2D> getPointsInCone(Point2D[] pa, double angle_deg) {
Point2D a = pa[0];
Point2D b = pa[1];
double threshold = a.distance(b) * Math.cos(Math.toRadians(Math.PI / 4 * angle_deg));
System.out.println("threshold: " + threshold);
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 key = dist_a_c - dist_b_c;
if (key >= threshold) {
                points.add(c);
System.out.printf("%s=(%d, %d) key=%f%n", (char) ('A' + i), (int) c.getX(), (int) c.getY(), key);
            }
        }
return points;
    }
}

Danke an alle, die hier mitgeholfen haben!

PS. Es hätte mich eigentlich auch gewundert, wenn es ohne PI gegangen wäre.

 

[simpsonsfan]

@ChristianG. Klar, den acos kann man sich sparen, wenn es effizient sein soll. Dann aber natürlich größer, nicht kleiner vergleichen.

@CyborgBeta Deine Rätsellösung ist halt leider immer noch genau so falsch wie vorher. Und ja, da kommen bei deinen Tests zufällige Treffer raus, weil du einfach nur Punkte markierst, die in etwa auf der Achse und hinter B liegen.
Dazu hin berechnest du 3 Abstände von Punkten und betreibst damit mehr Rechenaufwand, als mit der Winkelberechnung mit Skalarprodukt (die ich btw. ggü. einer Winkelberechnung mit dem Kreuzprodukt vorgeschalgen hatte, weil sie etwas weniger Operationen benötigt.)

Dass du keinen Beweis für die Allgemeingültigkeit deiner Methode findest, liegt eben daran, dass sie es nciht ist. Wenn man sich mal kurz überlegt, was in Grenzfällen geschieht, findet man auch ganz schnell ein Gegenbeispiel. Insbesondere markeirt deine Methode bspw. den Punkt
C_falsepositiv = A + (threshold - 1) * vec(AB),
wobei vec(AB) den Vektor von A nach B bezeichnet, als innerhalb des Kegels.

 

[CyborgBeta]

Dazu hin berechnest du 3 Abstände von Punkten und betreibst damit mehr Rechenaufwand, als mit der Winkelberechnung mit Skalarprodukt

Stimmt doch gar nicht. Man müsste mal die genaue Anzahl der Operationen ermitteln.

Dass du keinen Beweis für die Allgemeingültigkeit deiner Methode findest, liegt eben daran, dass sie es nciht ist.

Dann nenne ein konkretes Gegenbeispiel mit Koordinaten, das nicht auf Rundungsfehler zurückzuführen ist. Nach meinen Versuchen wird immer das richtige Ergebnis zurückgegeben. Ergo: allgemeingültig. Den Beweis kann wer anderes machen.

 

[dms]

@dms Guten Tag, nun sei nicht so zickig ...

Servus, bitte überarbeite doch mal deine Fragetechnik etwas, zB das Prinzip der Userstories könnte stark helfen - denn so funktiniert Softwareentwicklung im Team nicht wirklich wenn mann wartbare Software anstrebt.

Da zieht sich ein methodischer Faden durch deine Art der Fragen - was fällt denn hier auf

* nach N-Beiträge ist das Problem benannt und das versuchte oder der Eigenanteil kommen ein bischen

* die Musterdaten für das 3D-Problem arbeiten einfach mal so alle dann im 2D-Bereich - ja Z kann man ja Konstant auf 0 legen .. aber dann ist die Lösung viel einfacher möglich

* die nicht extra genannte Programmiersprache wird dann hier fragmentarisch einkopiert das man zum mitmachen sich zu dem Stub alles selber hinbauen müsste

* Auf Hinweise kommen dann Erwiederungen zwischen "Cholerisch und Basta..." oder wirkt "Pampig" oder "Berliner Schnauze" wo man als Adressat ein dickes Fell braucht

Ja, man hat beim puren Text weniger Kontext als im Gespräch und das kann man Versuchen zu kompensieren

Ahoi D.

Lesetipps für das Drummrum:

• Der pragmatische Programmier
• Weniger schlecht Programmieren
• Der Termin von deMarco

 

[CyborgBeta]

@dms Also, wenn man ehrlich sein möchte, stand alles, bis auf die Programmiersprache, schon im Eingangsposting ... und mir hätte bei dieser mathematischen Frage auch Pseudocode genügt. Außerdem, ein Forum ist für Fragen da ... unabhängig von der Anzahl der Postings des Fragestellers. Nur meine Sicht.

 

[simpsonsfan]

Stimmt doch gar nicht.

Und wenn ich jetzt "stimmt ja wohl" schreibe? Und vielleicht noch den Beweis kann wer anderes machen?
Das Gegenbeispiel habe ich genannt. Das zu ignorieren ist sehr ignorant ;-P
Aber gut. Sei bspw. A=(0,0,0), B=(100,0,0) und C=(99.6, 0, 0), dann ist C laut deiner Methode im Kegel enthalten, weil 99,2/100>cos(7,58°) ist.

Die pi/4 machen an der Stelle (nämlich für einen Wert in Grad) übrigens auch keinerlei Sinn. Deine Methode wird bei größeren Winkeln übrigens sehr schnell deutlich größere Abweichungen zeigen. Kannst ja mal einen Halbwinkel nahe 90° probieren (oder auch 180° oder auch nur die 25°, die du zuvor getestet hattest.)

Letzlich hatte der ChatGpt-Ansatz aus Post #5 es ja schon sehr schön (wie von mir beschireben mittels Skalarprodukt) gelöst, hatte nur den Fehler, dass er in Zeile 10 die Kegelspite in Punkt A gelegt hat (davor jedoch nicht.)

Ein stures "in meinem Test funktioniert es fast, und die Gegenbeispiele ignoriere ich" bringt eigentlich wenig zur technischen Lösung. Ein "in meinem Test funktioniert das fast, und das Ergebnis ist gut genug für den gewünschten Anwendungszweck" wäre da schon was anderes.
Deine Animation zeigt übrigens bereits beim ersten Punkt "P" eine fehlerhaft Erkennung. Schau doch mal Frame-by-Frame drauf.
Und dass es sich eben gerade nicht um Rundungsfehler handelt, hat mein analytisches Gegenbeispiel ja schon bewiesen.

Ein Skalarprodukt im R³ besteht übrigens aus 3 Multiplikationen, deren Ergebnisse dann zusammenaddiert werden. Distanzbestimmung im R³ besteht aus 3 Subtraktionen, 3 Multiplikationen, deren Eregbnisse aufaddiert werden, und schließlich einmal Wurzelziehen.
Wobei die Performanceunterschiede für den Anwendungsfall bei dir vermutlich absolut egal sein dürften.

Ach ja und

ich habe eine Liste mit 3-Punkten (hier sind es zur Vereinfachung nur 26).

benötigt einiges an Überlegung, was gemeint sein soll. (3D Punkte, zur Vereinfachung nur 2D?; 30 Punkte, zur Vereinfachung nur 26?; 3D Punkte, und zwar viele, hier zur Vereinfachung nur 26? - so genau weiß man das nicht.) Mir passieren auch Tippfehler, aber manche sind halt schwerer zu entziffern als andere.

So. Ich geh jetzt bieren.

 

[CyborgBeta]

Sei bspw. A=(0,0,0), B=(100,0,0) und C=(99.6, 0, 0), dann ist C laut deiner Methode im Kegel enthalten, weil 99,2/100>cos(7,58°) ist

Hast recht, aber bitte dann auch richtige Werte verwenden:

99.56 wäre natürlich echt größer als 99.06 ...

Distanzbestimmung im R³ besteht aus 3 Subtraktionen, 3 Multiplikationen, deren Eregbnisse aufaddiert werden, und schließlich einmal Wurzelziehen.

Es gibt einen Trick, wonach das Sqrt bei Längenvergleichen nicht benötigt wird. (Nur, wenn man das tatsächliche Ergebnis braucht ...)

Wobei die Performanceunterschiede für den Anwendungsfall bei dir vermutlich absolut egal sein dürften

Warum der Unterton? Es geht um ein 4,5 GB großes Datenbankfile (gepackt), mit etwa 400 Milliarden 3D-Punkten ... also schon in Richtung Big Data, wo solche Optimierungen Sinn machen würden.

Ergänzung (29. März 2025)

So. Ich geh jetzt bieren.

Schönen Abend.