image provider

State Finder

home page up jump to foot of page Google search web for more information on this topic Pinterest pin button
©1996-2017 Roedy Green of Canadian Mind Products

Disclaimer

This essay does not describe an existing computer program, just one that should exist. This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have prepared to help you is right here.

This project outline is not like the artificial, tidy little problems you are spoon-fed in school, when all the facts you need are included, nothing extraneous is mentioned, the answer is fully specified, along with hints to nudge you toward a single expected canonical solution. This project is much more like the real world of messy problems where it is up to you to fully the define the end point, or a series of ever more difficult versions of this project and research the information yourself to solve them.

Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; or give you any additional materials. I have too many other projects of my own.

Though I am a programmer by profession, I don’t do people’s homework for them. That just robs them of an education.

You have my full permission to implement this project in any way you please and to keep all the profits from your endeavour.

Please do not email me about this project without reading the disclaimer above.

The idea of this class is given a latitude and longitude, it returns the corresponding state in the USA. If you solve that, you might extend your algorithm to cover the globe and give country, state/province, county, city and borough.

This algorithm will eventually have all kinds of uses in e-commerce (calculate sales tax, shipping), in helping you find information of local interest such as weather reports, TV Guide, theatre listings, bus schedules, maps. With the advent of cheap handheld GPS (Global Positioning System) units, people will come to know their accurate latitude and longitude, even when traveling. It won’t be long before every laptop has a built-in GPS and thus knows where it is at all times. Already GPS systems are common in automobiles. You need algorithms to figure what you are close to on a map and to figure out your current time zone.

How might you implement such a lookup? You need digitized outlines of the states. These mathematically can be treated as polygons on a flat plane. Testing each state in turn using the standard is-this-point-inside-this-polygon algorithm would take forever. See PostScript or mathematical textbooks for how you would do this.

Here are five techniques to speed the process up.

  1. Use a simplified hanging moss algorithm no narrow down which states are possible candidates. Create a one-degree grid. At each intersection point list the states that overlap into that rectangle of the earth’s surface. This will usually narrow it down immediately to one state (and you are done), sometimes two or three. You will have to experiment to determine the optimum fineness of that grid.
  2. Use a simplified boundary polygon with perhaps only 10 sides to describe each state. Create an inner polygon totally enclosed by the state and an outer polygon, totally enclosing the state. If your point is inside the inner simplified polygon, you are done. If it is outside the outer simplified polygon, you know the point could not possibly be in that state. If the point is outside the inner polygon but inside the outer polygon, you then have to look at the detailed boundary outline polygon to decide.
  3. You can lay a fine grid over your detailed polygon and then create a series of little connecting polygons all around the perimeter. You then don’t have to compute all the points of the detailed polygon, just the ones in the fine grid intersection where the point you are looking up lives.
  4. You might search the literature for quad trees, a technique reported good for solving this sort of geographical classification problem.
  5. Consider using a distributed implementation. The database is spread over various servers, each specialising in a particular part of the globe. The client caches just the region of the planet they are currently in. As Terje Mathiesen said, Writing fast programs is always an exercise in caching.

There is a related problem, reporting deliberately inaccurate latitude and longitude, in a way that no one can figure out where you are to within greater accuracy than you intentionally reveal.

I suspect before long all laptops will come with a built-in GPS unit that lets the laptop know at all times where it is.

Big Brother will love the back door security holes in Windows to track the whereabouts of all Windows laptop users.

Perhaps, like the military controllers of GPS, you would want to restrict the outside world from getting too accurate a fix on your whereabouts.

We will have to think this one out carefully. People managed to defeat the GPS scheme used by the military to restrict accuracy by using extreme patience, possibly some sort of mass averaging of inaccurate readings.

One scheme might divide the globe into squares and only report the square someone is in. You need logic to prevent divulging extra information when someone is vibrating hack and forth over a boundary. It would make even more sense with political regions.

This page is posted
on the web at:

 http://mindprod.com/project/statefinder.html

Optional Replicator mirror
of mindprod.com
on local hard disk J:

 J:\mindprod\project\statefinder.html
Canadian Mind Products
Please the feedback from other visitors, or your own feedback about the site.
Contact Roedy. Please feel free to link to this page without explicit permission.

IP:[65.110.21.43]
Your face IP:[18.118.126.44]
You are visitor number