Category Archives: All

Planet surface tessellation with irregular tiles. Part 2

Ocean segments

Actually, the ocean segments are almost the same polygons, about which we spoke earlier, only without the subtracted areas of the continents and small polygons merged with neighbors.

Some of the parts left after lands subtracting can be very small. Also, small polygons can be formed near the border of the ‘world’ polygon. We should add them to the neighboring sectors, so as not to spoil the overall picture.

Red lines in the figure indicate the desired merging of polygons.

desired merging

The choice of rectangles for merging with can be done in different ways. The project implemented two methods: by the longest border and by the nearest center. In the following image, the second method is applied.

ocean sectors

In general, we achieved what we wanted. The area of the sectors is approximately the same (on the sphere) and sectors are mainly convex with small exceptions.

Land segments

On the continents we can create a more interesting subdivision. It based, from one side, on generated small Voronoi polygons (base polygons), and, from the other side, on natural geographical objects such as rivers and watersheds. The obtained structure is very similar to the world’s subdivision into the states and provinces in them. That is, it is the process of the procedural generation of the world political map.

Unlike the ocean, convexity is unnecessary, and we should consider natural boundaries, other than land borders, as possible boundaries between sectors.

Watersheds in the project are not yet build, but there are already rivers!

As the first step, we create the Voronoi diagram of small area polygons for the selected land. In the project, each division of the global landmass is marked with the identifier aid (area Id) and can consist of a continent and nearest islands or only small islands located close by each other. The availability of areas and their identifiers can be determined from the content of the lands shapefile.

The average size of the base polygons is made as small as possible (it increases the computation time!). For the current example, we choose the average sector size of 40,000 km2 and the average size of the base polygons at 5000 km2. This is a rather large size chosen so only for clearness of the example.

In the picture there is a part of Voronoi diagram inside a land.

small Voronoi polygons

In practice, it is better to choose the average size of the base polygons in the interval 500–1000 km2. Smaller sizes are also permissible (up to several m2), but take into account the computation time and use a more suitable database configuration.

To merge base polygons into sectors, we randomly choose from them as much as we want to make separate sectors, and then gradually join remaining adjacent base polygons to resulting sectors.

In the picture an example of what we can get.

raw sectors

Now it is time to consider the rivers. We use the representation of rivers as two-dimensional linestrings, by which we can divide the initial sectors into parts (with ST_Split function). The river linestrings can be taken from riversz shapefile. Since we do not need the z-coordinate stored in that shapefile, we cut it off when importing shapefile to PostGIS enabled database.

Division of sectors by rivers can be performed depending on a number of conditions: the final streamflow of the river, the area of the separated sector part, etc.

After this division we will get many separate parts.

rivers cut sectors

Small parts of sectors (cuts) need to be attached to large sectors. But we must try not to attach parts to the same sectors from which they were cut off.

After joining, we will see the following picture.

land sectors

You might think that we have done everything that is required. But in fact it is not so, because there are still small islands. Those of them that have an area close to the average sector area are made as individual sectors right away. But with those whose area is much smaller than the average sector, we act in two ways.

1. If such islands are located relatively far from existing sectors, then we make them separate sectors. “Farness” here depends on the defined average sector area: the smaller this area the more likely that the island will become a separate sector.

2. If the island is close to other already defined sectors, then it merges with one of them. With the one that has the largest area in some polygon obtained with ST_Buffer of the island polygon.

On the next picture, four islands that have merged into two sectors.
2 sector archipelago

With an increase in the defined average sector size, these islands will fall into single sector.

Planet surface tessellation with irregular tiles. Part 1

Spherical tiling

Usually, the problem of dividing the sphere into tiles (tessellation) is solved seeking to obtain as much as possible a regular structure on the sphere. If there are few tiles, then a spherical polyhedra can be used. 20 is the maximum number of spherical divisions which can be achieved by a spherical icosahedron. And hosohedra is more often far from the desired.

There are derived methods.
1. Further fission of divisions can produce tessellation with a large number of tiles.
2. Using of semiregular polyhedra.
But the tessellation obtained by such methods is not always convenient in practice. It can completely consist of triangles, or it can consist of dissimilar elements. Imagine a strategic game with a tile map made up of triangles!

Now let’s take a look at this from the other side. What if the tiles must match some defined structure on the sphere?

We are dealing with whole planets and we want some tiles to be parts of the ocean and others to be parts of the continents. Usually, when creating tile maps, tiles are divided into the ocean and land ones, according to some principle, thereby determining the map content. And the resulting map has a resolution defining by the the number of tiles in the world map.

But, what if the division into the ocean and continents is already defined on the planet surface, and with a resolution far exceeding possible tile resolution? There may come in handy irregular tiles. Despite the name, irregular tiles may have imposed requirements. For example, there may be a convexity of tiles or an uniformity of size within certain limits.

On the plane such tessellation is, usually, made by using a Voronoi diagram. Here, we will see how to generalize this method to the surface of the sphere. And how the generated Voronoi polygons can be used to make ocean and land sectors.

We use the term ‘sector’ instead of ’tile’, since tiles are generally acting as elementary objects. But inside our sectors there are always an internal structure (terrain and geographic objects). Sectors can also act as elementary objects, serving as a tile map on sphere. For this purpose, a graph of possible transitions between sectors is also build.

SQL script constructing planet surface sectors. See also the tutorial on its use.

Polygons on planet sphere

Here, I give a description of how to partition the planet sphere into polygons using the arsenal of PostGIS tools. The only imposed requirements for polygons: convexity and uniformity of their spherical area with possible deviations of the order of the predetermined average area. Thus obtained polygons will be used to create sectors in the ocean and in the continents.

In the case of a flat map, one could break it into a Voronoi diagram of convex polygons, and could further use Lloyd’s algorithm to bring the diagram to ultimate form (Centroidal Voronoi tessellation). The essence of Lloyd’s algorithm is to repeat the creation of the Voronoi diagram, where at each iteration the centers of polygons obtained in the last iteration are taken as reference points for the new iteration.

In PostGIS there is a function ST_VoronoiPolygons, which builds the Voronoi diagram in a square area. Let’s see how we can use it for our purposes.

What will happen if we will try to use a straightforward approach? Any rectangular projection of the planet can be converted to a square by the coordinate transformation, then diagram is build, and then we can apply reverse coordinate transformation. But, the rectangles constructed will be stretched in one direction, which would be undesirable. And, if we will try to directly use Lloyd’s algorithm, polygons close to the poles of the sphere will have substantially smaller spherical area than those close to the equator.

Therefore, I offer another adapted method, which has not these flaws.

The random reference points for Voronoi diagram are chosen uniformly distributed on the sphere. In a Mercator projection, this means that they should appear less frequently towards the poles with probability proportional to the Cosine of the latitude. We construct the Voronoi diagram in the ‘world’ polygon, which is the entire planet projection or part of the projection of the planet. The ST_VoronoiPolygons function itself completes the rectangle to a square, we just need to subtract added space from the resulting diagram polygons.

The sample of the Voronoi diagram obtained by the proposed method is on the picture. Here is a part of the test planet map from the equator at the top to 73 degrees of south latitude at the bottom edge. And the lands are already subtracted from the Voronoi polygons.

Voronoi polygons

Apparently, in the Mercator projection, the polygons are usually have larger area when approaching the poles, but as spherical polygons they have the same distribution anywhere, this is what we wanted. But at the same time, the polygons have a very large dispersion in area and, because of this, the overall picture is unattractive.

Let’s try to apply the partial Lloyd’s algorithm. As new reference points for the subsequent iterations we select the centers of the polygons obtained by clipping with ‘world’ polygon. And, to prevent too much area reduction of polygons near the poles, we do only a small number of iterations (3 or so).

After applying such a modified algorithm, we obtain the following picture, which can already be acceptable.

Lloyd's algorithm

In the next post we will see how to make ocean sectors and, more interestingly, land sectors.

Change Log: 0.9

  • Possible tiling of the planet sphere with tiles of various polygonal form. Ocean sectors on the planet map (ocean_sectors shapefile).
  • Division of the landmasses into sectors taking into account rivers. Sectors can act as provinces of possible states (land_sectors shapefile). The procedural generation of the political map.
  • Graph of possible transitions between neighboring sectors (ocean_sectors_graph.dbf and land_sectors_graph.dbf files respectively).
  • The height contours of the example planets are moved to a separate archive.
  • Fixed bug in generation of LineStringZ rivers.

The Nishke II and Shkay II planets were updated.

The next few posts and tutorials will be devoted to the spherical tiling theory and practice.

Change Log: 0.8

  • Height contours in the contours shapefile. For the example planets, the contours were made at intervals of 200 and 250 meters; mlevel parameter specifies the height of a contour. For the present, contours are without smoothing.
  • The hlevel parameter value of the lakes is rounded down.

The Nishke II and Shkay II planets were updated.

The height contours are obtained without the use of Digital elevation model data (DEM), therefore they have their own distinctive properties.

The granularity of the contour data does not depend so much on position of the points. In the case of a traditional approach of getting contours from DEMs, their resolution vary significantly on the latitude. In the project, dependence on latitude and, possibly, on longitude is due to the method of cones to sphere mapping, but this dependence is not as great as in the former case.

The resolution of the contours is not limited by the generally accepted DEM formats, but only by the computational resolution of the planet, that is, by the parameters gn and ln.

If GeoTiffs are not required, but only height contours, then there is no need to produce a resource consuming DEMs generation operation.