Getting inspired by open software for a web site: g3n.fyi
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Bremer, Thomas
So you are here at FOSDEM in Brussels. Also sightseeing? Geocaching? Tried to optimize your way along the sights or to find many caches without making it a hike? Then you've got the traveling salesman problem! Famous in computer science because finding the optimum is extremely difficult and finding good approximations can be done easily. Last year we had a talk about 3geonames.org where the Hilbert curve was mentioned to be used in name generation. When researching about this space curve it turned out that such space filling curves give good approximations for the traveling salesman problem. This has already been evaluated scientifically. Route finding using thees curves is extremely simple. Other algorithms need much more computational effort. Using a space filling curve to find a route proposal and improving it with 2-Opt optimization algorithm gives the quality of 2-Opt at high speed. Even so fast that it keeps track with interactive changes of the waypoints on a moving map display. This mechanism gives short routes for your sightseeing or geocaching planning and can also be used professionally if you have to visit several locations on a single tour as in package delivery, meals on wheels, or elderly care.
 Good morning all together. My name is Thomas Bremer. I'm from Germany. I'm a software developer. I'm working as a freelancer, mainly in the area of embedded systems and geoscience or geospatial science is kind of my hobby, which on the one hand gives me lots of fun entertainment, hopefully useful results, but I don't have much time for it. And with this thing I'm going to present here, I've hit some big bubble which might explode at some time. So he's not the AV guy. Yeah, okay, I expected that. Yeah. Yeah. Yeah. So you added the camouflage. Yeah. Well, before the remainder, I need the slides. Well, the first slide I can start, I can try to start my presentation without the slides because the first stuff I can simply tell you. I started with a presentation or the idea of Thomas Aver Edison, who, well, rumor has it that he has invented the light bulb, which isn't true. He hasn't done it. It was a German called Heinrich Gübel. And Edison made it usable for the public, this light bulb, and this screw mount, which you know, or which maybe the elder people of you know from when we had this incandescent light bulbs to plug or to screw in, they have different sizes, E10, E14, E27, and this E stands for Edison. So that's where his name has remained until today. But he's also famous for certain quotes he made. And one of it, this is genius is 1% inspirations and 99% perspiration. This also holds for me because I'm more on the 1% side, I have to say. And last year I've been here and there was a talk about this web server, three geo names.org. I have to correct the slides. I see there are some typos on it on them. This web server had the feature that you give it some geo coordinates, interactively by clicking or it also has had an API. And you get back a combination of three city names worldwide, which represent this location. It's not a kind of compression, but it's kind of a mental compression because three words with meaning or you maybe know them have, they are more easily to remember than two long decimal numbers. And here, yeah, I try. And he also had on this website or he has on this website a feature that you can encode these two geo names, these two dimensional geo coordinates into a one dimensional, so to say, hash string of 11 characters. And the presenter also told about a Hilbert curve, which was, hey, you're binding me. He also told about the Hilbert curve he used for this mapping or for this conversation to reduce the borders. Now he's also taking me away. It's okay. You just have to do your work. I'm only for fun. I've already used it to watch TV and stuff like that. Okay. Let's see. Okay. So what I did then after because I found the idea rather interesting was I analyzed the website and I had a closer look at it, so to say. And I saw that the mapping really works in both directions. You can enter geo coordinates and get the bird combination or back. I already told you that there's an API which you can use. There's a link to the source code which is also appreciatable in terms of open source. There's also a map in the user interface but it's rather small. It's improvable, so to say. And also the user interface around it is also improvable. So I had a closer look at the code. It has been written in Perl. The code is working as expected but it's not easily readable. Then in the code there are some obstacles, so to say, or almost obstacles. It's tweakable because some big integer representation is used for arbitrary size integers which are not needed. There's a bit shuffling code in it which is done in the most standard way which is heavily tunable. And also the hashes I told you about. This 11 letter string consists of 26 characters, all alphabet characters and 10 digits. There are other representation which only use 32 characters and digits per letter to avoid some rude words which might create with such a mechanism. So to say, this free geo-names.org website represents a very good idea. It works but it's still improvable in terms of UI and also coding style. And I would say it's maybe in the area of 50% if you use this adjacent scale as I called it. But then there was the idea of the Hilbert Curve. And this now was the 1% inspiration for me because when you do some research on it then you find out you could do the following. You could just take one Hilbert Curve or take several, take four of them, connect them to a Cyclic Moor Curve, put them on the map. You can use, for the whole world you can use this level 0 OSM tile with the Mercator mapping with the Mercator projection. Then what you can do is that you can take a point on this map, map it to the distance it has on this curve from a fixed origin you have to define. And then if you have several points you can map all of them and you can sort them according to this distance on the curve. And the result is that this order you find is an approximation to the traveling salesman problem. It's a rather reasonable, not optimal, but reasonable route you find. This has already been studied in the past. You find examples where mills on wheels have been using it and they really improved their driving times with that. You can also use it again for packet delivery, for geocaching or for home care, wherever you have to visit many, many positions. So imagine that you use this system as an addressing system for postal services. You simply have this, you give it this unique address and the postman simply has to sort his letters according to this index and travels them and well, he can do it rather fast. So regarding the perspiration, as I said, I'm more on this 1% side. Yeah, what I did or what I'm working on now is another proof of concept. I would like to make it a complete system, but as I said, I don't have the perspiration on the one hand and since it's only a hobby, I can't find the time for that. And there's even more inspiration just to improve the user interface regarding the routing. This TSP approximation only is according to the distance on the map. If you have small areas, then you get, well, you get no or almost no distortion on a MacCator projection and you get good results, but you can also use or you can even you can further improve if improve the result if you use routing algorithms according to or using the roads and highways. And you can also use this the result as an input for other optimization or algorithms like the two opt algorithm, which run much faster than than before. They don't give better results, but they they are finished much earlier. Yeah, basically that that was everything I wanted to tell you without without this. Maybe we could make a little bridge. What is your question to the room? My question to the room. Could you imagine to use such such system which very easily gives you a short round trip route for whatever purpose, as I already said, geocaching if you want to to find 10 caches on a day or so then you have to well if you're visiting a firm place or for instance, if you get to Brussels, you find several 10 geocaches on the map and then have to sort have to order them according to your to have to find the visit order. So that's what I wanted to say. Something like that or if you know someone who does home care or works for DPD or is recharger e scooter with Saja recharger room. Anybody interested in this or could see somewhere in the interest? Is there anybody? Yeah, sorry, could you? Yeah, sorry. Yeah, I work at within the way by. So I was out the walk indoors. And we have a lot of contractors that need to go through different rooms in the airport. It's quite interesting because they need to go through security filters and other things to go somewhere in a place and then you go out and you go to other places. And actually, I'm finished now. So I don't know. Are you doing anything? I'm the best. I have to listen to you. Okay, but then we have like more logic with how you cross security filters in the airport. But then even this algorithm I just presented, it could help you if you put another algorithm on it, which also considers the waiting times at the security filters to get, well, to quickly get a result because those algorithms, if you have 10 or several 10 locations, they usually they have certain they have immense run times. They are rather slow because the struggling salesman problem is one of the the most complicated or most complex problems in computer science. It could help. Yes. With a conversation at another time, another place, it's worthwhile for the two of you. Well, you have something out of this meeting. I think it will work for you. Does anybody else have a question to? Yeah. It's such a bummer with the screen. So I thought maybe it would be nice that if like anyone's interest is tickled, you could point out to those people to get any online resources which might have a trace of what you said. So these addresses, you can have a look, but they are also at the currently at a low level of implementation. But well, not really because they are doing this habit optimization and then you can stop it before that they are doing a two opt optimization to find even shorter route. So unfortunately, you have not been able to show your algorithms like last year. Yeah. On the other hand, it sort of flew at the time of my head, but I'm not a mathematician. Okay.
 Good morning all together. My name is Thomas Bremer. I'm from Germany. I'm a software  developer. I'm working as a freelancer, mainly in the area of embedded systems and geoscience  or geospatial science is kind of my hobby, which on the one hand gives me lots of fun  entertainment, hopefully useful results, but I don't have much time for it. And with this  thing I'm going to present here, I've hit some big bubble which might explode at some  time. So he's not the AV guy. Yeah, okay, I expected that. Yeah. Yeah. Yeah. So you  added the camouflage. Yeah. Well, before the remainder, I need the slides. Well, the  first slide I can start, I can try to start my presentation without the slides because  the first stuff I can simply tell you. I started with a presentation or the idea of Thomas  Aver Edison, who, well, rumor has it that he has invented the light bulb, which isn't  true. He hasn't done it. It was a German called Heinrich Gübel. And Edison made it usable  for the public, this light bulb, and this screw mount, which you know, or which maybe  the elder people of you know from when we had this incandescent light bulbs to plug  or to screw in, they have different sizes, E10, E14, E27, and this E stands for Edison.  So that's where his name has remained until today. But he's also famous for certain quotes  he made. And one of it, this is genius is 1% inspirations and 99% perspiration. This  also holds for me because I'm more on the 1% side, I have to say. And last year I've  been here and there was a talk about this web server, three geo names.org. I have to  correct the slides. I see there are some typos on it on them. This web server had the feature  that you give it some geo coordinates, interactively by clicking or it also has had an API. And  you get back a combination of three city names worldwide, which represent this location.  It's not a kind of compression, but it's kind of a mental compression because three words  with meaning or you maybe know them have, they are more easily to remember than two  long decimal numbers. And here, yeah, I try. And he also had on this website or he has  on this website a feature that you can encode these two geo names, these two dimensional  geo coordinates into a one dimensional, so to say, hash string of 11 characters. And  the presenter also told about a Hilbert curve, which was, hey, you're binding me. He also  told about the Hilbert curve he used for this mapping or for this conversation to reduce  the borders. Now he's also taking me away. It's okay. You just have to do your work.  I'm only for fun. I've already used it to watch TV and stuff like that. Okay. Let's see.  Okay. So what I did then after because I found the idea rather interesting was I analyzed  the website and I had a closer look at it, so to say. And I saw that the mapping really  works in both directions. You can enter geo coordinates and get the bird combination or  back. I already told you that there's an API which you can use. There's a link to the source  code which is also appreciatable in terms of open source. There's also a map in the user  interface but it's rather small. It's improvable, so to say. And also the user interface around  it is also improvable. So I had a closer look at the code. It has been written in Perl.  The code is working as expected but it's not easily readable. Then in the code there are  some obstacles, so to say, or almost obstacles. It's tweakable because some big integer representation  is used for arbitrary size integers which are not needed. There's a bit shuffling code  in it which is done in the most standard way which is heavily tunable. And also the hashes  I told you about. This 11 letter string consists of 26 characters, all alphabet characters  and 10 digits. There are other representation which only use 32 characters and digits per  letter to avoid some rude words which might create with such a mechanism. So to say, this  free geo-names.org website represents a very good idea. It works but it's still improvable  in terms of UI and also coding style. And I would say it's maybe in the area of 50%  if you use this adjacent scale as I called it. But then there was the idea of the Hilbert  Curve. And this now was the 1% inspiration for me because when you do some research on  it then you find out you could do the following. You could just take one Hilbert Curve or take  several, take four of them, connect them to a Cyclic Moor Curve, put them on the map.  You can use, for the whole world you can use this level 0 OSM tile with the Mercator mapping  with the Mercator projection. Then what you can do is that you can take a point on this  map, map it to the distance it has on this curve from a fixed origin you have to define.  And then if you have several points you can map all of them and you can sort them according  to this distance on the curve. And the result is that this order you find is an approximation  to the traveling salesman problem. It's a rather reasonable, not optimal, but reasonable  route you find. This has already been studied in the past. You find examples where mills  on wheels have been using it and they really improved their driving times with that. You  can also use it again for packet delivery, for geocaching or for home care, wherever  you have to visit many, many positions. So imagine that you use this system as an addressing  system for postal services. You simply have this, you give it this unique address and  the postman simply has to sort his letters according to this index and travels them  and well, he can do it rather fast. So regarding the perspiration, as I said, I'm more on this  1% side. Yeah, what I did or what I'm working on now is another proof of concept. I would  like to make it a complete system, but as I said, I don't have the perspiration on the  one hand and since it's only a hobby, I can't find the time for that. And there's even more  inspiration just to improve the user interface regarding the routing. This TSP approximation  only is according to the distance on the map. If you have small areas, then you get, well,  you get no or almost no distortion on a MacCator projection and you get good results, but you  can also use or you can even you can further improve if improve the result if you use routing  algorithms according to or using the roads and highways. And you can also use this the  result as an input for other optimization or algorithms like the two opt algorithm,  which run much faster than than before. They don't give better results, but they they are  finished much earlier. Yeah, basically that that was everything I wanted to tell you without  without this. Maybe we could make a little bridge. What is your question to the room? My question to  the room. Could you imagine to use such such system which very easily gives you a short round trip  route for whatever purpose, as I already said, geocaching if you want to to find 10 caches on  a day or so then you have to well if you're visiting a firm place or for instance, if you get to  Brussels, you find several 10 geocaches on the map and then have to sort have to order them  according to your to have to find the visit order. So that's what I wanted to say. Something like  that or if you know someone who does home care or works for DPD or is recharger e scooter  with Saja recharger room. Anybody interested in this or could see somewhere in the interest?  Is there anybody? Yeah, sorry, could you? Yeah, sorry. Yeah, I work at within the way by.  So I was out the walk indoors. And we have a lot of contractors that need to go through different  rooms in the airport. It's quite interesting because they need to go through security filters and other things to go somewhere in a place and then you go out and you go to other places.  And actually, I'm finished now. So I don't know. Are you doing anything?  I'm the best. I have to listen to you. Okay, but then we have like more logic with how you cross security filters in the airport. But then even this algorithm I just presented, it could help you if you put another algorithm on it, which also considers the waiting times at the security filters to get, well, to quickly  get a result because those algorithms, if you have 10 or several 10 locations, they usually they have certain they have immense run times. They are rather slow because the struggling salesman problem is one of the the most complicated or most complex  problems in computer science. It could help. Yes. With a conversation at another time, another place, it's worthwhile for the two of you. Well, you have something out of this meeting.  I think it will work for you. Does anybody else have a question to? Yeah. It's such a bummer with the screen. So I thought maybe it would be nice that if like anyone's interest is tickled, you could point out to those people to get any online resources which might have a trace of what you said.  So these addresses, you can have a look, but they are also at the currently at a low level of implementation. But  well, not really because they are doing this habit optimization and then you can stop it before that they are doing a two opt optimization to find even shorter route.  So unfortunately, you have not been able to show your algorithms like last year. Yeah. On the other hand, it sort of flew at the time of my head, but I'm not a mathematician. Okay.
getting_inspired_by_open_software_for_a_web_site_g3nfyi_0_167.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_168_7487.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_7488_7751.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_7752_7931.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_7932_9683.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_9684_9743.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_9744_10091.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_10092_10163.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_10164_10379.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_10380_11711.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_11712_11903.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_11904_12227.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_12228_15179.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_15180_15491.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_15492_17339.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_17340_18347.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_18348_19787.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_19788_19967.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_19968_22607.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_22608_22991.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_22992_23579.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_23580_23843.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_23844_24623.png getting_inspired_by_open_software_for_a_web_site_g3nfyi_24624_24737.png