narmi2

asked on

# Longitude & Latitude within a radius

Dear Experts

How do I work out the following:

If I have 11 sets of longitude and latitude co-ordinates on a world map. The first set of co-ordinates shows the center point of a circle on the map which has a radius of 10 miles, and the rest of the co-ordinates (the remaining 10), are random points on a world map. How do I know which of these 10 points are within the radius the radius of this circle without having to check all 10 points.

For example, I do not want to tell if to get point one, work out the distance, if it is within the radius, give me a true, get point two, work out the distance, if it is within the radius, give me a true and so on. that is what I do not want to do.

I would prefer if it is possible to somehow just know by looking at the co-ordinates to tell if they would fall within the circle or not.

Is this possible?

How do I work out the following:

If I have 11 sets of longitude and latitude co-ordinates on a world map. The first set of co-ordinates shows the center point of a circle on the map which has a radius of 10 miles, and the rest of the co-ordinates (the remaining 10), are random points on a world map. How do I know which of these 10 points are within the radius the radius of this circle without having to check all 10 points.

For example, I do not want to tell if to get point one, work out the distance, if it is within the radius, give me a true, get point two, work out the distance, if it is within the radius, give me a true and so on. that is what I do not want to do.

I would prefer if it is possible to somehow just know by looking at the co-ordinates to tell if they would fall within the circle or not.

Is this possible?

ASKER

So it is definately impossible to work this out without doing each point individually? My consern is when I will have to do this for millions or billions of points and the processing time will take too long.

So just to confirm, is it not possible to look at the structure of the longitude and latitude co-ordinates to figure out which co-ordinates fit into the circle?

If that were possible, then all points would not have to be calculated.

So just to confirm, is it not possible to look at the structure of the longitude and latitude co-ordinates to figure out which co-ordinates fit into the circle?

If that were possible, then all points would not have to be calculated.

Depending on where your circle is, you could eliminate points that are obviously too far away (because either their latitude or longitude is too far from the circle center's latitude resp. longitude).

ASKER

That sounds interesting. Could you please provide more info?

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

You say the circle is 10 miles radius.

Calculate the max and min latitude of circle.

Calculate the max and min longitude of circle.

If your point has lat or long outside this range it is outside circle.

Check the remainder of pts for distance

Reduces number of distance calculations

Calculate the max and min latitude of circle.

Calculate the max and min longitude of circle.

If your point has lat or long outside this range it is outside circle.

Check the remainder of pts for distance

Reduces number of distance calculations

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

What if I said that I will need a radius which will go upto 10 miles but generally it will be about 3 miles. Also, I will only need to draw this circle in builtup areas of the world. Those parts of the world which are buildings and roads. Does that exclude the poles? Does that make things easier? Does it make things more accurate. And yes, accuracy is important as long as long as co-ordinates within the circle are not missed. For example, if i set the circle to 4 mile radius, and it includes some co-ordinates which are 5 miles away from the center point that is ok. So what I am saying is, it should not miss any co-ordinates within the circle, but if it includes a few co-ordinates slighly beyond the circle that is fine.

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

I don't suppose you could help me put all this theory together? Or would that be another question with more points?

There's already a fair deal of the solution in this thread. You just have to decide how precise you want it, and then the method of calculating distances you want to use.

ASKER

Ok, I will try putting it together and will keep you posted on the progress.

Which method are you going for ?

ASKER

More or less exactly what you said in your post, i.e. cut out all or most of the co-ordinates which are too far leaving a margin for error, then use something more accurate on the few co-ordinates left to make sure they are in the circle.

So less precise method to remove most of the world leaving a margin around the circle, followed by something more accurate to do the rest.

So less precise method to remove most of the world leaving a margin around the circle, followed by something more accurate to do the rest.

I meant which formula for calculating a distance ;)

ASKER

Ah, you got me their.

My requirement is to be able to detect if a co-ordinate is within a radius (max 10 miles) on a map as fast as possible taking into account that eventually, the chosen formula will have to deal with millions of possible co-ordinates at any given moment.

So if I through 1000000 co-ordinates at this formula, it should tell me which of these co-ordinates are within the circle preferable within a second if not instant.

So, which formula would you suggest? Sorry about being so dumb about this, I'm not a maths expert...

My requirement is to be able to detect if a co-ordinate is within a radius (max 10 miles) on a map as fast as possible taking into account that eventually, the chosen formula will have to deal with millions of possible co-ordinates at any given moment.

So if I through 1000000 co-ordinates at this formula, it should tell me which of these co-ordinates are within the circle preferable within a second if not instant.

So, which formula would you suggest? Sorry about being so dumb about this, I'm not a maths expert...

ASKER

sorry about the typos...

Well, we suggested a few above. It's up to you to pick one, keeping our remarks in mind ;)

ASKER

Ok, first I need to get rid of co-ordinates for most of the world leaving the points within the radius and a margin around the radius to ensure all points inside the radius are included.

How do I do that?

Circle radius 5 miles

The center point of the circle is:

longitude: -105.564537

latitude: 37.768272

test point 1

longitude: -105.564655

latitude: 37.768340

test point 2

longitude: -115.664063

latitude: 62.754726

How do I apply a fast less precise formula to remove test point 2?

How do I do that?

Circle radius 5 miles

The center point of the circle is:

longitude: -105.564537

latitude: 37.768272

test point 1

longitude: -105.564655

latitude: 37.768340

test point 2

longitude: -115.664063

latitude: 62.754726

How do I apply a fast less precise formula to remove test point 2?

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

Ouch.

Looks like I will have to process all the points anyway. That is, even if the point is too far, I still have to run a calculation to find out if it fits or not. Is that correct? If this is true, will that not slow things down (make them twice as slow because 2 separate calculations are being done)?

For example, process all points (billions) and find all points which fit in the circle, THEN use more precise calculations to calculate the rest.

Would it not be faster to just process all (billions) or points with a precise calculation?

The ideal solution (seems impossible), would be to totally ignore points which will be too far from being looked at all.

Looks like I will have to process all the points anyway. That is, even if the point is too far, I still have to run a calculation to find out if it fits or not. Is that correct? If this is true, will that not slow things down (make them twice as slow because 2 separate calculations are being done)?

For example, process all points (billions) and find all points which fit in the circle, THEN use more precise calculations to calculate the rest.

Would it not be faster to just process all (billions) or points with a precise calculation?

The ideal solution (seems impossible), would be to totally ignore points which will be too far from being looked at all.

SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

Thanks, quick question before I continue.

If I have

lat: 0.000000

lng: 0.000000

and

lat: 1.000000

lng: 0.000000

How many miles are these 2 points apart?

And, will:

lat: 2.000000

lng: 0.000000

be double the distance of the previous 2 points?

If I have

lat: 0.000000

lng: 0.000000

and

lat: 1.000000

lng: 0.000000

How many miles are these 2 points apart?

And, will:

lat: 2.000000

lng: 0.000000

be double the distance of the previous 2 points?

ASKER CERTIFIED SOLUTION

membership

Create an account to see this answer

Signing up is free. No credit card required.

ASKER

Thanks! :D

The "just know" is done by calculating the distance between the center of the circle and the point. If that distance is smaller than the radius, then the point is inside the circle.

You will have to do this for all points ...

Here's a nice script that calculates distances on the Earth's surface :

http://www.movable-type.co.uk/scripts/latlong.html

(it also shows the Haversine formula used)