SRL Archive - Suggestions

Before you say anything, I know there's FilterPointsDist, this is slightly different. FilterPointsDist removes points in a TPA that are within a distance range of another point where as FilterTPADist removed any points in the TPA that are within a certain distance of each other.

I used it in MSI's object finding to get rid of some overlapping TPAs (would get multiple points on one tree). Also works well with FindDTMs since the same DTM is sometimes found several times, all within 5 points of each other.

I'm just wondering if it's worth sending a pull request for. If not, it'll stay in MSI. :)

procedure FilterTPADist(var TPA: TPointArray; maxDist: extended);
var
  c, d, i, j, l, h: integer;
  newTPA: TPointArray;
  badElements: TIntegerArray;
begin
  l := length(TPA);
  h := high(TPA);

  setLength(badElements, l);
  setLength(newTPA, l);
  c := 0;

  for i := 0 to (h - 1) do
  begin
    if (i > 0) then // array elements are set to 0 by default
      if (inIntArray(badElements, i)) then // increases speed significantly
        continue;

    for j := (i + 1) to h do
    begin
      d := distance(TPA[i].x, TPA[i].y, TPA[j].x, TPA[j].y);
      if (d <= maxDist) then // if points are too close
        if (not inIntArray(badElements, j)) then
        begin
          badElements[c] := j; // new array of bad elements (indexes)
          inc(c);
        end;
    end;
  end;

  clearSameIntegers(badElements);
  setLength(badElements, c);
  c := 0;

  // set the new TPA
  for i := 0 to high(TPA) do
    if (not inIntArray(badElements, i)) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

I'm also not sure if, because I call methods like clearSameIntegers and inIntArray, it would cause problems.

Firstly, this should be in a plugin. No question.

I've made some optimizations to the code:

procedure FilterTPADist(var TPA: TPointArray; maxDist: extended);
var
  c, d, i, j, l, h: integer;
  newTPA: TPointArray;
  inBadElements: TBooleanArray;
begin
  h := high(TPA); // length(X) == high(X) + 1, this doing it this way saves an arithmetic statement
  l := h+1;

  setLength(newTPA, l);
  setLength(badElements, l);

  for i := 0 to h do
    badElements[i] := False; // just in case..

  for i := 0 to (h - 1) do
  begin
    if (badElements[i]) then // increases speed significantly
      continue;

    for j := (i + 1) to h do
    begin
      if (badElements[j]) then // increases speed significantly
        continue;

      d := distance(TPA[i].x, TPA[i].y, TPA[j].x, TPA[j].y);  // this could be modded to use L,W as well fairly easily 
      if (d <= maxDist) then // if points are too close
        badElements[j] := True;  
    end;
  end;

  c := 0;

  // set the new TPA
  for i := 0 to h do
    if (not badElements[i]) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

Basically, I removed a CRAPLOAD of iterations in your loops. Everytime you call inIntArray it will iterate through the entire array. This could be a *very* large number (>9000). Now, it will create a boolean array of the same length (easier on RAM since its only 4 bits vs. 8 per), then just check if the index has been invalidated. A simple boolean is *much* quicker than iterating through and doing arithmetic comparisons.

I do like this idea, but I feel like it needs a better name and to be plugin-ized.

Oh and if it goes in a plugin:

procedure FilterTPACustom(var TPA: TPointArray; compare: function(a, b: TPoint): Boolean);
var
  c, d, i, j, l, h: integer;
  newTPA: TPointArray;
  inBadElements: TBooleanArray;
begin
  h := high(TPA); // length(X) == high(X) + 1, this doing it this way saves an arithmetic statement
  l := h+1;

  setLength(newTPA, l);
  setLength(badElements, l);

  for i := 0 to h do
    badElements[i] := False; // just in case..

  for i := 0 to (h - 1) do
  begin
    if (badElements[i]) then // increases speed significantly
      continue;

    for j := (i + 1) to h do
    begin
      if (badElements[j]) then // increases speed significantly
        continue;

      if (compare(TPA[i], TPA[j]) then
        badElements[j] := True;  
    end;
  end;

  c := 0;

  // set the new TPA
  for i := 0 to h do
    if (not badElements[i]) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

{
  Filter by distance between points
}
function FilterTPADist(var TPA: TPointArray; maxDist: Integer);
function distComp(a,b: TPoint): Boolean;
begin
  Result := (sqr(a.x-b.x) + sqr(a.y-b.y)) <= sqr(maxDist); // lambda would be nice..
end;
begin
  Result := FilterTPACustom(TPA, @distComp);
end;

{
  Filter by L,W parameters.
}
function FilterTPADistEx(var TPA: TPointArray; maxL, maxW: Integer);
function lwComp(a,b: TPoint): Boolean;
begin
  Result := (abs(a.x-b.x) <= maxW) or (abs(a.y-b.y) <= maxL); // lambda would be nice..
end;
begin
  Result := FilterTPACustom(TPA, @lwComp);
end;

E: Just to clarify, I never compiled anything, but my theory should be correct. Also, I'm not sure if you have to dereference pointers in FPC code.. if so add the & if necessary.. I don't code enough any more.

I actually think the FilterTPACustom is a better idea than Coh3n's >.< and it incorporates it.

Thanks, I figured it could be optimized. Didn't think about a boolean array, and when I was testing it was always less than 50ms, but I think I tested with a max of 30 or 40 points, I can see how it would add up. Plus it would be a lot faster in a plugin. Why a plugin though, why not just add to Simba? Since they're TPA methods, they should be with the rest of the TPA methods.

From: Nava2
I actually think the FilterTPACustom is a better idea than Coh3n's >.< and it incorporates it.

Isn't it exactly the same as mine except is uses a custom comparison function? Or am I missing something? I too like the custom concept better.

I don't know when I'll be able to test, but I will as soon as I can.

E: You have if (inBadElements[]) then continue in both loops, is that necessary? E: Nevermind. :)

E2: Quick test implemented into MSI (MSI_Debug may add to the overall speed as it writes to a file):

[0:00:04]: [  ] -- MSI_Withdraw
[0:00:04]: [  ] ---- Found item in bank: Rune Hatchet
[0:00:04]: [  ] ---- MSI_FilterTPADist
[0:00:04]: [  ] ------ Length (start): 9
[0:00:04]: [  ] ------ Distance: 1
[0:00:04]: [  ] ------ Distance: 2
[0:00:04]: [  ] ------ Distance: 1
[0:00:04]: [  ] ------ Distance: 1
[0:00:04]: [  ] ------ Distance: 1
[0:00:05]: [  ] ------ Distance: 2
[0:00:05]: [  ] ------ Distance: 2
[0:00:05]: [  ] ------ Distance: 2
[0:00:05]: [  ] ------ Bad elements: [0, 1, 1, 1, 1, 1, 1, 1, 1]
[0:00:05]: [  ] ------ New TPA: [(455, 97)]
[0:00:05]: [  ] ------ Length (end): 1
[0:00:05]: [  ] ---- MSI_FilterTPADist: Done (63 ms)
[0:00:10]: [  ] ---- Withdrew Rune Hatchet
[0:00:10]: [  ] -- MSI_Withdraw: True

Speed difference just for fun. TPA length set to a million.

SRL Compiled in 15 msec
Coh3n: 39515
Nava2: 2793
Successfully executed.

Mine's obviously better. :spongebob:

From: Coh3n
Thanks, I figured it could be optimized. Didn't think about a boolean array, and when I was testing it was always less than 50ms, but I think I tested with a max of 30 or 40 points, I can see how it would add up. Plus it would be a lot faster in a plugin. Why a plugin though, why not just add to Simba? Since they're TPA methods, they should be with the rest of the TPA methods.

Yes, as I text you this morning, put it in Simba instead haha.

From: Coh3n
Isn't it exactly the same as mine except is uses a custom comparison function? Or am I missing something? I too like the custom concept better.

Yes which is slower, but I think that the solution is very elegant and would be very useful as well. Perhaps doing the two with the code directly in and having the custom one as well.

From: Coh3n
I don't know when I'll be able to test, but I will as soon as I can.

Why so rush? :)

From: Coh3n

E: You have if (inBadElements[]) then continue in both loops, is that necessary? E: Nevermind. :)

I thought the same thing, so I traced out the loops for about 4 iterations and it was necessary. Its because you compare *every* point to *every* other.

From: Coh3n

E2: Quick test implemented into MSI (MSI_Debug may add to the overall speed as it writes to a file):

.. snip

Speed difference just for fun. TPA length set to a million.

SRL Compiled in 15 msec
Coh3n: 39515
Nava2: 2793
Successfully executed.

Mine's obviously better. :spongebob:

Obviously yours is faster. :P Higher numbers means faster, right?

I actually didn't even think of the idea until later. I started doing it as trying to get rid of the one inIntArray inside the double loop.. then I realised it was redundant! So I did the boolean. I'm glad it works though.

Was that report out with mine or yours?

From: Nava2
Was that report out with mine or yours?

Yours. The 63 ms isn't much different than the original, I just figured because the array is so small, you can't notice the difference yet. Could have missed something plugging it into MSI, but I did double check.

Looks nice, perhaps we can include it in Simba?

From: Wizzup?
Looks nice, perhaps we can include it in Simba?

That was the idea of this thread. ;) Made it to see if it would be worth sending a pull request. Now I'll finally get around to setting up Lazarus on this computer. :stirthepot:

Isn't x*x faster then sqr(x)? My benchmarks say so…4940ms / 1000000 calls versus 4089ms / 1000000 calls.

Besides, this is the first language I encountered where sqr is square instead of square root.

There was a function that does this in WizzyPlugin. I used it in my yew chopper. Can't recall the name though.

EDIT: Used SplitTPA which doesn't filter so nevermind

From: ZephyrsFury
There was a function that does this in WizzyPlugin. I used it in my yew chopper. Can't recall the name though.

EDIT: Used SplitTPA which doesn't filter so nevermind

Good, you really upset me for a minute there. :p The only thing close I found was FilterPointsDist which filters points in the TPA close to a point given in the parameters, not other points in the TPA.

From: masterBB
Isn't x*x faster then sqr(x)? My benchmarks say so…4940ms / 1000000 calls versus 4089ms / 1000000 calls.

Besides, this is the first language I encountered where sqr is square instead of square root.

This very well may be true, something to look at as well.

procedure FilterTPADist(var TPA: TPointArray; maxDist: extended);
var
  c, d, i, j, l, h: integer;
  maxDist: extended;  
  newTPA: TPointArray;
  inBadElements: TBooleanArray;
begin
  h := high(TPA); // length(X) == high(X) + 1, this doing it this way saves an arithmetic statement
  l := h+1;
  maxDist2 := maxDist^2;
  setLength(newTPA, l);
  setLength(badElements, l);

  for i := 0 to h do
    badElements[i] := False; // just in case..

  for i := 0 to (h - 1) do
  begin
    if (badElements[i]) then // increases speed significantly
      continue;

    for j := (i + 1) to h do
    begin
      if (badElements[j]) then // increases speed significantly
        continue;

       if ((TPA[i].x-TPA[j].x)^2 + (TPA[i].y-TPA[j].y)^2)<= maxDist2 then // if points are too close
        badElements[j] := True;  
    end;
  end;

  c := 0;

  // set the new TPA
  for i := 0 to h do
    if (not badElements[i]) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

or that with x*x instead of ^2

My version of simba doesn't recognize ^2.

procedure FilterTPADist(var TPA: TPointArray; maxDist: extended);
var
  c, d, i, j, l, h: integer;
  maxDist: extended;
  newTPA: TPointArray;
  BadElements: TBooleanArray;
begin
  h := high(TPA); // length(X) == high(X) + 1, this doing it this way saves an arithmetic statement
  l := h+1;
  maxDist2 := maxDist*maxDist;
  setLength(newTPA, l);
  setLength(badElements, l);

  for i := 0 to h do
    badElements[i] := False; // just in case..

  for i := 0 to (h - 1) do
  begin
    if (badElements[i]) then // increases speed significantly
      continue;

    for j := (i + 1) to h do
    begin
      if (badElements[j]) then // increases speed significantly
        continue;

       if ((TPA[i].x-TPA[j].x)*(TPA[i].x-TPA[j].x) + (TPA[i].y-TPA[j].y)*(TPA[i].y-TPA[j].y))<= maxDist2 then // if points are too close
        badElements[j] := True;
    end;
  end;

  c := 0;

  // set the new TPA
  for i := 0 to h do
    if (not badElements[i]) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

e:
Not feeling like testing, but putting (TPA.x-TPA[j].x) in a var would make it slower right?

From: masterBB
My version of simba doesn't recognize ^2.

procedure FilterTPADist(var TPA: TPointArray; maxDist: extended);
var
  c, d, i, j, l, h: integer;
  maxDist: extended;
  newTPA: TPointArray;
  BadElements: TBooleanArray;
begin
  h := high(TPA); // length(X) == high(X) + 1, this doing it this way saves an arithmetic statement
  l := h+1;
  maxDist2 := maxDist*maxDist;
  setLength(newTPA, l);
  setLength(badElements, l);

  for i := 0 to h do
    badElements[i] := False; // just in case..

  for i := 0 to (h - 1) do
  begin
    if (badElements[i]) then // increases speed significantly
      continue;

    for j := (i + 1) to h do
    begin
      if (badElements[j]) then // increases speed significantly
        continue;

       if ((TPA[i].x-TPA[j].x)*(TPA[i].x-TPA[j].x) + (TPA[i].y-TPA[j].y)*(TPA[i].y-TPA[j].y))<= maxDist2 then // if points are too close
        badElements[j] := True;
    end;
  end;

  c := 0;

  // set the new TPA
  for i := 0 to h do
    if (not badElements[i]) then
    begin
      newTPA[c] := TPA[i];
      inc(c);
    end;

  setLength(newTPA, c);
  TPA := newTPA;
end;

e:
Not feeling like testing, but putting (TPA.x-TPA[j].x) in a var would make it slower right?

In this case, might be faster.

E: cleaner code is v=better in this case in my opinion.

Will using that rather than distance() really make that much of a difference?

Yes, a lot. That is like day and night difference. A CPU can do really fast plus/minus and multiply/dividing. Square root is very slow. And that is used in distance(p1,p2). The sqr() vs x*x also makes a difference. Cause it's an unneeded function call.

From: masterBB
Yes, a lot. That is like day and night difference. A CPU can do really fast plus/minus and multiply/dividing. Square root is very slow. And that is used in distance(p1,p2). The sqr() vs x*x also makes a difference. Cause it's an unneeded function call.

Good to know. So why not change distance() to not call sqrt()? Unless it's in the interpreter rather than Simba.

From: Coh3n
Good to know. So why not change distance() to not call sqrt()? Unless it's in the interpreter rather than Simba.

I will try to explain.

Distance() returns the distance between to points. So it basically does sqrt(sqr(p1.x - p2.x) + sqr(p1.y+p2.y));. As you know a square root is required if you want to know the distance. But it's not required if you want to compare distances. Then it's better to take the square of the distance you want to compare with. As seen in boreas his example. Then all we need to know is sqr(p1.x - p2.x) + sqr(p1.y+p2.y), you see, that is a huge optimization.

From: masterBB
I will try to explain.

Distance() returns the distance between to points. So it basically does sqrt(sqr(p1.x - p2.x) + sqr(p1.y+p2.y));. As you know a square root is required if you want to know the distance. But it's not required if you want to compare distances. Then it's better to take the square of the distance you want to compare with. As seen in boreas his example. Then all we need to know is sqr(p1.x - p2.x) + sqr(p1.y+p2.y), you see, that is a huge optimization.

Oh right right right! Genius. :p

I have a massive todo list for tomorrow night so I'm not sure if I'll get to this, but I'll try to test Boreas' version in MSI just to make sure everything works. If I have time I'll compare the speeds of different versions just for fun. :)

From: Coh3n
Oh right right right! Genius. :p

I have a massive todo list for tomorrow night so I'm not sure if I'll get to this, but I'll try to test Boreas' version in MSI just to make sure everything works. If I have time I'll compare the speeds of different versions just for fun. :)

You need to take more maths.. now. ;)

From: Nava2
You need to take more maths.. now. ;)

Meh, I understand it, I just didn't see it/didn't think about how distance() worked. :p Who need school. :rolleyes:

Yea, technically it's not even calculating the distance, it doesn't need to for a comparison. If A squared is more than B squared, then A is more than B (assuming a and b are both positive, which they are in this case). You don't actually need to know what A and B are.

In addition to the computer being better at multiplication than square roots, since MaxDist stays the same, I squared it outside the loop. So depending on how big the TPA is, it's one multiplication vs a crapload of sqrts.

Also, I was afraid ^2 wouldn't work, I confess I didn't actually check if it compiled.

So if you're squaring each term in the comparison, couldn't you remove the square altogether? You said if A squared is more than B squared then A is more than B, but why square to begin with? Alo, what if the points were negative?

The squaring is in case the numbers turn out negative.

Oh hah, duh. There's a basic math fail by Coh3n. Yeah I just referred to myself in the third person.

From: Coh3n
So if you're squaring each term in the comparison, couldn't you remove the square altogether? You said if A squared is more than B squared then A is more than B, but why square to begin with? Alo, what if the points were negative?

A is the distance. sqrt((x1-x2)^2+(y1-y2)^2)
A squared is the distance squared. (sqrt((x1-x2)^2+(y1-y2)^2))^2, or simplified (x1-x2)^2+(y1-y2)^2
B is the max distance
B squared is the MaxDist2

So we don't actually calculate A, just calculate the simplified form of A squared. We are given B, so we calculate B squared and compare it to A squared.

And we are allowed to simplify it because (sqrt(blah))^2 = blah when blah is positive, and in this case blah is the sum of x^2 and y^2, and squares are positive.

e:ninja'd

Yeah I understand. You're just using pythagorean theorem and maxDist is the hypoteneuse, which is given. I'm apparently a little slow after being away from school for a couple years. :p

Yall really hurt my brain =(

Then I realized what your talking about with this ^ >…> (In pascal it's a dereference)

From: Dgby714
Yall really hurt my brain =(

Then I realized what your talking about with this ^ >…> (In pascal it's a dereference)

I tried looking at some links in Google, and I don`t understand how this is dereferencing. Maybe I`m just not understanding dereferencing properly.

From: Dgby714
Yall really hurt my brain =(

Then I realized what your talking about with this ^ >…> (In pascal it's a dereference)

Nah we weren't talking about pointers. Simba will probably never support them.

From: senrath
The squaring is in case the numbers turn out negative.

Huh, what? I lost you there, the squaring is cause we need distance^2… The positive returns are just an extra.

From: masterBB
Nah we weren't talking about pointers. Simba will probably never support them.



Huh, what? I lost you there, the squaring is cause we need distance^2… The positive returns are just an extra.

In this case its both! Its one of the properties of the pythagorean theorem. :)

About the custom function, are you sure PS supports function pointers as parameters to imported functions? If so, I bet they could be used at some more points in Simba :)

From: Coh3n
I tried looking at some links in Google, and I don`t understand how this is dereferencing. Maybe I`m just not understanding dereferencing properly.

var
  p: ^int8;
begin
  p := GetMem(sizeof(int8));
  P^ := 5; //<--
  FreeMem(p);
end.

From: masterBB
Nah we weren't talking about pointers. Simba will probably never support them.



Huh, what? I lost you there, the squaring is cause we need distance^2… The positive returns are just an extra.

You should join IRC more >..< or at least read Simba update threads.
Lape, an interpreter, has Pointers =) (Will be replacing PS soon-ish?)

From: nielsie95
About the custom function, are you sure PS supports function pointers as parameters to imported functions? If so, I bet they could be used at some more points in Simba :)

I don't think it does. I know it doesn't from Plugins.

Sorry, my fault, just typed it in the reply box, been doing more spreadsheet stuff than scripting lately.