Geography Example

Let's model the real world (literally). How would you make a reasonably spherical map for a simulation of the real world using a procedural language and relational tables? The map needs to be evenly divided into 2000 equilateral triangles. Each element in the simulation will occupy one and only one triangle. From any triangle we need to be able to find its immediate neighbors. Please show how the associations are generated in addition to the empty schema.

Ever play "Civilization"? I love that game, but it's on a rectangular map. The north pole is as wide as the equator. I'm writing my own twist on that game, and I need a map that's spherical enough to allow ICBMs to change who can attack who by just going over a pole. I still want the map to be a grid, like the original game. That's the big use case. It inherits an untold number of use cases from "Civilization".

Compare and contrast with CampusExample, HexGridSphere, and HexGridIcosahedron, noting variables like complexity, familiarity, and representation of physical world or abstract domains.

No special knowledge about spheres or maps beyond high school geometry and geography needed, including familiarity and ability to use a globe. No trigonometry required at all. This isn't rocket science. There are a few areas that can trip up a simplistic design.

Are there UseCases to constrain the requirements? It almost sounds like spherical finite-element simulations. A visual tool would help explore such a problem space better than code.

It's more difficult than it seems at first, at least if you keep thinking in latitude/longitude. The obvious solution (divide globe into 8 triangles of 90 degrees each, then subdivide at the 45 degree marks and repeat) won't work, because the Earth is a sphere. The vertical sides will be cut by 1/2, but the new base of the triangle will be cut by 1/sqrt(2), as it's dependent on cos(latitude). Thus we get isosceles triangles instead of equilateral. --JonathanTang''

Paradigmatic Comparisons

[An] OO language makes it easier for me to manipulate the abstractions. The programmer can create maps, spheres, neighbors, triangles, visitors, etc. and find out what behavior they should have. How would this be modeled with relational tables in a procedural language?

In the object-oriented paradigm, it is NOT necessary to populate all the cells in advance. You can use lazy evaluation to create the cells as needed.

Relational Database Schema

Table: location --------------- locID locTitle longitude latitude locType (city, tourist stop, etc.) locPopulation

Table: region -------------- regnID regnTitle regnType (country, state, province, etc.) centerLongitude centerLatitude regnPopulation (if applic.)

Table: path ------------ pathID pathType (river, road, boundary, etc.) pathTitle leftRegionRef (f.k. to "region" table, if boundary) rightRegionRef

Table: vector (a line segment) -------------- vecID pathRef prevVectorRef (prior vector node) toLongitude toLatitude

Use a many-to-many table: (this applies to triangle version only)

Table: neighbors -------------- triangleRef neighborTriangleRef

[Possibly an application for an AdjacencyGraph.]

A simple SQL statement for discovering the adjacent triangles is implied:

select * from neighbors where triangleRef = $triangleID

If the number of neighbors is fixed, then a variation is given below.

Questions remain, however. How is the table populated? There seems to be constraint that each triangle is equilateral? A query for a specific neighbor (by some criteria) is not possible.

The data, once generated, is static, but it has to be populated somehow. 2000 triangles is 6000 neighbors. How would you populate the table using a procedural language? Start by dividing the globe into 8 triangles at the 90 degree marks in the Northern and Southern hemipsheres. These are all equilateral, as their sides are great circles (meaning a degree has a constant length), and each side is 90 degrees.

Triangular variation

Neither the triangular nor hexagonal variations meet the requirements. They don't produce cells of the same shape and size for the entire map.

For each triangle, pick the midpoints of the sides, and then connect them with great circles. This divides the triangle into 4 smaller subtriangles.

As each side has been cut at its midpoint, we know that the center triangle is still equilateral (the sides are great circles, so they're "straight" lines and we can use degrees as a useful distance measure). According to SphericalTrigonometry, its sides are each 60 degrees in length. Its three angles are equally acute (but greater than 60 degrees).

The three corner triangles are not equilateral. Each corner triangle has one 60 degree-long side, and two 45 degree-long sides. Each corner triangle has one 90 degree angle and two acute angles.

The four triangles actually look nothing like triangles on a Mercator projection (the horizontal crosspiece will bulge upwards, and the diagonal sides will bulge inwards), but that's because the sum of the angles don't equal 180 degrees on a sphere.

Additional refinements for Greater Accuracy.

The map won't have exactly 2000 triangles. To cover the sphere with this procedure, you need a multiple of 2 * 4^n triangles. A matrix of 2048 triangles works, though that's only 32 triangle edges from the North to South poles. Most games use at least a 128x128 matrix, so for something equivalent you'd want 32,768 squares. These refinements may be beyond the scope of the requirements for this example.

Equal-area almost-triangular variation moved to HexGridSphere.

The Right Shapes

A grid of squares might be simpler than triangles on a sphere. Squares are possible, but you can't project them directly onto a sphere. Then area of each cell has to be equal. Triangles can be projected directly onto an icosahedron, and that's spherical enough to satisfy the use cases.

Why not hexagons? They are more consistent in their neighbor patterns than triangles and can cover a sphere smoothly and with equal sizes I believe.

Hexagonal Variation moved to HexGridSphere.

Examining Object Behaviors

The app can ask triangles for neighbors by compass direction. Half the triangles have southern neighbors, the other half have norther neighbors. All of them have eastern and western neighbors, since the poles of the sphere are on vertices.

A visual, scaled down to a 6 triangles N-S, so it would fit. Pretend that there are horizontal crossbars on every row.

. a/\ /\ /\ /\a . /\/\ /\/\ /\/\ /\/\ . /\/\/\/\/\/\/\/\/\/\/\/\(equator below this line) . \/\/\/\/\/\/\/\/\/\/\/\/ . \/\/ \/\/ \/\/ \/\/ . \/ \/ \/ \/

[I added dots to the left side to reduce WikiFormattingDrift?]

Each diamond is a 90 degree arc of the globe. The right edge wraps around to the left - if you're at point a on the right side, you're also at point a on the left. An edge to the diamond is a line of longitude. And triangles on the edges of the diamonds still have 3 neighbors - for example, the top of the leftmost diamond has the top of the second diamond and the top of the rightmost diamond, along with the triangle beneath it, as neighbors. --JonathanTang

A Survey of the Relational Space

If the neighbors are a fixed number (3), then perhaps we can do something like this:

Table: triangles -------------- triangleID centerLongitude centerLatitude topRef (triangle IDs of neighbors...) leftRef rightRef bottomRef

If one is not applicable, then it is null/zero. If you want to know the top neighbor of a given triangle:

select topRef from triangle where triangleID = $triangleID

Questions on Data Sources

Geography will be generated algorithmically. All we're dealing with now is how to generate the map that the continents, oceans, rivers, mountains, etc. will occupy. Where does the geography, (elevation, terrain info, rivers), flora, fauna (including us and our cities, roads, mining, etc.), weather capable of mini ice ages, come frome? Would the freely-available USGS map data be applicable?

  Table: triangles
  --------------
  ...(see above for other fields)...
  elevation
  terrainType  (ocean, land, city, snow....)
  floraLevel
  faunaLevel

one of these records for each corner in the globe:

Table: point ------------- id latitude longitude

Each cellid would relate to 3 pointids

Table: cellpoints ------------- cellid pointid

you can then relate anything you want to a cell

Table: somefeature ------------- somefeatureid cellid somefeaturedata

Right away serval possibly useful queries can be asked of the data. What cell is a certain latitude and longitude in? find the three nearest points, and find the cell with those three points. What cells are adjacent to a certain cell? Find all cells that share two points with your cell. What cell is adjacent in a certain direction? Requires enough math to make for a messy query, but doable.

The procedural side is easy too. You have a function that creates your sphere: Create a point at each pole and four point equally spaced along the equator. Create the eight valid cells that form the surface. Between each pair of points find the point halfway between them. With these points, divide each cell into four. Repeat until you have the desired number of cells. If you are feeling cocky, start with a shape that looks like a 20-sided die instead.

Geometry Lesson

The first solution (an octahedron) is too far from a sphere to project without significant distortion. An icosahedron (the 20 sided die) works much better. How would you write the procedural algorithm for one of those?

The "repeat until you have the desired number of cells" part. This algorithm (which apparently me and this poster figured out independently; I'm not the one who wrote this solution) can give you an arbitrary-precision approximation of a sphere. Am not entirely sure the icosahedron works out in the general case; the problem is subdividing triangles when the edges must be great circles. I'll try to do a FunctionalProgramming example of how to populate the code a bit later. --JonathanTang

Repeatedly subdividing the 8 sides of an octahedron doesn't produce a better approximation of a sphere, just more cells in an octahedron.

No; you're confusing how a figure looks in 3-space with how it behaves mathematically. Just because an icosahedron looks less distorted when we build one does not mean it's less distorted than an octahedron (BTW, I'd argue that my solution isn't an octahedron at all, because the faces are not flat.) A spherical surface cannot be deformed into a flat plane at all, though you can approximate it as the size of the triangles approaches zero. See, I wasn't completely asleep in general relativity. ;)

A sphere is made out of 8 equilateral triangles - each triangle has a side length of pi*r/2, and 3 angles of 90 degrees each. The algorithm we gave then divides each triangle into 4 triangles, completely covering the original, with side lengths of pi*r/4 and a total angle measurement of somewhere between 180 and 270 degrees. For it to be a "triangle" on a sphere, the sides all have to be geodesics (great circles). That's why neither an octahedron nor an icosahedron's a good analogue for this problem. The sides on those figures are all straight in 2-space, so they can only approximate their 3-dimensional analogues as the side size become infinitesimal in relation to the whole surface area.

I believe an icosahedron could also represent a sphere in much the same way, but the math is much more difficult - certainly more than my measley brain can handle. You have to prove that all the sides are geodesics, and that they cover the sphere completely. Why bother when the triangular solution is just as accurate? --JonathanTang

It wasn't clear that the subdivisions were made on the sphere instead of the sides of the octahedron. If you subdivide the sphere you won't produce equilateral triangles. The vertices at the poles approach 90 degrees, the vertices at the center of each of the eight initial surfaces approach 60 degrees. A subdivided icosahedron is a good enough approximation to satisfy the use cases.

Now you have a globe for which you can map cellid to location, location to cellid, and navigate through adjacent cells. You can tell what is in each cell. Now you can write functions for any task you want to accomplish, like move something from one cell to another.

Geometry Lesson II

[Help Me!]

The triangles on the sphere cannot be perfectly equilateral, however they approach equilateral as the length of the sides approaches 0. By implication, increasing the number of triangles improves the approximation to a sphere. Similarly dividing a sphere into 6-sided figures does not give ideal hexagons. See for example the football (soccer ball in USA).

LOL. Yes, if every triangle side is 0 then all the triangles are equilateral. Not very useful for a game. Soccer balls are truncated icosahedrons. For a list of some possible polyhedral maps, see http://www.progonos.com/furuti/MapProj/Normal/ProjPoly/projPoly.html.

Implementation Details

An argument can be made that the implementation of move(somefeatureid, direction) vs. feature.move(direction) is simpler. In the former case, query for a bunch of ids, act on them, and forget about them.

Vectors Point the Way?

A "vector" approach which uses lines and polygon regions is arguably more general-purpose than a triangle grid or any cell-based grid. The vector approach can be mapped to triangles and perhaps any other representation or coordinate approaches. Triangles are just an implementation detail under that approach. For example, if all data is stored as triangle cells, the existing triangle data is useless for scaling up the resolution. Vectors and polygons can theoretically be generated on infinite triangles. It is similar to trying to scale bit-mapped graphics to arbitrarily high resolutions. For this reason many graphics libraries, such as the ones in Corel Draw, use vectors and polygons instead. The lines are smooth regardless of resolution. (Some sort of line-smoothing may be needed in some cases to avoid sharp angles.)

Heavily refactored by StevenNewton. I hope I've helped. Wow, I'm really impressed how this page has turned around -- thanks to everyone's contributions. Maybe I'll give OoLacksMathArgument a shot next.