CODEWITHSUNDEEP
phpdictionarygeospatial
Josh
Josh

Reputation: 942

Algorithm For Determining Overlapping Geographic Areas

I have the latitude and longitude for a point for which I then compute circle using a radius to give a range. I also have latitude and longitude bounds of a geographical region (in this case a state). I'm trying to find out if any area of the circle intersects the any area region.

Basically the end result I'm looking for is if a point (geocoded address) is within x miles of any state it will return that state.

I'm sure there's some sort of algorithm to find this, but I don't know where to start looking.

Upvotes: 4

Views: 1889

Answers (4)

EPSG31468
EPSG31468

Reputation: 971

If your post would be tagged with Java and not with PHP, I wouldn't try to reinvent the wheel but just use JTS (Java Topology Suite), create one geometry and call the method

public boolean intersects(Geometry g)

I don't know much about PHP, so I can't tell you if there is a comparable library for PHP.

Where are the geometries from? You could also try to call some underlying functions, for example a database call, if your geometries are stored in a database like PostGIS

Upvotes: 0

Ina
Ina

Reputation: 4470

If you're trying to see if a single point is within a circle, you can use Pythagoras' theoy for. In the below code, pass the centre_x, centre_y and radius of your circle, and then the x,y for the point you're evaluating.

def in_circle(centre_x, centre_y, radius, x, y):
    square_dist = (centre_x - x) ** 2 + (centre_y - y) ** 2
    return square_dist <= radius ** 2

Upvotes: -2

tskuzzy
tskuzzy

Reputation: 36476

Use the Haversine formula:

a = sin²(Δlat/2) + cos(lat1)*cos(lat2)*sin²(Δlong/2)
c = 2*atan2(√a, √(1−a))
d = R*c

JavaScript:

var R = 6371; // km
var dLat = (lat2-lat1)*Math.PI / 180;
var dLon = (lon2-lon1)*Math.PI / 180;
var lat1 = lat1*Math.PI / 180;
var lat2 = lat2*Math.PI / 180;

var a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
var d = R * c;

This will give you the great-circle distance between any two points. The rest depends on how you represent the states.

Upvotes: 4

joshx0rfz
joshx0rfz

Reputation: 19

http://en.wikipedia.org/wiki/Quad_tree

This is an excellent starting point for any kind of 2-d spatial relationship kinda stuff.

Upvotes: 0

Related Questions