Punkt innerhalb Kreis?

[sx2008]

Folgende Funktion berechnet, ob ein Punkt innerhalb eines Kreise mit einem bestimmten Radius liegt.
Dabei wird der bekannte Satz des Pythagoras verwendet.
Aus Geschwindigkeitsgründen wird auf Wurzelziehen und Gleitkommaberechnungen verzichtet.
Die Unit math muss mit uses eingebunden werden.

Delphi-Quellcode:

// a: Kreismittelpunkt
// b: Testpunkt
// Result => 
// 1  = Punkt innerhalb Kreis
// 0  = Punkt liegt auf Kreislinie
// -1 = Punkt ausserhalb Kreis
function PointInCircle(a,b:TPoint; radius:integer):integer;
  function SquareInt(x:integer):integer; // Hilfsfunktion: Quadrieren
  begin
    result := x * x;
  end;
begin
  result := Sign(SquareInt(radius) - SquareInt(a.x-b.x) - SquareInt(a.y-b.y));
end;

Falls Kreismittelpunkt und/oder der Testpunkt nur in x- und y-Werten vorliegen, kann man die Funktion Point() verwenden:

Delphi-Quellcode:

if PointInCircle(Point(shape.Left, shape.Top), Point(x,y), 50) >= 0 then ...

[CalganX]

Warum liefert die Funktion einen Integer und keinen Boolean zurück? Wenn du ohnehin auf ">= 0" prüfen musst, kannst du das auch direkt in der Funktion tun. :gruebel:

[sx2008]

Zitat:

Zitat von CalganX

Warum liefert die Funktion einen Integer und keinen Boolean zurück?

Weil es mathematisch gesehen 3 Fälle sind: im Kreis, auf der Kreislinie und Ausserhalb.
So kann der Anwender selbst entscheiden, ob er die Punkte, direkt auf der Kreislinie liegen noch mitrechnet oder nicht.
Wenn man z.B. wissen möchte, ob sich zwei Kreise mit den Mittelpunkten M1 und M2 gerade berühren, dann kann man das so ermitteln:

Delphi-Quellcode:

if PointInCircle(M1, M2, Radius1+Radius2) = 0 then ...

Wer mag, kann sich die Funktion natürlich so umschreiben, dass ein Boolean zurückgeliefert wird.

[DeddyH]

Für SquareInt kann man auch die Builtin-Funktion Sqr benutzen ;). Außerdem steht ein paar Threads weiter unten ein weiterer zu diesem Thema.

[Uwe Raabe]

Die Beschränkung auf Integer erscheint mir nicht sehr weise, da z.B. bei einem Kreis mit "ungeradem" Durchmesser der Mittelpunkt und der Radius eben nicht als Integer ausgedrückt werden können. Auch ist der Geschwindigkeitsnachteil von Gleitkommaoperationen bei zeitgemäßen Prozessoren durchaus zu vernachlässigen. Interessanterweise ist gerade in diesem Fall die Verwendung von Extended statt Integer etwas schneller:

Der Code

Delphi-Quellcode:

result := Sign(Sqr(radius) - Sqr(a.x-b.x) - Sqr(a.y-b.y));

läuft auf meinem System ca. 10% schneller als die Integer-Variante

Delphi-Quellcode:

result := Sign(SquareInt(radius) - SquareInt(a.x-b.x) - SquareInt(a.y-b.y));

während die leicht optimierte Version

Delphi-Quellcode:

var
  x, y: Integer;
begin
  x := (a.x-b.x);
  y := (a.y-b.y);
  result := Sign(radius*radius - x*x - y*y);
end;

nur knapp 5% schneller ist als die Extended-Version.

[sx2008]

Zitat:

Zitat von Uwe Raabe

... SQR() ...läuft auf meinem System ca. 10% schneller als die Integer-Variante

Die Sqr()-Funktion kannte ich natürlich.
Ich hätte erwartet, dass eine Unterfunktion mit einer Integer-Multiplikation schneller ist, als Sqr() mit anschliesender impliziter Umwandlung nach Integer. :gruebel:

[Uwe Raabe]

Zitat:

Zitat von sx2008

Zitat:

Zitat von Uwe Raabe

... SQR() ...läuft auf meinem System ca. 10% schneller als die Integer-Variante

Die Sqr()-Funktion kannte ich natürlich.
Ich hätte erwartet, dass eine Unterfunktion mit einer Integer-Multiplikation schneller ist, als Sqr() mit anschliesender impliziter Umwandlung nach Integer. :gruebel:

Die Integer-Multiplikation ist auch geringfügig schneller. Zeit kostet aber der zusätzliche Funktionsaufruf, während SQR ein Maschinenbefehl ist. Eine implizite Umwandlung nach Integer für das Ergebnis findet auch gar nicht statt, da für SIGN auch eine overloaded Funktion mit Extended-Parameter vorliegt.

[Namenloser]

Zitat:

Zitat von Uwe Raabe

Zitat:

Zitat von sx2008

Zitat:

Zitat von Uwe Raabe

... SQR() ...läuft auf meinem System ca. 10% schneller als die Integer-Variante

Die Sqr()-Funktion kannte ich natürlich.
Ich hätte erwartet, dass eine Unterfunktion mit einer Integer-Multiplikation schneller ist, als Sqr() mit anschliesender impliziter Umwandlung nach Integer. :gruebel:

Die Integer-Multiplikation ist auch geringfügig schneller. Zeit kostet aber der zusätzliche Funktionsaufruf, während SQR ein Maschinenbefehl ist. Eine implizite Umwandlung nach Integer für das Ergebnis findet auch gar nicht statt, da für SIGN auch eine overloaded Funktion mit Extended-Parameter vorliegt.

Und wenn man eine inline-Funktion draus macht?

[Uwe Raabe]

Zitat:

Zitat von NamenLozer

Und wenn man eine inline-Funktion draus macht?

Möglich, der Performance-Gewinn liegt aber allenfalls im 1-stelligen Prozentbereich. Meines Erachtens nach rechtfertigt das nicht die Einschränkungen auf Integer-Variablen. Wie schon gesagt: hat der Kreis einen ungeraden Integer-Durchmesser, wird das Ergebnis schon ungenau, weil ich sowohl den Mittelpunkt, als auch den Radius nicht mehr exakt angeben kann.

[Dipl Phys Ernst Winter]

"sx2008"

Zitat:

Aus Geschwindigkeitsgründen wird auf Wurzelziehen und Gleitkommaberechnungen verzichtet.

Der Ko-Prozessor rechnet mit Gleitkommazahlen vom Typ extended allemal schneller als die CPU mit Integerwerten.

Was soll radius: integer? Die Komponenten von TPoint sind offensichtlich, wegen SquareInt(a.x-b.x), auch nur Integerwerte,?

Diese Einschränkungen gehen viel zu weit!

Delphi-Quellcode:

typ
  TPoint= record x, y: extended end;
cons
  eps= 1e-14;

function PointInCircle(m, p:TPoint; radius: extended):integer;
var
  a: extended;       // Abstend m - p
begin
  a:= (m.x - p.x)*(m.x - p.x) + (m.y - p.y)*(m.y - p.y);
  if Abs(a)>eps then a:= sqrt(a) else a:= 0;    // a könnte durch Rundungsfehler<0 sein
  if (a - radius)<-eps then Result:= 1          // Punkt innerhalb Kreis
  else if (a - radius)>eps then Result:= -1     // Punkt ausserhalb Kreis 
  else Result:= 0                               // Punkt liegt auf Kreislinie
end;

Noch ein Hinweis: Verwende immer den Typ extended! single und double werden vor und nach jeder Verwendung durch den Koprozessor in/aus extended Typgewandelt.