Page 1 of 3
Math Php question
Posted: Wed Nov 26, 2008 11:38 am
by shurik
Hello i have in my DB a table of points. each point has X and Y.
My aim is to find which point is the most distant point relatively to all the other points.
here is an example of some points:
As i already mentioned, my mission is to find the most faraway point from all the others.
in this case its point A.
the relativeness defined by the radius to the closest point as shown here:
and here it is for all the points
At first i thought to measure the distant from
each point to
all the other points, but i think maybe there is a better way to solve this problem.
Anyway, my table currently contains 3,000 points and it requires 3,000 * 2,999=8,997,000 measures just to know which point is the most distant from all the others.
This process lasts more that a minute.
Another problem is that during the calculations a new points are being inserted to the DB so i cannot allow this calculation to last more than a second.
If anyone has a good solution for me, it would be very nice
Thanks ahead.
Re: Math Php question
Posted: Wed Nov 26, 2008 11:47 am
by mintedjo
How long does it currently take?
Can i see some code too?
I doubt very much that i'll be able to contribute much but i'm curious to see what you do anyway. My guess is you do about 9billion pythag calculations

Re: Math Php question
Posted: Wed Nov 26, 2008 11:59 am
by shurik
no i use the formula of the distance between 2 points
i have the Xs and Ys of all the points remember?
imagine you have a lot of rats playing a game, the rat which will run faraway from all the others is the winner of the game, i want to find this winner:D.
just consider that there are always a new rats joining the game... and each one of them can change all the competition.
Re: Math Php question
Posted: Thu Nov 27, 2008 4:29 am
by mintedjo
Ok i can't help with your problem...
But can i point out that
me wrote:My guess is you do about 9billion pythag calculations
shurik wrote:no i use the formula of the distance between 2 points
i have the Xs and Ys of all the points remember?
What you are doing IS pythagoras. The only difference is that you are calculating the length of the sides before applying it.
Sorry I couldnt be of more help.
Re: Math Php question
Posted: Thu Nov 27, 2008 4:33 am
by shurik
yes this formula derives from pythagoras
Re: Math Php question
Posted: Thu Nov 27, 2008 5:07 am
by Eran
Once you calculate the distance between one point and another, you won't have to repeat that calculation, so for each point you calculate all the distances you will need to calculate for one less point the next time - for example for 10 points, you calculate 10 distances for the first point, 9 distances for the second point (as one of those has already been calculated) and so forth. If you keep those calculation in a organized look up table (an array) you can save some calculations.
However, that is still inefficient. What you can do is the following:
Once you calculate all the distances for one point, keep only the shortest distance. For the next point, if it has a distance to another point that is shorter than the previously shortest distance, you can stop calculating for that point (as it can already be eliminated as not being the farthest point from all others). If you find a point that the shortest distance calculated for it is longer than the previously shortest distance, that point becomes your baseline (as it farther than all other points than the previous baseline).
Hope I managed to explain it properly..
Re: Math Php question
Posted: Thu Nov 27, 2008 5:14 am
by VladSun
shurik wrote:As i already mentioned, my mission is to find the most faraway point from all the others.
in this case its point A.
[sql]SELECT pxls.x, pxls.y, sum(pow(pxls.x - other_pxls.x, 2) + pow(pxls.y - other_pxls.y, 2)) AS distanceFROM pxlsLEFT JOIN pxls AS other_pxls ON pxls.x != other_pxls.x OR pxls.y != other_pxls.yGROUP BY pxls.x, pxls.yORDER BY distance DESC[/sql]
PS: I think you can even use ABS() instead of POW() - that would be a first order distance and much easier to calculate.
Keep in mind that there may be two or more pixels wich have the same sum distance.
Re: Math Php question
Posted: Thu Nov 27, 2008 5:20 am
by shurik
pytrin wrote:Once you calculate the distance between one point and another, you won't have to repeat that calculation, so for each point you calculate all the distances you will need to calculate for one less point the next time - for example for 10 points, you calculate 10 distances for the first point, 9 distances for the second point (as one of those has already been calculated) and so forth. If you keep those calculation in a organized look up table (an array) you can save some calculations.
However, that is still inefficient. What you can do is the following:
Once you calculate all the distances for one point, keep only the shortest distance. For the next point, if it has a distance to another point that is shorter than the previously shortest distance, you can stop calculating for that point (as it can already be eliminated as not being the farthest point from all others). If you find a point that the shortest distance calculated for it is longer than the previously shortest distance, that point becomes your baseline (as it farther than all other points than the previous baseline).
maybe i forgot to mention but i need to find the most distant and also to rate later who the less distant and so on, so your method is not so efficient
Hope I managed to explain it properly..
Re: Math Php question
Posted: Thu Nov 27, 2008 5:40 am
by mintedjo
Just a thought...
If you are only interested in the greatest distance and the others are not really of any concern then why not simplify the maths to reduce processing.
Addition and subtraction are much faster than multiplications and powers so if you arent interested in the actual distance values and only the one which would evaluate to the largest value then to find the greatest distance you could just do
Code: Select all
(pxls.x - other_pxls.x) + (pxls.y - other_pxls.y)
The distance values will still evaluate to the same order
find the greatest value using this simpler formula and then if you really need to you can apply the full formula to the pixels that genrated the greatest value.
Re: Math Php question
Posted: Thu Nov 27, 2008 5:46 am
by shurik
VladSun
your solution i just like i said: it sum all the distants from all the points to all the other points and it takes 01:56 minutes to run this query... i am looking for a better solution, a faster one, and I'm sure there is.
Re: Math Php question
Posted: Thu Nov 27, 2008 5:49 am
by shurik
mintedjo wrote:Just a thought...
If you are only interested in the greatest distance and the others are not really of any concern then why not simplify the maths to reduce processing.
Addition and subtraction are much faster than multiplications and powers so if you arent interested in the actual distance values and only the one which would evaluate to the largest value then to find the greatest distance you could just do
Code: Select all
(pxls.x - other_pxls.x) + (pxls.y - other_pxls.y)
The distance values will still evaluate to the same order
find the greatest value using this simpler formula and then if you really need to you can apply the full formula to the pixels that genrated the greatest value.
this is a very clever thought. and it optimizes the calculating process but its still requires to measure all the distants between each point to all the others and its 9,000,000 calculations.
Re: Math Php question
Posted: Thu Nov 27, 2008 5:57 am
by mintedjo
May I ask how long your code takes to run if you do what i suggested?
Just curious how much it helped (if at all)
Also i dont think theres much else you can do to improve the performance if you want to be able to rank all the points. Without comparing every single point with every other single point you can't possibly find the distance between them.
I just realised (and i`m sure you did anyway, but) you will probably need to use abs() on the code i suggested
ie
Re: Math Php question
Posted: Thu Nov 27, 2008 6:01 am
by shurik
without your suggestion it was- 01:56 minutes
now its : 01:07 minutes
almost 40% improvement at run time
but still not enough.
as i said there can be new points added each second...
Re: Math Php question
Posted: Thu Nov 27, 2008 6:05 am
by mintedjo
How many points can be added each second?
could you not calculate the distance for each point as it is inserted?
Re: Math Php question
Posted: Thu Nov 27, 2008 6:09 am
by Eran
Did you try my suggestion? you can easily eliminate some points without calculate all the distances for them.