Math Php question

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

mintedjo wrote:How many points can be added each second?
could you not calculate the distance for each point as it is inserted?
it should be undefined amount of new added points.
i expect for 5-6 new points in second, but it could be more.
I don't believe it will be more than 50 (in second).
but generally it is unknown the amount of new points to be inserted
.
and it is not possible to ignore the new inserted points, because each new inserted point can change all the global distants and come become the most distant point itself or can make another point to be the most distant.
shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

pytrin

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
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Math Php question

Post by Eran »

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
Well you did forget to mention it.. if this is the case you can't avoid making all the calculations. Basically, I wouldn't perform this kind of process in PHP, rather use something like C or Java to handle it.
mintedjo
Forum Contributor
Posts: 153
Joined: Wed Nov 19, 2008 6:23 am

Re: Math Php question

Post by mintedjo »

pytrin has a valid point
c would probably go a bit faster

Do you NEED to calculate the values every second? Or is it more like the game u used as an example, where calculating at the end is sufficient?
shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

mintedjo wrote:pytrin has a valid point
c would probably go a bit faster

Do you NEED to calculate the values every second? Or is it more like the game u used as an example, where calculating at the end is sufficient?

i dont need to calculate it every second but i need to know any time which point is the most distant. that means when there are no new points, no new recalculations needed.
mintedjo
Forum Contributor
Posts: 153
Joined: Wed Nov 19, 2008 6:23 am

Re: Math Php question

Post by mintedjo »

Is there a reason you need to know? Or is it just so that when the points stop being added you dont have to do any more calculations?
User avatar
Eran
DevNet Master
Posts: 3549
Joined: Fri Jan 18, 2008 12:36 am
Location: Israel, ME

Re: Math Php question

Post by Eran »

This might be of interest:
Closest pair: plane sweep algorithm - http://www.cs.mcgill.ca/~cs251/ClosestP ... airPS.html
Fast marching algorithm for closest pair - http://www.cco.caltech.edu/~sean/closes ... osept.html
The last one is for 3d surfaces, but can be easily downgraded to 2d planes. It also has the algorithm in mock code.
shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

mintedjo wrote:Is there a reason you need to know? Or is it just so that when the points stop being added you dont have to do any more calculations?
i need to know each time which point is the most distant, if there were no new points added since the last time so there is no need of recalculation, but each new point can be the most distant by it self are can make another point to be the most distant.
mintedjo
Forum Contributor
Posts: 153
Joined: Wed Nov 19, 2008 6:23 am

Re: Math Php question

Post by mintedjo »

Ok i dont think you are going to get this to process in under a second unless you come up with something absolutely amazing.

I looked at one of the algorithms pytrin posted and that looks good, but your problem is the inverse of what that algorithm acheives. That being the case there is no way (as far as i can tell) to restrict the area of inspection quite so efficiently and hence no efficient way to reduce the number of points you need to inspect.

What is this for? I don't think I can help much more given the requirements but I'd like to know what you are building anyway.

Joe
shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

actually i am a coder in VB now im learning C and PHP+MYSQL
so i set a goal for my self to build something with a lot of information from database, loops, ifs, and so on. and i thought about comparing points. but then i bump into the math problem of solving this.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Math Php question

Post by VladSun »

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.
Yes, that's the "first order distance" I've mentioned ... But your expression is wrong ;) It should be

Code: Select all

ABS(pxls.x - other_pxls.x) + ABS(pxls.y - other_pxls.y)
shurik wrote: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.
I really doubt that any code that takes all the data from the DB, iterates over it and finally sort it (or a kind of) will be faster than the SQL solution.
How many records do you have, have you created the appropriate indexes?
Did you try first order distance?
There are 10 types of people in this world, those who understand binary and those who don't
shurik
Forum Newbie
Posts: 13
Joined: Wed Nov 26, 2008 11:06 am

Re: Math Php question

Post by shurik »

VladSun wrote:
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.
Yes, that's the "first order distance" I've mentioned ... But your expression is wrong ;) It should be

Code: Select all

ABS(pxls.x - other_pxls.x) + ABS(pxls.y - other_pxls.y)
shurik wrote: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.
I really doubt that any code that takes all the data form the DB and iterate over it and finally sort it will be faster than the SQL solution.
How many records do you have, have you created the appropriate indexes?
Did you try first order distance?
but its not enought to order the distance between 2 points.
you need all the distants. because i need to find the most distant point relatively to all the other points.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Math Php question

Post by VladSun »

shurik wrote:but its not enought to order the distance between 2 points.
you need all the distants. because i need to find the most distant point relatively to all the other points.
???

Read my posts again, please.
There are 10 types of people in this world, those who understand binary and those who don't
mintedjo
Forum Contributor
Posts: 153
Joined: Wed Nov 19, 2008 6:23 am

Re: Math Php question

Post by mintedjo »

VladSun wrote: ... But your expression is wrong ;) It should be

Code: Select all

ABS(pxls.x - other_pxls.x) + ABS(pxls.y - other_pxls.y)
I know, I followed up with a post correcting that.
User avatar
VladSun
DevNet Master
Posts: 4313
Joined: Wed Jun 27, 2007 9:44 am
Location: Sofia, Bulgaria

Re: Math Php question

Post by VladSun »

mintedjo wrote:
VladSun wrote: ... But your expression is wrong ;) It should be

Code: Select all

ABS(pxls.x - other_pxls.x) + ABS(pxls.y - other_pxls.y)
I know, I followed up with a post correcting that.
Sorry, I didn't see it.
There are 10 types of people in this world, those who understand binary and those who don't
Post Reply