Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

Cities within a distance of a ZIP Code

Posted on 2004-04-09
13
1,693 Views
Last Modified: 2012-08-13
The question is simple but I can't find the solution which should be answered in C++ or Visual Basic:

 After I get

a. A ZIP Code  and
b. A distance (miles)

How do I find all the cities that are lied within the provided distance from that ZIP Code?

* I already had
- The ZIP Code Lat/Long database
- City name corresponded to that ZIP Code



0
Comment
Question by:vtb2000
  • 4
  • 4
  • 2
  • +3
13 Comments
 
LVL 24

Expert Comment

by:fridom
ID: 10796057
Well a you have a center your ZIP code you then calculat a circle around and and see what other codes lies within that distance. I would pick a book about mathematics and check the chapter about trigonometry.

Regards
Friedrich
0
 
LVL 45

Expert Comment

by:sunnycoder
ID: 10796288
Hi vtb2000,

Friedrich has given you a way to go .. here is another ...

In questions of this kind, you can increase the response time of your program considerably by doing some preprocessing. Since you get the input at the beginning of the program, you can dynamically allocate a 2D array of dimension nXn where n is the number of cities ...

An entry [n][m] would indicate the distance from n to m ... the matrix will be symmetrical about its diagonal ... so you can compress it a bit if n is large ...

At  run time all you need to do is get n and m,  perform a  lookup and display the result

Since this sounds like a homework question, I am not providing you any code ... give it a shot ... if you get stuck, we are here to help

sunnycoder
0
 
LVL 84

Expert Comment

by:ozo
ID: 10796331
You can estimate the distance as
arccos(sin(lat1)*sin(lat2)+cos(lat1)*cos(lat2)*cos(lon1-lon2))*69miles/degree
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 

Author Comment

by:vtb2000
ID: 10797892
Thanks for all the answer so far:  I just would like to add something:

1. I can find the distance between one ZIP to another (but still thanks to Ozo).
2. However, there is over 50K of ZIP Code for US, or even worse, 780K of Postal code for Canada.

So if I calculation from one ZIP to 50K of other ZIP, find out the distance between each of the pair, sort them, and get the one that lies within the range, it would be ... tough. Let's say if make a Local Match Maker program, and about 100 people do the search at the same time then my server would run extremely slow.

So, what I am looking for IS ACTUAL CLEVER CODES that attacks this problem from another angle but so far which will reduce search time.  As for me, I am stuck.  

Please help!
0
 
LVL 84

Expert Comment

by:ozo
ID: 10798116
For a 50 mile radius, you could quickly eliminate anything furthir than 50/69 degrees away
0
 

Author Comment

by:vtb2000
ID: 10798127
Ozo:

Sounds like you got the perfect solution.  However, could you clarify it a little bit please.  Thanks!
0
 
LVL 84

Expert Comment

by:ozo
ID: 10798240
If the difference in latitude or longitude of the two cites is greater than about 50/69, you can skip that city with no furthur computation
0
 

Author Comment

by:vtb2000
ID: 10798281
Last questions to Ozo:

1. Has your fomular been tested yet?
2. What if the distance is 100, 200, 500, or greater?  Any ratio or fomular for that elimination check?

Thanks,
0
 
LVL 84

Accepted Solution

by:
ozo earned 90 total points
ID: 10798337
ignoring the oblateness of the Earth, one degree of latitude is slightly more than 69 miles, so check in the range ±100/69, 200/69, 500/69 for latitude
±100/(69*cos(latitude)) for longitude
0
 
LVL 1

Expert Comment

by:MortimerCat
ID: 10798729
Adding to previous suggestions:

Reduce the amount of processing by indexing your database by Latitude. You then only need process cities that lie within a band.

Pseudo Code:

Seek LATITUDE-10miles
Do





0
 
LVL 1

Assisted Solution

by:MortimerCat
MortimerCat earned 35 total points
ID: 10798811
Sorry, fingers slipped and I posted before I finished.

Pseudo Code

Seek Zip (LATITUDE-10miles)
Do
   Calculate Distance
   MoveNext Zip
While Zip<LATITUDE+10


Taking this further, create extra indexed fields Latitude & Longitude rounded to the nearest 5 degrees (possibly). This effectively divides the country up into a grid system. Then you would only need to process the cities that fall in the surrounding squares.


0
 

Author Comment

by:vtb2000
ID: 10799385
Final comments:

From a mathematical view points (I do need time to integraded your comments in). both Ozo and MortimerCat would best help to solve the problem.  So ... I love to split the points (90 for Ozo and 35 for MortimerCat).  Could it happen by EE system?

Please advise
0
 
LVL 1

Expert Comment

by:matticus
ID: 11455877
Quote: "For a 50 mile radius, you could quickly eliminate anything furthir than 50/69 degrees away"

This reduced my query time for smaller radii, but I noticed an increase in time when the radius reached 1000+. Has anyone else experimented with this technique?
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
topping3 challenge 14 90
Image decoding from Camera 3 96
Windows and other UI names - The Proper names for the Various elements! 1 106
Create .bat File 16 28
Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
Whether you’re a college noob or a soon-to-be pro, these tips are sure to help you in your journey to becoming a programming ninja and stand out from the crowd.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…

808 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question