State Finder

This essay is about a suggested student project in Java programming. This essay gives a rough overview of how it might work. It does not describe an actual complete program. I have no source, object, specifications, file layouts or anything else useful to implementing this project. Everything I have to say to help you with this project is written below. I am not prepared to help you implement it; I have too many other projects of my own.

I do contract work for a living, which could include writing a program such as this. However, 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 any way you please.

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 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 timezone.

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.

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.
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.
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.
You might search the literature for quad trees, a technique reported good for solving this sort of geographical classification problem.
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.

	Please email your feedback for publication, errors, omissions, broken/redirected link reports and suggestions to improve this page to Roedy Green :
	Canadian Mind Products
	mindprod.com IP:[65.110.21.43]
	Your face IP:[38.103.63.61]	The information on this page is for non-military use only.
	You are visitor number 3,934.	Military use includes use by defence contractors.
	You can get a fresh copy of this page from:	or possibly from your local J: drive (Java virtual drive/mindprod.com website mirror)
	http://mindprod.com/project/statefinder.html	J:\mindprod\project\statefinder.html