Generation of analytical surfaces on the example of maps

Introduction

There was once an interesting task: to organize the possibility of the program working with three-dimensional images of the earth's surface of large sizes. After studying a variety of literature and various sources, it became clear that effective approaches in the general access can not be found.

There is either complex mathematics, which still needs to be adequately transferred to the source code, or closed commercial products. Game algorithms for this task are not suitable, because it requires high accuracy and reliability of the results obtained.

Task

To be able to get height at any point, having two coordinates:

h = f (x, y);
')
Coordinates can be both geographic and linear. To be able to get heights with any step of coordinates within machine accuracy. Map sizes range from a few hundred kilometers to thousands, all the way to the whole earth. The operation of obtaining the height must have O (1) complexity and will be performed quickly enough for the graphics engine to work.

Initial data

The cards come in a variety of formats, so pre-processing was done. After processing, there is a contour map (irregular grid) of the earth's surface in a unified format:

<Number of points> <Height>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>

<Number of points> <Height>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>
<Latitude> <Longitude>
...

Or in numbers:

3 0.000000

32.071945 69.587814
32.074299 69.586975
32.070995 69.585907

4 0.000000

32.063576 69.578514
32.062050 69.578270
32.059124 69.578407
32.057785 69.579376

Isolines can be closed and consist of separate lines. Isolines are not allowed to intersect, although the approach used will also process incorrect data. Also in large numbers there are single points of height.

The content of the work

It was decided to split the entire work into three stages: data preparation, obtaining a uniform grid, and obtaining an analytical surface using spline interpolation.

In the first part, it is necessary to increase the resolution of the data provided in order to avoid conversion losses. Imagine a situation where you have points, some of them are connected by a line. This line ensures that the height along it is constant (Figure 1).

In the second part, the non-uniform grid is converted to a uniform one with the required resolution.

The stage of creating a spline surface from a uniform grid, the calculation of coefficients, correction values ​​completes the work.

At each stage, there are problems and peculiarities. All of them will be listed in the relevant sections.

Part 1. Data preparation

Introduction

All maps come with some scale. This parameter directly affects the number of parts that can be obtained (the spatial analogue of the Shannon-Kotelnikov theorem). The quality of the entire work will depend on the correctness of the data preparation.

The content of the work

Part 1. Data preparation
Part 2. Generating a uniform grid.
Part 3. Creating an analytical surface

Subtask target

Determine the most efficient detailing of the irregular grid, to preserve details.

Algorithms

This part uses a fairly simple approach to data processing. Suppose in some part of the map we meet several points. Some are connected and represent isoline. And one more point is located close to the isoline, but has a strong difference in height with it. During simple processing of points, after interpolation, the part of the isoline will change its height by something in between two heights (Figure 1). What do you think, what height will be at the point marked with a question mark? To avoid distortions at elevation changes, it is necessary to increase the number of points on the contour.


Figure 1. Initial data.

The best option is to set the resolution of the uniform grid at this stage. In this case, you can control the quality of the generated surface. Therefore, let us set the grid resolution and add all points to the isolines, so that all points of the isolines become inseparable.

The easiest way: linear interpolation . Simply add points to the contour using the Bresenham algorithm or the like.

A bit more complicated and demanding on computer resources spline interpolation on the plane. We used cubic interpolation . It is very important to use interpolation algorithms (new elements contain all given points), approximation (new elements are close to the original points) in this case will only distort the data. With high quality source data, even linear interpolation gives excellent results.

Processing results

After processing an irregular grid, its size on the disk increases, about 3-5 times, depending on the quality of the data. Graphically, the result looks like this:


Figure 2. Linear interpolation.



Figure 3. Spline interpolation with some steps.

When using spline interpolation (Figure 3), the line is not straight, as information on the position of the extreme points is taken into account.

findings

After pre-processing of the non-uniform grid, you can proceed to the second stage of the work - creating a uniform grid of high detail. You can see how many different data you need to process to get the result. Perhaps the use of various algorithms to obtain high-quality data.

The next part will show an interesting, very high-quality and simple algorithm for obtaining a uniform grid, which showed itself perfectly on large amounts of data.