Punktberechnung im Kreis

[dredav]

Hallo,

ich suche eine Möglichkeit zu prüfen, ob ein Punkt in einem Kreis ist. Nun meine frage, gibt es in Java eine Ressourcen schonend Möglichkeit zu prüfen ob ein Punkt in dem Kreis ist. Bisher prüfe ich nur ob die Koordinaten, dem Mittelpunkt des Kreises entsprechen.

public boolean pruefeObGetroffen (int x, int y) {
    if (x == koordinate.holeKoordinate("x") && y == koordinate.holeKoordinate("y")) {
        return true;
    }
    return false;
}

Grüße
David

 

[Marcinek]

Du berechnest den Abstand zwischen 2 Punkten (Mittelpunkt und dem zu prüfenden Punkt) mit der Formel aus der 8.Klasse.

Wenn der Abstand kleiner ist als der radius des Kreises, dann liegt der Punkt innerhalb des Kreises.

Das ganze ist in O(1) lösbar und damit effizient.

 

[Marco13]

Das ganze ist in O(1) lösbar und damit effizient.

In diesem Fall macht die Betrachtung der asymptotischen Laufzeitkomplexität keinen Sinn. Lapidar formuliert: Wenn es "O(n)" wäre, was sollte 'n' denn dann überhaupt sein? :autsch:

So, wie du es beschrieben hast, sollte man das nicht machen:
Du berechnest den Abstand zwischen 2 Punkten...Wenn der Abstand kleiner ist als der radius des Kreises
Stattdessen:
Du berechnest den quadrierten Abstand zwischen 2 Punkten...Wenn der Abstand kleiner ist als der quadrierte radius des Kreises

Damit spart man sich das Wurzelziehen bei der Abstandsberechnung, und das ist SEHR viel schneller. Wenn dieser Test oft gemacht werden muss, lohnt sich das sogar richtig. Und selbst wenn nicht, macht man das aus Prinzip so :smoke:

 

[faetzminator]

In deutsch: ein einfacher Pythagoras

public boolean isInCircle(Point p, Circle c) {
    int x = Math.abs(p.getX() - c.getX());
    int y = Math.abs(p.getY() - c.getY());
    return Math.sqrt(x * x + y * y) <= c.getRadius();
}

 

[Marco13]

public boolean isInCircle(Point p, Circle c) {
    int x = Math.abs(p.getX() - c.getX());
    int y = Math.abs(p.getY() - c.getY());
    int rr = c.getRadius() * c.getRadius();
    return (x * x + y * y) <= rr;
}

 

[Final_Striker]

public boolean isInCircle(Point p, Circle c) {
    int x = Math.abs(p.getX() - c.getX());
    int y = Math.abs(p.getY() - c.getY());
    int r = c.getRadius();
    return (x * x + y * y) <= (r * r);
}

So hat man sich auch noch einen Methodenaufruf gespart. :-D

 

[faetzminator]

Freaks!

Edit:
wenn, dann sowieso als Methode in [c]Circle[/c], also :bae:

public boolean isInCircle(Point p) {
    int x = Math.abs(p.getX() - getX());
    int y = Math.abs(p.getY() - getY());
    int r = getRadius();
    return (x * x + y * y) <= (r * r);
}

 

[Landei]

Wofür nehmt ihr denn alle abs, wenn sowieso quadriert wird?

public boolean isInCircle(Point p) {
    int x = p.getX() - getX();
    int y = p.getY() - getY();
    int r = getRadius();
    return (x * x + y * y) <= (r * r);
}

 

[Marco13]

Stimmt, das hatte ich beim C&P aus faetzminator's Beitrag übersehen ...

 

[Semox]

Hallo,

Also, wenn man die Punkte in einer ArrayList namens AllNodes hat, kann man doch nach Import von java.awt.Point folgende Operation laufen lassen. Wenn der Kreis einen Durchmesser mit dem Attribut DIA hat, dann erledigt das prüfen, ob z.B. ein Klick in einem Kreis liegt die Methode distance().

public void mouseClicked(MouseEvent e) {
		q = e.getPoint();
		for (Iterator<Point> iterator = AllNodes.iterator(); iterator
			.hasNext();) {
			Point p = iterator.next();
			if (p.distance(q) <= DIA) {
				System.out.println("Der Klick war innem Kreis");
			}
		}
}

Hilft das weiter?

Gruß,
Semo

 

[Antoras]

Wer versichert dir, dass Point nicht eine selbst erstellte Klasse ist? Man muss nicht java.awt.Point benutzen. Im übrigen berechnet distance() noch die Wurzel. Das ist wie schon gesagt langsamer als eine Multiplikation.
Außerdem gibt es in Java mittlerweile eine foreach-Schleife, die man auch verwenden sollte.

 

[Semox]

Wer versichert dir, dass Point nicht eine selbst erstellte Klasse ist? Man muss nicht java.awt.Point benutzen. Im übrigen berechnet distance() noch die Wurzel. Das ist wie schon gesagt langsamer als eine Multiplikation.
Außerdem gibt es in Java mittlerweile eine foreach-Schleife, die man auch verwenden sollte.

Ich verstehe Deine Frage nicht. Wie meinst Du das?

Man muß meinen Vorschlag auch nicht annehmen.

Warum sollte das Wurzelziehen langsamer sein? Das ist nicht wahr, denn intern wird der Prozi sich wegen dieser Kleinigkeit bestimmt nicht wirklich beeindrucken lassen, denn die Wurzel wird ohnehin über Potenzgesetze intern als eine Multiplikation angesehen.

For-Each - stimmt - kann man auch benutzen. Jeder nach seiner Façon...

Gruß,
Semo

 

[Antoras]

Ich meinte damit, dass man mit deiner Lösung nur dann was anfangen kann wenn man java.awt.Point verwendet.

Bei der Wurzelberechnung kenne ich nur ein paar Software-Algos, die um einiges langsamen und komplexer als eine Multiplikation sind. Wie die CPU/FPU das berechnet weiß ich nicht. Selbst wenn der Geschwindigkeitsunterschied nur minimal ist dürfte das aber ohnehin nur einen spürbaren Unterschied machen wenn man mal eine Million Punkte hat.

 

[Semox]

Ich weiß auch nicht, ob es relevant ist die Point Klasse einzusetzen. Das geht aus dem Startpost auch nicht hervor, ob das für ihn/sie rein von mathematischem Interesse ist, oder ob das mal ein Kollisionstest für ein Spiel o.ä. werden soll.

Ich fand es schlicht smarter eine fertige Methode zu nutzen, die in der API bereitsteht. Vorallem dann, wenn man sich damit einige Zeilen Code und der daraus resultierenden Fehlerquellen sparen kann (obwohl die paar Zeilen den Kohl auch nicht fett machen würden).

Letztendlich kann er/sie auf jeden Fall mal in der Klasse nachschauen, wie die Java Coder das machen... Ich finde deren Ideen doch recht kurz und prägnant. Und je kürzer desto schöner... :toll:

Viele Grüße,
Semo

 

[Marco13]

Das ist nicht wahr, denn intern wird der Prozi sich wegen dieser Kleinigkeit bestimmt nicht wirklich beeindrucken lassen, denn die Wurzel wird ohnehin über Potenzgesetze intern als eine Multiplikation angesehen.

Es gibt schon einen Grund, warum es in der Point-Klasse auch eine Methode "distanceSq" gibt: Wurzelberechnung IST aufwändig. Sie wird nativ durchgeführt, aber es ist auf jeden Fall besser, wenn sie nicht durchgeführt werden muss.

Ein kleiner Monte-Carlo-PI-Brechnungs-Microbenchmark (der mit der üblichen Vorsicht zu genießen ist, aber schon einen Unterschied zeigt)

import java.util.*;
import java.awt.*;
import java.util.List;

class DistanceTest
{
    static int size = 1000;

    public static void main(String args[])
    {
        int min = 500000;
        int max = 5000000;
        for (int n=min; n<=max; n+=(max-min)/5)
        {
            System.out.println("n="+n);

            Random random = new Random(0);
            List<Point> points = new ArrayList<Point>();
            for (int i=0; i<n; i++)
            {
                int x = random.nextInt(size);
                int y = random.nextInt(size);
                points.add(new Point(x,y));
            }

            long before, after;
            double pi, time;

            before = System.nanoTime();
            pi = test(points);
            after = System.nanoTime();
            time = (after-before)/1e6;
            System.out.println("PI: "+pi+" time         "+time+"ms");

            before = System.nanoTime();
            pi = testSq(points);
            after = System.nanoTime();
            time = (after-before)/1e6;
            System.out.println("PI: "+pi+" time squared "+time+"ms");
        }


    }

    private static double test(List<Point> points)
    {
        int count = 0;
        for (Point point : points)
        {
            if (point.distance(0,0) < size)
            {
                count++;
            }
        }
        return 4.0*count/points.size();
    }
    private static double testSq(List<Point> points)
    {
        int count = 0;
        int ss = size*size;
        for (Point point : points)
        {
            if (point.distanceSq(0,0) < ss)
            {
                count++;
            }
        }
        return 4.0*count/points.size();
    }
}

 

[Semox]

Hübscher Test. Gefällt mir. Es steht natürlich außer Frage, daß man bei Millionen Punkten tatsächlich einen hübschen Betrag Zeit braucht, wenn alles über Umwandlungen von Wurzeln laufen muß.

Mich würde mal der perfekte Algo interessieren, wie der wohl aussieht?

Grüße,
Semo