brain teaser for the gurus

Ok, I have a very challenging brain teaser for the sql gods.

We have a very simple sql table that lists every city in the world,
like this

*cityname*, *lat*, *lon*
baltimore, 111.333, -38.3333
boston, 112.11111, -22.2222
rio , 23.01007 ,33.7233963
(etc, 3 million rows)

I am tasked me with writing a sql statement that will find all cities
that fall into 4 lat/lon coordinates Plygon (NOT a perfect square).

For instance the coordinates are:



lat1=23.01007 lon1=33.7233963

lat2=23.0183048 lon2=33.816658

lat3=21.9754562 lon3=33.8121071

lat4=21.9797649 lon4=33.7281723

Does anybody care to help here Any math math or geography people
in here?

On Fri, 22 Jun 2007 13:29:41 -0700, jamesd <jamesd@ring4freedom.com>
wrote:

>Ok, I have a very challenging brain teaser for the sql gods.
>
>We have a very simple sql table that lists every city in the world,
>like this
>
>*cityname*, *lat*, *lon*
>baltimore, 111.333, -38.3333
>boston, 112.11111, -22.2222
>rio , 23.01007 ,33.7233963
>(etc, 3 million rows)
>
>I am tasked me with writing a sql statement that will find all cities
>that fall into 4 lat/lon coordinates Plygon (NOT a perfect square).
>
>Does anybody care to help here Any math math or geography people
>in here?

Begin with a
SELECT * FROM cities
WHERE lat BETWEEN (smallest_lat,biggest_lat) AND lon BETWEEN
(smallest_lon,biggest_lon)

not to have to make computations on all the cities, only the possibly
relevant ones.

On this result set, you can apply a function that will compute if the
coordinates are inside the polygon.
Algorithms can be found there (or google : point inside polygon for
more)

http://local.wasp.uwa.edu.au/~pbourk...ry/insidepoly/

The solution will work if you take the sides of the polygon as
following the geodesics (and not for example the straight lines on a
flat map). I hope that's what you need, but if not please give
precisions about the geometry you are in.

So provided you have written your function is_inside(...) that returns
1 if the city is inside the polygon :

SELECT * FROM (
SELECT * FROM cities
WHERE lat BETWEEN (smallest_lat,biggest_lat) AND lon BETWEEN
(smallest_lon,biggest_lon)) AS tmp
WHERE
is_inside(lat1,lon1,lat2,lon2,lat3,lon3,lat4,lon4, tmp.lat,tmp.lon)=1;