Yeah, hello everyone. I'm very happy to see you. I was expecting five friends and five lost people, so it's much more. We are going to talk about Douglas Poiker.

And that is a very old system from the late 70s. And I have some update to share with you. So Douglas Poiker was used for reducing the number of points in a polyline. So when I talk about the polyline,

you imagine a line that seems to be a curvy line. But in fact, it's small segments of straight lines that are connecting by a point of noise. I use the name of points. But it's easy to reduce the number of points.

You throw one out of two or nine out of 10, and you have less points. But the shape of your polyline is destroyed. So you don't want to change the shape of the polyline.

So the Douglas Poiker algorithm says that you have to draw a baseline between the start and the end point. And when you do, you have done that. You search for the point that is the most distant from the baseline on the polyline.

And you keep that point, and then you separate your polyline in the left part and the right part, and you would do it again. And again, and again, and again. When do you stop?

Well, you stop when you have reached the maximum number of points. That is one criteria. And the other criteria is to stop when the error that you have, so the distance that you measure, is less than the maximum error that you want to have.

So this is an example of a polyline. And I'm applying the Douglas Poiker algorithm. So the red line is my baseline. And I'm looking for the point that is, at maximum, the fastest from the baseline. And that's the point there up.

So I keep that one, and I do it again here with the green baseline. I search for the bigger distance, and I keep that point. I do the same on the other part, and again, and again, and again.

So I just told you that there are two criteria when you stop the algorithm. Or you give a maximum number of points. I want to have only 1,000 points. Then you have 1,000 points, you just stop. And the other is when the distance that you measure

is less or equal to the maximum allowed. In each segment, of course, if you have your line and you have divided it in 1,000 pieces, you have to see that in each piece, the criteria is followed.

Douglas Poiker has one problem, maybe more than one. But this one is the annoying one. You have to apply the algorithm only when you know your last point. So if you imagine that you are tracking with a GPS

your trip to South France, you have to wait until you are in your destination point to start to reduce your number of points. Maybe if you have a small device,

maybe you have already exceeded your maximum memory. So it could be a problem. The results of Douglas Poiker are quite good. And probably, at least, the community says that it is the best.

And it is the best because the quality of the resulting polyline, the simplified polyline, is something that is very nearly what people can do. So we ask the people to do it by hand. And I will not say that they have chosen the same points. But the polyline that they have when it is simplified

is very comparable to the Douglas Poiker algorithm. So why do I need to update the Douglas Poiker algorithm? I can't wait until the end point.

And there are several reasons for that. And one of the reasons is that I can't store them all. The example going from here to South France with a small device, you probably will have not enough memory in a small device.

Maybe I cannot compute it fast enough when I arrive. Maybe I have a larger device going to South France. And when I set to my navigation system shut down,

it has to start all the computation. But I turn the key of my car, and the power is out. And it's too late to compute it. Another reason. Maybe I need to transmit the data. But transmitting the data, it's easy if you have a cable, if you have a Wi-Fi.

But when you are in your car, transmitting at every time that you have a point will cost you a lot on your GSM. Or if you have another example of transmitting, well, there is always a cost.

And why should you transmit all your data to throw it away afterwards? So you are better to have the updated Douglas Poiker and to throw it on the go. OK, I just told that about the data transmitted on a mobile network.

The cost is probably too high. But I can wait a little bit. So if I don't have the most recent data, it's OK. I can wait for a certain amount of time. So the Douglas Poiker W, W is me.

I have two types of points. And the one who I want to keep, I give them the name of essential point. And all the other points are observation points.

An observation point can be promoted to be an essential point. I don't create new points. I keep the essential one, and I throw away the observation point. Well, that's the bad thing about observation points. They are doomed to be promoted or dumped.

That's life of a point. So when you start, your very first point, well, it's like when you have a company. If you are the first one, you get promoted. You are CEO. Well, the first observation point

is immediately promoted to essential. And for the rest, it looks like a Douglas Poiker. That means I have to wait. And I wait until I have two observation points. So I have an essential one, and I have two observation

points. And then I apply something that looks like Douglas Poiker. I draw a baseline between the last essential point, that was the very first one, and the last observation point. And then it's like I'm looking from, so imagine there is here such a line.

I take the, I position myself at the last observation point, and I look to the last essential point. And I look through a pipe. So the form of the, it's a straight pipe, but the form of the pipe is completely up to you. You can choose a square pipe, or a round pipe, or oval pipe.

I don't care. You look in it, and if all your observation points are into the pipe, you have nothing to do. Then you take the next one, then the next one, and you still keep looking to the pipe. And if you lose one of the observation points

because it goes out of the pipe, that one is promoted to essential point. It's like in business. If you are that good, and you come out of the pipe, you are promoted to essential point.

So the form of the pipe is, in fact, your function about the distance. So if you are talking in two dimension, it's just a rectangle. And if you go out of the rectangle, you are promoted.

If you look in three dimension, then you can have the pipe. And the point that goes out of the pipe is promoted to essential point. All the other observation points that are behind or older than the new promoted one, sorry,

they are dumped. They will never be promoted. It is not necessary to keep them in memory. So you can dump it. And if you have to transmit your position, you transmit the new promoted essential point.

It's just what I told. Of course, it could be that if you need to follow, let's say, a truck, you want to be updated at least every half hour. Then even if the truck is on the straight line,

no point is being promoted. But just keep the last one promoted. It's just time. It's like in business. If everyone is retired, the guy who stays is promoted to be the new CEO.

And you do it again and again. So you have your last essential point. You have or you not have observation point. But each time that you have a new one, you just do the new algorithm again. You look in your pipe.

If there is one out, it's promoted. So that's nice. But if you are in a very, very long, straight road, like the one between San Francisco and Los Angeles or Las Vegas, I've not been there.

But it seems to be a very long, straight line. Or if you are in a train in Australia, there is something like 600 kilometers straight rails. Maybe you need to have a maximum buffer size. And it's just like the time interval.

If your buffer is nearly full, promote the last one, dump the others. And yeah, that point is just lucky. And you keep it. All right. What are the results of the updated Douglas-Poyaker?

Well, you have a little bit more points than in the Douglas-Poyaker. And you have nearly the same quality, which is not a surprise. Because when you are doing that, you don't know what's coming.

And if you wait your endpoint, then, OK, it's easy to be better. It's not a big deal. You have to choose what you are going to do. And if you are little on your memory, then it's acceptable.

So you can just do the same with non-geographic data. It's a little bit harder to visualize. But I have done it with temperature. So you keep the temperature outside, for example. Well, most of the time, the temperature doesn't change.

So you don't need to keep every observation point. And if the temperature raise, because it's morning, the sun shines, then you will promote one of the observation temperature to essential.

And the idea is just the same. There are some problems in the updated Douglas-Poyaker. You must take into account that you could have straight lines. That can be quite long.

You cannot use the criteria with the number of points, because you don't know how long you will travel again after it. So the only criteria that you can apply is the maximum error criteria. So you have to choose an error. Your GPS has an error.

And if your GPS gives you an horizontal dilution of position, as it is called, of six meters, well, it's logic to have maximum error from at least

that value. Doesn't make sense. If your thermometer doesn't give you something better than one degree, you cannot think of it.

If your thermometer only gives you an accuracy of one degree, well, your maximum error must be greater. Otherwise, you don't know what you are doing. It's a little bit hard to make a demonstration of it. But I have a truck of a Swiss paraglider.

You know the paraglider? That's the guy with the kind of parachute. And not that the Swiss are better, or not as other people, but in Switzerland, they make some trips over the mountains. And so the problem is certainly a three-dimensional one,

because sometimes they just keep turning around to get altitude. And that is something that is a little bit weird if you are using the standard Douglas Poicke. If your maximum error is bigger than the circle,

it could be disappearing at a certain moment. But it looks like this. And it's only a part of it. It's a real flight. I have 899 observation points. And that is my polyline. So you see the circles here and there, and also 8

when he's trying to get some essential altitude gain. I have run the Douglas Poicke two-dimensional with a maximum error of 10 meters. And I have 347 points that are promoted.

If I do it without looking what comes after the point which I'm processing, so the DPW two-dimension, I have 375 points.

If I do it on three, you hardly see the difference. So when I said that the quality of the updated Douglas Poicke is nearly the same as the Douglas Poicke,

I'm not lying here. I will show you where the differences are. And the difference can most be seen in the straight line. So that is Douglas Poicke three-dimensional. And this is the updated one. Do you see the points that are changing?

There are some points changing, but the overall shape of the polyline is the same. So to put all the results on the line, I had 899 points with a maximum. I should have taken 900. It's not for one point.

Oh, just lie, but I cannot lie. Maximum error of 10 meters. And then you can see the differences. So I have 8% more points on the two-dimensional, and I have less than 1% more points on the three-dimensional one.

So I think it's a good idea not to have to wait until the endpoint of a polyline before simplifying it. And I think it will be more and more usable in a situation where you have to report your position

or if you have small devices. Think about a watch or a GPS smaller on your bicycle, also the smallest and lightest. So I made that in a sprint, so I have a lot of time

to answer your question. Who is going to put the first question? Yes. No, it is not used in practice.

I had a course about GIS in 2002 here at the VUB, not far from here. And when the prof was explaining the last part, he said, the problem is that you have the endpoint,

and there is no way. It is impossible to do it in another way. Yeah, impossible. That's a challenge. So I don't know what he said after that, because I was thinking it must be possible.

And I had the idea of the pipe. And afterwards, I put it on my ID on paper. I got back to him and said, hey, prof, I have something very interesting here. I think I have resolved the impossible problem. He had a look, and he said, oh, if you

think that it's workable, then you have to compare it to Douglas Parker, and you have to read all this. And he make a lot of copies of very interesting things that I had to read. And I read them. It took some time to understand what those people were

trying to explain. And it was only, well, it's not too bad. I don't want to diminish the error. But it was a way of accelerating the computation of the algorithm. But they didn't change anything on the algorithm itself. So I start to write something to show

that the quality of the modified Douglas Parker was nearly equal to the original one. Then I say, yeah, no, I'm going to be rich. I'm going to get a patent on it.

And a patent, if you have eight different points, you lost, well, people can use your ID into something else. So I said, I have to change. I have to go from 2D to three dimensional.

And that was a little bit more math. And I have other things to do. So I drop it after a while. And then I said, I will never be rich, not in that way. So I'm going to write in some scientific book or publication.

I got back to the professor. I'm going to write. Maybe I will not be rich, but I will be famous.

But the list of things that you have to do, and then I decide to share it with you today. OK, more questions? So I hope to see you again next year, again at FOSM, when I would like to talk about the same thing,

but about the temperatures and all the things that are not spatial related. And it will be probably in the embedded deaf room. So see you next year.