spatial search & search radius circumference with Geokit

[Xin Zheng]

I am using Geokit to search for points within X miles of a location.

I would like to show this search region as a circular polygon in Google
Maps. For this I need a number of points around the circle's
circumference.

My original thoughts were to generate the boundary points myself, but
then my thoughts drifted to Geokit.

Geokit is computing the region already. Is there a way of exposing this
so I can get the boundary points?

Any help and advice is greatly appreciated.

I am going take a look under Geokit's hood to see if I can find a way.

 

[Bill Eisenhauer]

I am using Geokit to search for points within X miles of a location.

I would like to show this search region as a circular polygon in Google
Maps. For this I need a number of points around the circle's
circumference.

My original thoughts were to generate the boundary points myself, but
then my thoughts drifted to Geokit.

Geokit is computing the region already. Is there a way of exposing this
so I can get the boundary points?

Any help and advice is greatly appreciated.

I am going take a look under Geokit's hood to see if I can find a way.

Hello Xin,

GeoKit uses either the Haversine or Pythagorean formulas depending upon
whether you prefer the accuracy of a spherical Earth or just simply a
flat Earth. But these are just formulas that are applied within an
origin and a set of points.

Yeah, there is an implied circumference within which points may be
contained, but there's no internal representation of that needed or used
by GeoKit. There are formulas you can use to derive points on a circle
given a radius and a number of points desired. However, I haven't
researched this topic well enough to know how such would be applied to a
spherical Earth. All of that said, we could potentially roll some kind
of helper into GeoKit if needed. What would the API be?

Cheers,
Bill

 

[Xin Zheng]

What would the API be?

Hi Bill,

Thanks for the quick reply. It's fantastic you guys are so responsive.


The API could be:

data_with_location, radius_points = MappableModel.findall, rigin =>
[lat, lng], :within => distance, :return_radius_points => true)

I think it will be good having an option in the find method. I am not
sure how the radius points should be returned, as returning it to two
vars is unconventional.

radius_points = [[lat,lng],[lat,lng],...]

FYI. I am using KML with Google Maps. KML wants the coordinates like
this:
<coordinates>
-112.3372510731295,36.14888505105317,1784
-112.3356128688403,36.14781540589019,1784
-112.3368169371048,36.14658677734382,1784
-112.3384408457543,36.14762778914076,1784
-112.3372510731295,36.14888505105317,1784
</coordinates>

Perhaps radius_points can be an object with helper method to_kml:
radius_points.to_kml

What do you think?

 

[Bill Eisenhauer]

What would the API be?

Hi Bill,

Thanks for the quick reply. It's fantastic you guys are so responsive.


The API could be:

data_with_location, radius_points = MappableModel.findall, rigin =>
[lat, lng], :within => distance, :return_radius_points => true)

I think it will be good having an option in the find method. I am not
sure how the radius points should be returned, as returning it to two
vars is unconventional.

radius_points = [[lat,lng],[lat,lng],...]

FYI. I am using KML with Google Maps. KML wants the coordinates like
this:
<coordinates>
-112.3372510731295,36.14888505105317,1784
-112.3356128688403,36.14781540589019,1784
-112.3368169371048,36.14658677734382,1784
-112.3384408457543,36.14762778914076,1784
-112.3372510731295,36.14888505105317,1784
</coordinates>

Perhaps radius_points can be an object with helper method to_kml:
radius_points.to_kml

What do you think?

I'm not sure I would put this under "find". We will probably add it as
method to our Mappable module which will get mixed into a model.
However, it'll probably respond to some different type of method name to
isolate it away from database semantics.

Let me get with Andre and see what can come up with.

 

[Andre Lewis]

Hi Xin, here is an example of plotting a circle (from centerpoint and
radius) in Javascript :
http://www.ovationmarketing.com/GMaps/MapCircle.asp . You can find other
examples out there too by googling around.

I find it cleaner to calculate the points in Javascript since
calculating the points is primarily a display concern.

Cheers,

Andre

 

[Xin Zheng]

Hi Xin, here is an example of plotting a circle (from centerpoint and
radius) in Javascript :
http://www.ovationmarketing.com/GMaps/MapCircle.asp . You can find other
examples out there too by googling around.

Thanks for the link Andre. This is a lot easier to understand than the
xmaps (http://xmaps.busmonster.com/) code I was looking at.


I have now converted this into Ruby. Most of the time the circle polygon
I draw matches with the results returned from Geokit. But sometimes
results fall outside of it.

Here's my code:
def circle_points(center_x, center_y, radius, quality = 3)

points = []
radians = Math:I / 180

0.step(360, quality) do |i|
x = center_x + (radius * Math.cos(i * radians))
y = center_y + (radius * Math.sin(i * radians))
points << [x,y]
end
points
end

radius = miles * (360 / 24901.463)
where 24901.463 is the circumference of Earth in miles I'm using. I took
this from Wikipedia.

Are you using the same algorithm?

Are you using the same circumference?

Thanks for helping!

Xin

 

[Andre Lewis]

Are you using the same algorithm?

Since we don't have to plot points, we don't use this algorithm. We use
the Haversine formula in SQL to select all the points inside a circle.

Are you using the same circumference?

We define constants in mappable.rb for Earth's radius, etc -- you can
use those to be in sync with GeoKit.

Andre

 

[Clifford Heath]

Are you using the same algorithm?
Are you using the same circumference?

The algorithm using 360 degrees of sin and cos is
the most naive and inefficient one possible. Look
up Bresenham's algorithm for circles, and run it
for 1/8 of the circumference, using reflection and
rotation for the rest.

It's well known that Bresenham's works for straight
lines, but there's a cute version that does circles
and ellipses also, using pure integer arithmetic
and no multiplication or division.

Google finds plenty of presentations showing how.