Punkt innerhalb Kreis?

[quendolineDD]

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

[3_of_8]

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 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 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 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

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 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 von Medium:

Für eine einzelne Berechnung? Zigfach langsamer.

siehe mein [add] im letzen Post

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