# Efficiently transforming a series of points into curves to be serialized

I’m working on a video game where I need to display a map (in 2D) of an actual big European city (Paris, London, Madrid… that kind of big) and the player, displayed as a simple dot on the map, can take different routes while following the street lines.

To do so I extract real data from OpenStreetMap.org. Thanks to it I have access to a ton of data and geographic information, and among them I have street visual settings given as series of coordinates (long/lat converted to X/Y points using the right projection). In OpenStreetMap a street is composed of a set of points so drawing a line between these points is enough to display streets.

However it represents a huge number of points to load which means a lot of time spent processing the data which means: not ideal. For example, a big city like Paris is composed of 65.000 street points. That is huge. In order to reduce this number and still being able to draw / follow street curves I’m thinking about using a graph only composed of points implied in street intersections alongside curve equations to describe the street display. This way a street composed of 2000 points would be not much bigger than one composed of 10 points in theory.

# Example

In this example my initial set is composed of 13 points (red crosses) to display a street. What I’m aiming to in this case is keeping only 4 points (intersections with other streets) and an actual “equation” (or something similar) between each couple of points in order to reduce the size on disk of the final map.

This is where I’m stuck. I suck at Math (and regret it every day). So I can’t figure what would be the best way to transform a series of points into a simple equation that would allow me to follow the actual street curve at runtime.

I don’t know how to do it… I’ve read things about Bezier curves, about Clothoids, Circular Arcs… but I don’t know where to start, what is the best solution here, how to convert my series of points using one of these techniques, or if it’s really the clever thing to do in order to reduce the size (in bytes) of the map…

• keyword "linear regression" – ratchet freak Oct 17 '15 at 16:42

Streets can be pretty funky, with plenty of twists and turns. This can make it hard - or impossible - to describe one by a function of the form $$\y = f(x)\$$, where $$\x\$$ and $$\y\$$ are Cartesian coordinates. Polar coordinates, too, will often fail, no matter where you choose the origin. Therefore, I think your best bet is to create a parametric curve - that is, a relationship so that any point $$\(x,y)\$$ can be represented by functions of some parameter $$\t\$$:

$$(x,y) = (f(t), g(t))$$

When you're doing some sort of curve fitting like this, it's best to make $$\t\$$ proportional to the arc length $$\s\$$, which tells you where on the curve you are. You can then treat $$\t\$$ as the time it takes to move along the curve with some constant velocity (usually set to 1).

### Step 1: A good approximation

Let's say you have a series of ten points $$\\{p_1,p_2,p_3,p_4,p_5,p_6,p_7,p_8,p_9,p_{10}\}\$$ on your grid, each one with coordinates $$\p_j=(x_j,y_j)\$$. You want to create a curve $$\P(t)\$$ that contains them all. The curve starts at $$\p_1\$$, and goes from $$\p_j\$$ to $$\p_{(j+1)}\$$ until it reaches $$\p_{10}\$$, where it stops.

We need to figure out the time at which a person traveling on the curve reaches the next point, i.e. how far apart two points are. If they're close enough together, then a linear approximation is enough. In pseudocode:

$$p_1 = (x_1,y_1)$$ $$p_2 = (x_2,y_2)$$ $$d_x = x_2 - x_1$$ $$d_y = y_2 - y_1$$ $$dist = \sqrt{d_x^2+d_y^2}$$

We do this for each two points. If $$\P(t_1) = p_1\$$, then $$\P(t_2 - t_1) = p_2\$$, where $$\t_2\$$ is the linear distance between $$\p_1\$$ and $$\p_2\$$. We can set $$\t_1 = 0\$$, if we want, for the sake of simplicity - assuming $$\p_1\$$ is one of the endpoints.

After we've done this for all the points, we have three sets of numbers:

\begin{align}T =& \{t_1,t_2,t_3,t_4,t_5,t_6,t_7,t_8,t_9,t_{10}\}\\ X =& \{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,x_{10}\} \\ Y =& \{y_1,y_2,y_3,y_4,y_5,y_6,y_7,y_8,y_9,y_{10}\}\end{align}

and so at $$\t=t_j\$$, the curve is at point $$\p_j(x_j,y_j)\$$. Now we can interpolate. You can construct two Lagrange polynomials1, one each for the $$\x\$$ and $$\y\$$ coordinates, each in terms of $$\t\$$. The formula is simple enough, although it's obviously harder to do by hand.

We now have a parametric curve that describes all the points.

But wait! That still requires a lot of coefficients, and we're trying to reduce that. So why did we even do this?

### Step 2: Remove some points.

Let's say we only want to use four points. That's reasonable. I'll pick the endpoints and two others: $$\\{p_1,p_4,p_7,p_{10}\}\$$. Now, we can do the same thing as before. In fact, we could do the same interpolation we did in Step 1, by just finding the linear distance. And that's fine if you have a curve that only deviates a little from a straight line during each segment. However, that's often not the case. By simply finding the shortest distance between $$\p_4\$$ and $$\p_7\$$, we'd think that the two are a lot closer together, making the curve a lot different.

Therefore, we take what we did from step one. We find the length between these two points based on our interpolated curve $$\P\$$ that uses all ten. This can be done by just finding the arc length. I'd recommend using numerical methods for this. We then have three sets:

\begin{align}T =& \{t_1',t_4',t_7',t_{10}'\}\\ X =& \{x_1,x_4,x_7,x_{10}\} \\ Y =& \{y_1,y_4,y_7,y_{10}\}\end{align}

I use the primes to show that the times we've found are different from what we did in step one. They may be more accurate. Now we do the same sort of interpolation, just with four points.

We now have a parametric equation for the curve, using only four points. It's much less accurate than the first equation, but it uses much less data, and it guarantees that the curve will still pass through these four points (that's an issue with polynomial regression - only rarely will a best-fit curve go through any of the points).

Now, we could have skipped Step 1. I know, maybe you're disappointed. As I said before, we could just have used the linear distances between the four points. But that misses most of the finer details of the curve, and if you're shortening a curve from, say, 20 points to 6 points, skipping the first interpolation could really be costly.

1 A Lagrange polynomial (not parameterized) is of the form

$$L(x)=\sum_{i=1}^ny_ik_i(x)$$

where

$$k_i(x)=\prod_{m=0,m\neq i}^n\frac{x-x_m}{x_i-x_m}$$

Here's the reasoning behind Lagrange polynomials (in this case, there is no parameterization - $$\y\$$ is directly a function of $$\x\$$). You have $$\n\$$ points with coordinates $$\\{(x_1,y_1),(x_2,y_2), ... ,(x_n,y_n)\}\$$. You want to come up with a non-parameterized function $$\y = f(x)\$$. The simplest way to do that is to come up with a function with $$\n\$$ terms. At each point $$\p_j\$$, i.e. when $$\x = x_j\$$, all but one term - let's call it the jth term - will come to zero, and the remaining term will be equal to $$\y_j\$$. From there, it's simple to construct the second expression for any point $$\p_l\$$, and you simply add up $$\n\$$ terms, each corresponding to a different $$\p_l\$$, $$\x_l\$$ and $$\y_l\$$. This gives you the Lagrange polynomial for your set of points.

In your application of Lagrange polynomials to streets, we've done the same thing - just parametrically.

• Holly Macaroni! It took more than a year for someone to answer, but WHAT AN ANSWER! :) Thanks for the time spent writing this piece of knowledge. I'll try to implement and will probably get back at you soon. Thanks! – lvictorino Mar 16 '17 at 7:28