php - Finding Points in a Rectangle or Circle with mysql -

i have mysql database table list points co-ordinates (x,y)

i want find list of points fall inside rectangle. have been simple had 1 side of rectangle been aligned parallel or perpendicular axis. not. means rectangle rotated. have find points inside circle.

known data rectangle -coordinates 4 points known data circle -co-ordinates center , radius.

how query mysql table find points falling in rectangle , circle?

if matters front end using php.

a rectangle can defined 2 points representing opposing corners, eg: a(x,y) , b(x,y). if have point c(x,y) want test see if inside rectangle then:

if( (cx between ax , bx) , (cy between ay , by) )   point c in rectangle defined points , b else   nope endif 

a circle can defined single point c(x,y) , radius r. if distance d between center , point p(x,y) less radius r, inside circle:

and of course remember pythagorean theoreom, right?

c² = a² + b² c = sqrt(a² + b²) 

so:

d = sqrt( abs(cx - px)² + abs(cy - py)²)  if( d <= r )   point p inside circle center c , radius r else   nope endif 

edit:

the algorithm checking if point within polygon bit more complex i'd prefer write in sql query or stored procedure, entirely possible. it's worth noting runs in constant-time , lightweight. [requires 6 arithmetic ops , maybe 2 or 3 logic ops each point in poly]

to pare down number calculations required can write select points within rough bounding box before procesing them further:

where   x between min(x1,x2,x3,x4) , max(x1,x2,x3,x4)   ,   y between min(y1,y2,y3,y4) , max(y1,y2,y3,y4) 

assuming columns containing x , y values indexed might use few less cpu cycles doing math, it's debatable , i'm inclined call wash.

as circle can't possibly more efficient than

where   sqrt( pow(abs($cx - x),2) + pow(abs($cy - y),2) ) < $radius 

you're far concerned perceived cost of these calculations, write code , working. not stage performing such niggling optimizations.