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.

[quendolineDD]

Übergeb doch ein Flag, ob es erlaubt sein soll, dass der Punkt auf der Linie ist oder nicht.

[3_of_8]

Zitat:

Zitat von Dipl Phys Ernst Winter

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

Ich kann mir kaum vorstellen, dass irgendein Koprozessor mehrere doppelt so schnell wie der Prozessor getaktete ALUs übertreffen kann. Eine Addition/Subtraktion erledigt ein Pentium 4 in einem halben Takt.

[alzaimar]

Zitat:

Zitat von Dipl Phys Ernst Winter

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!

Wenn man auf dem Canvas zeichnet (und man zeichnet unter Windows fast ausschließlich auf einem TCanvas bzw. einem DC), dann hat man es nur mit Integer-Werten zu tun, also ist eine Funktion, die Extended-Parameter verwendet, fehl am Platze.

Zitat:

Delphi-Quellcode:

typ
  TPoint= record x, y: extended end;

Weiterhin ist es unglücklich, den in der Unit Types definierten Datentyp 'TPoint' zu überschreiben. Besser wäre ein Name à la 'TExtendedPoint' o.ä.

Zu guter Letzt würde ich eine Funktion vorschlagen, die direkt angibt, ob der Punkt im Kreis, auf dem Kreis oder außerhalb des Kreises ist:

Delphi-Quellcode:

uses Types;
Type
  TPointInCircleResult = (prInsideCircle, prOnCircle, prOutOfCircle);

Function TestPointInCircle (aPoint : TPoint; aCircleCenter : TPoint; aCircleRadius : Integer) : TPointInCircleResult;

Dann gibt es keine Interpretationsmißverständnisse. Und dokumentieren muss man auch nichts.

[himitsu]

brauchte grad mal etwas Abwechslung

Delphi-Quellcode:

Function PointInCircle(Const aPoint, aCircleCenter: TPoint; aCircleRadius: Integer): Integer;
  Var t: Integer;

  Begin
    Result := radius * radius;
    t := a.x - b.x;  Dec(Result, t * t);
    t := a.y - b.y;  Dec(Result, t * t);
    If      Result < 0 Then Result := NegativeValue
    Else If Result > 0 ThenResult := PositiveValue;
  End;

und die SquareInt würde ich (in "neueren" Delphis) als Inline-Funktion definieren

wobei der Vorschlag mit TPointInCircleResult eigentlich besser ist, aber wenn hier alle sooo auf Tempo achten? o.O

also 100.000.000 Mal ausgeführt in ... (bei mir, grad eben mal schnell in D7)
1: ~1,35 sec (0,0000135 Millisekunden)
2: ~1,25 sec (0,0000125 Millisekunden)
3: ~0,50 sec (0,0000050 Millisekunden)
4: ~0,40 sec (0,0000040 Millisekunden)

das ist alles fast nix ... wie oft wollt ihr diese Funktion denn aufrufen?

Delphi-Quellcode:

// 1
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;

// 2
function PointInCircle2(a,b:TPoint; radius:integer):integer;
begin
  result := Sign(radius*radius - (a.x-b.x)*(a.x-b.x) - (a.y-b.y)*(a.y-b.y));
end;

// 3
function PointInCircle3(const a,b:TPoint; radius:integer): integer;
var t: Integer;
begin
  Result := radius*radius;
  t := a.x - b.x;  Dec(Result, t*t);
  t := a.y - b.y;  Dec(Result, t*t);
  if Result < 0 then
    Result := NegativeValue
  else if Result > 0 then
    Result := PositiveValue;
end;

// 4
Type TPointInCircleResult = (prInsideCircle, prOnCircle, prOutOfCircle);

Function PointInCircle4(Const aPoint, aCenter: TPoint; aRadius: Integer): TPointInCircleResult;
  ASM
    PUSH  EDI
    IMUL  ECX, ECX             // aRadius := aRadius * aRadius;
    MOV   EDI, [EAX]           // temp := aPoint.X - aCenter.X;
    SUB   EDI, [EDX]           //
    IMUL  EDI, EDI             // temp := temp * temp;
    SUB   ECX, EDI             // aRadius := aRadius - temp;
    MOV   EDI, [EAX + 4]       // temp := aPoint.Y - aCenter.Y;
    SUB   EDI, [EDX + 4]       //
    IMUL  EDI, EDI             // temp := temp * temp;
    SUB   ECX, EDI             // aRadius := aRadius - temp;
    TEST  ECX, ECX             // if ...
    JS    @@neg                // ... aRadius < 0 then goto negitive
    JNZ   @@pos                // ... aRadius > 0 then goto positive
    MOV   AL, &prOnCircle      // ... else Result := prOnCircle;
    POP   EDI                  // exit;
    RET
    @@neg:                     // negative:
    MOV   AL, &prInsideCircle  // Result := prOnCircle;
    POP   EDI                  // exit;
    RET
    @@pos:                     // positive:
    MOV   AL, &prOutOfCircle   // Result := prOnCircle;
    POP   EDI
  End;

[edit] Version 4 (ASM) eingefügt

[Medium]

Zitat:

Zitat von Dipl Phys Ernst Winter

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

Selbst wenn dies zuträfe, ist Singe noch immer schneller als Double ist schneller als Extended. Getestet mit reinen D7 Kompilaten, und D7 mit inline ASM handverschönert. Integer ist ünrigens noch mal eine ganze Ecke schneller. Wo die FPU schneller ist, ist bei Verwendung von MMX, das jedoch ist in nur wenigen Spezialfällen sinnvoll einsetzbar. Ebenso könnte es gut sein, dass die FPU Floats schneller als die CPU Integers berechnet, wenn ich dazu SSE(2) nehme. Aber auch hier gilt wie bei MMX dass es nicht generell sinnvoll einsetzbar ist.
Gerade heraus kompiliert gilt: Int < Single < Double < Extended

Dass in obigem Beispiel die Integer-Version sogar langsamer sein kann, ist in der Tat dem Prozeduraufruf geschuldet, der bei derart wenigen Instruktionen doch ganz schön rein haut.

[quendolineDD]

Und wenn man die GPU zur Berechnung nimmt?
Das dürfte dann nochmal einiges schneller als die CPU sein :p

[himitsu]

Extended ist eh ungünstig ... 10 Byte bei 32 Bit

Zitat:

Zitat von quendolineDD

Und wenn man die GPU zur Berechnung nimmt?
Das dürfte dann nochmal einiges schneller als die CPU sein :p

probier es doch einfach mal

ich hatte vorhin mal den Fall, daß ich die Testschleife so definierte
... man beachte, daß Delphi Point nicht in eine Konstante umwandelt, sonder daß da die Funktion Point aufgerufen wird, was das Ergebnis schön verfällscht :wall:

Delphi-Quellcode:

C := GetTickCount;
for i := 0 to 100000000 do
  if PointInCircle(Point(10, 20), Point(20, 30), 30) = 0 then ;
Caption := Caption + ' ' + IntToStr(GetTickCount - C);

[add]
der absolute Overkill, im Verhältnis zu allen anderen Versionen:
3,3 Sekunden
ohne const-Parameter sogar
4,5 Sekunden

und Single ist nur minimal schleller als Extended

Delphi-Quellcode:

type TExtendedPoint = record  x, y: Extended;  end;
function PointInCircle2_(const a,b:TExtendedPoint; const radius:extended):integer;
begin
  result := Sign(Sqr(radius) - Sqr(a.x-b.x) - Sqr(a.y-b.y));
end;

[Medium]

Zitat:

Zitat von quendolineDD

Und wenn man die GPU zur Berechnung nimmt?
Das dürfte dann nochmal einiges schneller als die CPU sein :p

Für eine einzelne Berechnung? Zigfach langsamer. Selbst wenn man den Initialisierungsaufwand für eine D3D Applikation heraus nimmt sollte es noch um ein Vielfaches langsamer sein. Interessant wird es hier wenn man es mehrere hundert Male machen möchte, wobei keine Rechnung von einem Ergebnis einer anderen abhängt. Dann lohnt sich der Aufwand, weil die große Stärke einer GPU Parallelität ist. D.h. es werden dann je nach GPU und Methode zig bis hunderte Rechnungen echt gleichzeitig ausgeführt.
Da tut sich allerdings etwas im Moment, und ich vermute dass GPUs in nicht allzu ferner Zukunft relativ integriert ansprechbar sind. Derzeit muss man halt eine volle D3D Umgebung initialisieren, und die Kommunikation mit den Shadern ist voll auf dieses Gebiet ausgerichtet, so dass man ein wenig tricksen muss um "normale" Dinge zu tun. Für nur eine oder auch 20 dieser Rechnungen ist das nicht lohnenswert.

[himitsu]

Zitat:

Zitat von Medium

Für eine einzelne Berechnung? Zigfach langsamer.

siehe mein [add] im letzen Post :angel:

jupp, das mit den besser ansprechbaren GPUs hab ich auch gehört,
auch wenn ich das wohl selber nie wirklich nutzen werd', klingt es schon interessant

[R2009]

Hi,
ich habe mit die Mühe gemacht und ein kleines Demoprogramm mit Zeitmessung erstellt.
Durch "einkommentieren" der oben genannten Funktionen könnt ihr direkt die Sekunden und ihre Bruchteile ablesen.

Delphi-Quellcode:

unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls, DateUtils, math;

type
  TPointInCircleResult = (prInsideCircle, prOnCircle, prOutOfCircle);
  TForm1 = class(TForm)
    Button1: TButton;
    Label1: TLabel;
    Label2: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}
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; 

function PointInCircle2(a,b:TPoint; radius:integer):integer; 
begin
  result := Sign(radius*radius - (a.x-b.x)*(a.x-b.x) - (a.y-b.y)*(a.y-b.y)); 
end;

function PointInCircle3(const a,b:TPoint; radius:integer): integer;
var t: Integer; 
begin
  Result := radius*radius;
  t := a.x - b.x;  Dec(Result, t*t);
  t := a.y - b.y;  Dec(Result, t*t);
  if Result < 0 then
    Result := NegativeValue
  else if Result > 0 then
    Result := PositiveValue;
end;


Function PointInCircle4(Const aPoint, aCenter: TPoint; aRadius: Integer): TPointInCircleResult;
  ASM
    PUSH  EDI
    IMUL  ECX, ECX             // aRadius := aRadius * aRadius;
    MOV   EDI, [EAX]           // temp := aPoint.X - aCenter.X;
    SUB   EDI, [EDX]           //
    IMUL  EDI, EDI             // temp := temp * temp;
    SUB   ECX, EDI             // aRadius := aRadius - temp;
    MOV   EDI, [EAX + 4]       // temp := aPoint.Y - aCenter.Y;
    SUB   EDI, [EDX + 4]       //
    IMUL  EDI, EDI             // temp := temp * temp;
    SUB   ECX, EDI             // aRadius := aRadius - temp;
    TEST  ECX, ECX             // if ...
    JS    @@neg                // ... aRadius < 0 then goto negitive
    JNZ   @@pos                // ... aRadius > 0 then goto positive
    MOV   AL, &prOnCircle      // ... else Result := prOnCircle;
    POP   EDI                  // exit;
    RET
    @@neg:                     // negative:
    MOV   AL, &prInsideCircle  // Result := prOnCircle;
    POP   EDI                  // exit;
    RET
    @@pos:                     // positive:
    MOV   AL, &prOutOfCircle   // Result := prOnCircle;
    POP   EDI
  End;

procedure TForm1.Button1Click(Sender: TObject);
var n,q:integer;s,e:tdatetime;a:string;r0,r:double;a0,b0:Tpoint;q0:TPointInCircleResult;
begin
  //Leerlaufzeit bestimmen
  s:=now;
  for n:=1 to 100000000 do
      begin
      end;
  e:=now;
  r0:=SecondSpan(s,e);
  //Laufzeit bestimmen
  s:=now;
  for n:=1 to 100000000 do
      begin
        q:=PointInCircle(a0,b0,10);
//        q:=PointInCircle2(a0,b0,10);
//        q:=PointInCircle3(a0,b0,10);
//        q0:=PointInCircle4(a0,b0,10);
      end;
  e:=now;
  //r0 korrigiert Laufzeit Leerlaufzeit wird abgezogen
  r:=SecondSpan(s,e)-r0;
  a:=floattostr(r);
  label1.Caption:=a;
end;

end.

Version 1: 1,937sec
Version 2: 1,657sec
Version 3: 0,452sec
Version 4: 0,343sec
Diese Werte sind mit einem Core 2 duo ermittelt. Ich bin mir nicht sicher inwieweit das die Ausführungszeit beeinflusst.
Was ich sehr interessant finde ist, dass sich die Ausführungszeit verändert wenn man die Eiungangsbedingungen ändert.
Hier waren sowohl der Kreismittelpunkt als auch der zu checkende Punkt völlig offen. Besetzt man diese Variablen kommen je nach Ergebnis andere Werte raus.
Für die die zu faul zum tippen sind hängt das Programm, mit Source, als Anhang dran.
Viele Grüsse

[alzaimar]

Zitat:

Zitat von R2009

Was ich sehr interessant finde ist, dass sich die Ausführungszeit verändert wenn man die Eiungangsbedingungen ändert.

Nun ja, ist nicht anders zu erwarten, denn der Ausführungspfad ändert sich auch (es kommen z.B. weitere Prüfungen hintu).

Immerhin sieht man, das man eben doch ab und zu mit Assembler noch etwas herausholen kann. In vergangenen Challenges (Textsuche, Arrays, Strings etc.) war das nicht bzw. nur marginal möglich. Hier (bei Berechnungen) kann man aber einen Compiler u.U. noch optimieren...

Ach, eine kleine Kritik (die aber nichts am Ergebnis ändert): Du vergleichst Äpfel mit Birnen, da die Funktionsresultate unterschiedlichen Datentyps sind.

Weiterhin ist der Aufruf der 'Sign'-Funktion in Version #2 +überflüssig, denn man prüft eh auf '<0' und '>0'.

[himitsu]

hier ließ sich nur viel mit ASM optimieren, da der Compiler die Variablen und Zwischenergebnise einzeln verwaltet und ich hier Vieles in sich selber belassen konnte,
also die ganze Berechnung komplett in die Register verlagert hatte, wärend der Compiler oftmals Zwischenergebnisse auf dem Stack ablegt (mir haben praktisch 4 Register gereicht, wärend Delphi mit allen Variablen und temporären Variablen, für Zwischenergebnisse, auf über 4 kommt ... wobei standardmäßig eh nur 3 Register frei veränderbar sind)

beim Suchen dagegen braucht man nicht viele Register, da dort eh vieles außerhalb (im RAM) abläuft ... also reinladen/vergleichen und das kann der Compiler selber schon ganz gut.

[R2009]

Hi,

R2009

Zitat:

Was ich sehr interessant finde ist, dass sich die Ausführungszeit verändert wenn man die Eiungangsbedingungen ändert.

Meine Aussage:
Bezieht sich auf die Parameter die übergeben werden. Die Ausführungszeit ändert sich wenn z.B. wenn der zu testende Punkt innerhalb des Kreises liegt relativ zu dem ausserhalb liegenden Punkt.

Viele Grüsse!

[himitsu]

Zitat:

Bezieht sich auf die Parameter die übergeben werden. Die Ausführungszeit ändert sich wenn z.B. wenn der zu testende Punkt innerhalb des Kreises liegt relativ zu dem ausserhalb liegenden Punkt.

bezieht sich das auf alle Versionen oder nur auf die mit Fließkommaarithmetik?

bei den Integerversionen sollte sich nicht groß was ändern, da egal wie die Werte sind die Berechnungen "etwa" gleich schnell sein sollten. :gruebel:

[R2009]

Hi himitsu,

bei der ASM Version hab ichs nicht probiert. Ansonsten bei allen!

Viele Grüsse.