masterBB
2012-11-09 19:33:05
[INDENT][INDENT]FilterPointsPie[/INDENT]
[INDENT][INDENT]a road to a better function[/INDENT][/INDENT][/INDENT]
Hi there, I just created a few new ways of doing FilterPointsPie. My previous attempts at speeding this function up usually ended with a lot of messy code and a small speed improvement. My last attempt however was a lot better then my previous attempts. With this thread I will try to give you an insight in my head at how I worked and how this function worked out.
While reading through the simba source I noticed that FilterPointsPie used a ArcTan2 to translate the x and y coordinates to an angle. This angle was then compared to the start and end angle. This could of course be a lot faster.
The FilterPointsPie function:
How to improve is the question. Usually when you google the problem you are having the first hit is the best solution. I however always want to try them myself without help.
So I was doing my homework. I was calculating the powers and stress that an axis had to take in a stirling engine prototype(Yeah, I am following a study to engineer). I used vectors and vector cross products when I realized I could apply this to solve the problem.
[INDENT]
[/INDENT]
A is the place vector. It is the middle of the screen. Note that a place vector is almost the same as a regular point.
are the vectors which travel from the A to the outside of the circle. Though in this image I decided to draw the vector to the outer ring of the circle, in the code I use vectors with a length of one, because only the direction of the vector matters. Not the length. This is called a unit vector.
[INDENT]
[/INDENT]
Here you can see the vectors explained a bit. As you can see the vectors just exist out of an x and an y value. I added the x vector, this vector just shows a random point we could check for. To know if it is on the right side of the AB Vector we will have to solve the equation. If it is more then zero, it will be on the right side.
[INDENT]
[/INDENT]
As you can see there solving the vector cross product will split the founds points in half. Some of the red points are in the area we need. But none of the green ones.
[INDENT]
[/INDENT]
Note how using both vectors sorts out just the points we want. Well, the theory is done. Let's see the code that I wrote:
[INDENT][INDENT]a road to a better function[/INDENT][/INDENT][/INDENT]
Hi there, I just created a few new ways of doing FilterPointsPie. My previous attempts at speeding this function up usually ended with a lot of messy code and a small speed improvement. My last attempt however was a lot better then my previous attempts. With this thread I will try to give you an insight in my head at how I worked and how this function worked out.
While reading through the simba source I noticed that FilterPointsPie used a ArcTan2 to translate the x and y coordinates to an angle. This angle was then compared to the start and end angle. This could of course be a lot faster.
The FilterPointsPie function:
procedure FilterPointsPie(var Points: TPointArray; const SD, ED, MinR, MaxR: Extended; Mx, My: Integer);
const
i180Pi = 57.29577951;
var
G: TPointArray;
I, L, T: Integer;
D, StartD, EndD: Extended;
cWise: Boolean;
begin
T := High(Points);
if (T < 0) then Exit;
SetLength(G, T + 1);
L := 0;
StartD := SD;
EndD := ED;
while StartD > 360.0 do
StartD := StartD - 360.0;
while EndD > 360.0 do
EndD := EndD - 360.0;
while StartD < 0.0 do
StartD := StartD + 360.0;
while EndD < 0.0 do
EndD := EndD + 360.0;
cWise := StartD > EndD;
if cWise then
SwapE(StartD, EndD);
for I := 0 to T do
begin
D := sqrt(Sqr(Points[I].X - Mx) + Sqr(Points[I].Y - My));
if( D <= MinR) or (D >= MaxR) then
Continue;
D := (ArcTan2(Points[I].Y - My, Points[I].X - Mx) * i180Pi) + 90;
if D < 0.0 then
D := D + 360.0;
if (not ((StartD <= D) and (EndD >= D))) xor CWise then
Continue;
G[L] := Points[I];
Inc(L);
end;
SetLength(G, L);
Points := G;
end;How to improve is the question. Usually when you google the problem you are having the first hit is the best solution. I however always want to try them myself without help.
So I was doing my homework. I was calculating the powers and stress that an axis had to take in a stirling engine prototype(Yeah, I am following a study to engineer). I used vectors and vector cross products when I realized I could apply this to solve the problem.
[INDENT]
[/INDENT]A is the place vector. It is the middle of the screen. Note that a place vector is almost the same as a regular point.
are the vectors which travel from the A to the outside of the circle. Though in this image I decided to draw the vector to the outer ring of the circle, in the code I use vectors with a length of one, because only the direction of the vector matters. Not the length. This is called a unit vector.[INDENT]
[/INDENT]Here you can see the vectors explained a bit. As you can see the vectors just exist out of an x and an y value. I added the x vector, this vector just shows a random point we could check for. To know if it is on the right side of the AB Vector we will have to solve the equation. If it is more then zero, it will be on the right side.
[INDENT]
[/INDENT]As you can see there solving the vector cross product will split the founds points in half. Some of the red points are in the area we need. But none of the green ones.
[INDENT]
[/INDENT]Note how using both vectors sorts out just the points we want. Well, the theory is done. Let's see the code that I wrote:
procedure FilterPointsPie(var Points: TPointArray; const SD, ED, MinR, MaxR: Extended; Mx, My: Integer);
var
BminusAx, BminusAy, CminusAx, CminusAy: Extended; //don't let the type deceive you. They are vectors!
G: TPointArray;
I, L, T: Integer;
StartD, EndD: Extended;
Over180: Boolean;
begin
T := High(Points);
if (T < 0) then Exit;
SetLength(G, T + 1);
L := 0;
StartD := SD; //I still think this can be done more efficient, a while loop... Come on
EndD := ED;
while StartD > 360.0 do
StartD := StartD - 360.0;
while EndD > 360.0 do
EndD := EndD - 360.0;
while StartD < 0.0 do
StartD := StartD + 360.0;
while EndD < 0.0 do
EndD := EndD + 360.0;
if StartD > EndD then //Calculate if the difference is more then 180 degrees
Over180 := (EndD + 360 - StartD) > 180
else
Over180 := (EndD - StartD) > 180;
if Over180 then
SwapE(StartD, EndD);
//a is the midPoint, B is the left limit line, C is the right Limit Line, X the point we are checking
BminusAx := cos(degtorad(StartD - 90)); //creating the two unit vectors
BminusAy := sin(degtorad(StartD - 90)); //I use -90 or else it will start at the right side instead of top
CminusAx := cos(degtorad(EndD - 90));
CminusAy := sin(degtorad(EndD - 90));
for I := 0 to T do
begin
if (not(((BminusAx * (Points[i].y - MY)) - (BminusAy * (Points[i].x - MY)) > 0) and
((CminusAx * (Points[i].y - MY)) - (CminusAy * (Points[i].x - MY)) < 0)) xor Over180) then
continue;
G[L] := Points[I];
Inc(L);
end;
SetLength(G, L);
FilterPointsDist(G, MinR, MaxR, Mx, My); //TODO: move this to the MMLAddon section, this doesn't belong in FilterPointsPie
Points := G;
end;