reduction of computation time

[storm11]

Hello,

I have been trying to speed up the following code. But, I can not think of a way to speed it up drastically. What the code does is that it goes through selected points (BINinfo[i].tpZ) in a set of points and then if any points fall within a set radius of a selected point then those points are then added to the selected point group(BINinfo[z].tepZ). The problem is that I am going through ~500,000 points and evaluating every single one of them. If there was a way to kick out of the loop when the distance was continuing to grow from the selected point in question that would significantly reduce the computation time.

Thank you any help is greatly appreciated.

A snip it of the code is below: (npts ~= 500,000, BINinfo[i].X are the X values, BINinfo[i].Y are the Y values and BINinfo[i].Z are the Z values)

int toomany=10; // if there are >10 returns than assume not road in a 2.5 ^2 circle
float size= 6.25; // buffer size "2.5^2" used to optimzie

for(int i = 1; i < npts; i++)
{
int startt, endt;

if(BINinfo[i].tpZ != 0)
{
double x=BINinfo[i].X;
double y=BINinfo[i].Y;

++j;
int c=0; //reset counter to 0

for (int t=1; t < npts; t++)
{
double x1=BINinfo[t].X;
double y1=BINinfo[t].Y;

if ( (BINinfo[t].tpZ != 0)&& (((((x1-x)*(x1-x)))+((y1-y)*(y1-y))) <= size) )
{
++c; //count how many pts are in the box
++h;
switch(c)
{
case 1:
startt=t;
break;

default :
endt=t;
break;
}

if (cc < c)
{
cc=c;
}

if (endt > npts)
{
endt=npts;
}

} //end if

} //end for

for (int z=startt; z < endt; z++)
{
if( BINinfo[z].X !=0 && BINinfo[z].Y !=0)
{

double x2 = BINinfo[z].X;
double y2 = BINinfo[z].Y;

if ( c > toomany && (BINinfo[z].tepZ != 0 ) && ((((x-x2)*(x-x2))+((y2-y)*(y2-y))) <= size))
{
++yyy;

BINinfo[z].tepZ = 0;

}

int returns=3; //number of returns to classify as road

if (c >= returns && (c <= toomany) && (BINinfo[z].tepZ == 0 ) && ((((x-x2)*(x-x2))+((y2-y)*(y2-y))) <= size) ) // if count is greater than return number and its in the circle and = 0 make it have its value back
{

BINinfo[z].tepZ = BINinfo[z].Z;

}

if (c < returns && BINinfo[z].tepZ != 0 && ((((x-x2)*(x-x2))+((y2-y)*(y2-y))) <= size)) //if count is less than return number and its in the circle and doesn't already = 0 make it 0
{

BINinfo[z].tepZ = 0;

}
}
}


} //end large if

[Moschops]

If there was a way to kick out of the loop when the distance was continuing to grow from the selected point in question that would significantly reduce the computation time.

Where in the code is the distance calculation?

if (distanceThisTime > distanceLastTime) break;

[storm11]

Ah, so I need to sort the structures first!

The distance calculation is: (it is embedded into the if statement)

(((((x1-x)*(x1-x)))+((y1-y)*(y1-y))) <= size)

[ne555]

¿And how would you sort them? You may use a kd-tree.
¿what's the purpose?