Author Topic: Grid filling algorithm (to get you warmed up for AoC)  (Read 2996 times)

Grid filling algorithm (to get you warmed up for AoC)
« on: 02 November, 2018, 11:36:55 am »
OK, as part of my script to make Veloview Tile bagging (https://yacf.co.uk/forum/index.php?topic=108374.0) easier, I want to take the KML file of my nearby unexplored tiles and convert it to a GPX file so I view them when plotting routes to go and cover my missing tiles.

If I do this naively (i.e. using kml2gpx.com) then I end up with thousands of individual GPX tracks, one for each tile, and websites like gpxeditor.co.uk get really bogged down by thousands of GPX tracks.

So far (https://yacf.co.uk/forum/index.php?topic=108374.msg2334829#msg2334829) I've done enough to convert it to an outline of each box in GPX, but I'd still like the lines for each tile in there as it's hard to guess whether a particular route goes through a tile or not inside a big box.

I want to draw each box and the internal grid lines using as few contiguous lines as possible.

The problem boils down to this:-

Given a set of unit length edges (either N/S or E/W) on a grid (that form a connected undirected graph), and starting from any point, what is the fewest number of lines that need to be drawn in order to cover all of the edges. The lines are contiguous, so the next line starts from where the previous line finishes, you can't jump spaces.

i.e. consider a single box of points (0,0) (0,1) (1,1) (1,0) it should be obvious that this requires 4 lines (and can be started anywhere).

If you take a two side by side boxes then it takes 6 lines (one of the lines has length 2), it can't be done in 5.

If you take an L shape of 3 boxes, then it still only takes 6 lines.

So, given an input of edges, give me a list of points that you need to travel to to cover all of the edges.

Example input (for an L shaped set of 3 boxes missing the bottom left box of a 2x2):-
0,1 0,2
1,0 1,1
1,1 1,2
2,0 2,1
2,1 2,2
1,0 2,0
0,1 1,1
1,1 2,1
0,2 1,2
1,2 2,2

One example output would be
1,2 1,0 2,0 2,2 0,2 0,1 2,1

which would be the start point (1,2) and 6 subsequent points representing each of the next lines.

No problem drawing the same line twice, or drawing a portion of a line twice (some shapes it will be impossible not to do this).

The goal is the minimal number of points in the resulting GPX track.

When I get a chance I'll modify my current scripts to get some real input data for this problem.

I had a search for a canonical algorithm for this (it's a bit TSP-ish I suppose) but I can't find an obvious one.
"Yes please" said Squirrel "biscuits are our favourite things."

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #1 on: 02 November, 2018, 01:03:07 pm »
The slowness is primarily down to the default for mapping to use the SVG element rather than the Canvas element.  The former involves creating thousands of new DOM nodes, the latter draws the pixels directly (hence the term Canvas).   Canvas can handle drawing over 100,000 nodes in less than a second in the browser.   Pretty sure GPX Editor uses Leaflet. Leaflet supports using Canvas for drawing paths / tracks if the option is set to true.  By default it is set to false for maximum browser compatibility.

In terms of an algorithm you can do a horizontal and vertical walk of your simple graph taking your input as example

0,1 0,2
1,0 1,1
1,1 1,2
2,0 2,1
2,1 2,2
1,0 2,0
0,1 1,1
1,1 2,1
0,2 1,2
1,2 2,2

First first we take all the lines that move vertically and sort the start point of the line by its x, and then its y coordinate so we end up with

0,1 0,2
1,0 1,1
1,1 1,2
2,0 2,1
2,1 2,2

You then walk through the sorted set of vertical lines looking for a join in the next line. Whenever a gap appears you output a line and start building the next one.

So 0,1 - 0,2 is a single line not joining to any of the other lines so one line output is 0,1 - 0,2
1,0 - 1,1 joins to 1,1 - 1,2 so the next vertical line output 1,0 - 1,2
2,0 - 2,1 join to 2,1 - 2,2 and you reach the end of the list so you output your final vertical line 2,0 - 2,2

So the three vertical lines output are 0,1 - 0,2 ; 1,0 - 1,2; 2,0 - 2,2

You then take all the lines which move horizontal and sort by y then x


1,0 2,0
0,1 1,1
1,1 2,1
0,2 1,2
1,2 2,2

1,0 to 2,0 does not join to the next line so you output first horizinal line 1,0 - 2,0
0,1 - 1,1 joins 1,1 - 2,1 so you output your next line  0,1 - 2,1
0,2 - 1,2 joins 1,2 - 2,2 so you output your third horizintal line 0,2 - 2,2

So you output 6 lines to draw your L shaped box

It is not the minimum number of lines, you could have a single line / path for an L shape but it is trivial to implement and gets you down to low enough number of lines very quickly.

For a 30 x 1 grid you end up with 33 lines
for a 30 x 2 grid you end up with 34 lines
for 30 x 3 grid you end up witth 35 lines
fora 30 x 30 grid you end up with 62 lines / tracks

You will have more lines for incomplete grids but not massive numbers a browser cannot cope with even in SVG mode. For SVG you should keep the number of tracks below about 1000. For Canvas you can scale into tens of thousands easily.

Remember you are not trying to solve the TSP problem (which is non trivial beyond a certain number of nodes) you are just trying to get it "good enough" for your purposes.

P.S If you truly want to minimise the tracks as much as possible you will want to use a Taxicab geometry matrix to solve.



Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #2 on: 02 November, 2018, 02:10:12 pm »
For a 30 x 1 grid you end up with 33 lines

Those won't be contiguous lines though.

For a 30x1 grid you need to draw 31 vertical lines, and you'll need to move horizontally at least 31 times, which is 62 lines at least.

3x1 requires 8 lines.
4x1 requires 10 lines.
...
"Yes please" said Squirrel "biscuits are our favourite things."

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #3 on: 02 November, 2018, 02:14:23 pm »


For a 30x1 grid you need to draw 31 vertical lines, and you'll need to move horizontally at least 31 times, which is 62 lines at least.


Nope you have 31 vertical lines and two horizontal lines. You do not have 31 horizontal lines as well. So 33 lines.

They do not need to be contiguous to be drawn on a map in a browser.  If that is your problem scope (which the opening para seems to idnciate it is) then contiguous is an unnecessary condition.

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #4 on: 02 November, 2018, 02:19:00 pm »
Sure, but:-
a) too many separate tracks make the browser performance horrible
b) you're not answering the problem I've set

Here's what the original naive kml2gpx conversion gave:-



That has ~830 separate tracks (each red dot is the start/end of a track)and you can barely use it to plot further routes.

The number of points in each track doesn't affect performance that much (as the browser is speedy even when looking at a single route with thousands of trackpoints), so the optimisation is to reduce the number of tracks to a minimum. Separate tracks for each horizontal/vertical line is not optimal (AND NOT THE PROBLEM I HAVE SET).

The bonus is also reducing the number of points in each track to a minimum.
"Yes please" said Squirrel "biscuits are our favourite things."

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #5 on: 02 November, 2018, 02:25:19 pm »
Your problem is the speed and I am pretty sure I solve that. You would have a lot less tracks than 830.  Add Canvas and that is orders of magnitude faster than SVG.  I have used Canvas for charts in the browser and 5,000 tracks of around 40 points each is superfast.

The reason single genuine GPX tracks are speedy in browsers is because the number of points has been dramatically reduced via the Douglas Puecker algorithm.  The mapping never draws all the points (unless it is a bad implementation) in the browser.

Ben T

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #6 on: 02 November, 2018, 02:31:34 pm »
No idea about the algorithm but in terms of rendering is there any reason why they have to remain as thousands of tracks - if it were to say convert:
<trk><trkseg>...</trkseg></trk> x 1000
into
<trk> <trkseg>...</trkseg> x 1000 </trk>

i.e. 1 track with 1000 segments, instead of 1000 tracks each with presumably one segment.

would that achieve the same end? that would reduce the number of DOM elements.

Part of it is the 'flags' at the right hand side explorer view which are one per track.

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #7 on: 02 November, 2018, 02:39:58 pm »
Your problem is the speed and I am pretty sure I solve that.

No, the problem was an AoC style problem I posed by giving some background. You're trying to solve the background problem (which is quite separate, but still useful) and ignoring the AoC problem I've posed. Apologies if it wasn't clear.

I may just delete this thread (saving the useful bits) and start again.
"Yes please" said Squirrel "biscuits are our favourite things."

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #8 on: 02 November, 2018, 02:43:52 pm »
So you are not trying to solve your grid problem, and speed, in the mapping. You are trying to pose a more abstract problem.  That was not clear from your OP.  In which case using a Taxicab geometry matrix is the way to solve the more abstract version.

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #9 on: 02 November, 2018, 02:49:32 pm »
No idea about the algorithm but in terms of rendering is there any reason why they have to remain as thousands of tracks - if it were to say convert:
<trk><trkseg>...</trkseg></trk> x 1000
into
<trk> <trkseg>...</trkseg> x 1000 </trk>

i.e. 1 track with 1000 segments, instead of 1000 tracks each with presumably one segment.

would that achieve the same end? that would reduce the number of DOM elements.

Part of it is the 'flags' at the right hand side explorer view which are one per track.

Doesn't seem to make much difference, there's still a 5-10 second delay on zooming in on my machine (FF60 on a reasonably powerful linux desktop).

Here are the files if you want to play with them:-
http://www.greenbank.org/misc/explorer2.gpx (original naive conversion)
http://www.greenbank.org/misc/explorer3.gpx (collapsed all trkseg's into a single trk)

[EDIT] And compare that to the minimal border GPX file (not quite the same as this is a more recent conversion): http://www.greenbank.org/misc/explorer4.gpx
"Yes please" said Squirrel "biscuits are our favourite things."

Ben T

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #10 on: 02 November, 2018, 02:54:26 pm »
No idea about the algorithm but in terms of rendering is there any reason why they have to remain as thousands of tracks - if it were to say convert:
<trk><trkseg>...</trkseg></trk> x 1000
into
<trk> <trkseg>...</trkseg> x 1000 </trk>

i.e. 1 track with 1000 segments, instead of 1000 tracks each with presumably one segment.

would that achieve the same end? that would reduce the number of DOM elements.

Part of it is the 'flags' at the right hand side explorer view which are one per track.

Doesn't seem to make much difference, there's still a 5-10 second delay on zooming in on my machine (FF60 on a reasonably powerful linux desktop).

Here are the files if you want to play with them:-
http://www.greenbank.org/misc/explorer2.gpx (original naive conversion)
http://www.greenbank.org/misc/explorer3.gpx (collapsed all trkseg's into a single trk)

[EDIT] And compare that to the minimal border GPX file (not quite the same as this is a more recent conversion): http://www.greenbank.org/misc/explorer4.gpx

does it matter if it doesn't have markers?

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #11 on: 02 November, 2018, 03:03:44 pm »
yes (it doesn't matter), they only really get in the way.

(I assume the 'markers' are the red or white circles for the start/end of each trkseg?)
"Yes please" said Squirrel "biscuits are our favourite things."

Ben T

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #12 on: 02 November, 2018, 03:17:20 pm »
yes (it doesn't matter), they only really get in the way.

(I assume the 'markers' are the red or white circles for the start/end of each trkseg?)

there you go, just made it not add the white markers if > 100 segments.

http://www.gpxeditor.co.uk/?lnk=http://www.greenbank.org/misc/explorer3.gpx

lots of tracks will still be slow though.


Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #13 on: 02 November, 2018, 03:26:48 pm »
Considerably quicker, thanks.

Will look at reducing the number of tracks but artificially keep the number of segments above 100.
"Yes please" said Squirrel "biscuits are our favourite things."

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #14 on: 02 November, 2018, 04:45:09 pm »
Ben if you set the mapping to use Canvas, preferCanvas:true when invoking Leaflet that should speed it up no end i have not delved into Leaflet to see if it does the browser compatibility check or not so you may want to add that check.

Ben T

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #15 on: 02 November, 2018, 04:47:23 pm »
doesn't use leaflet. Just uses google maps API

Graeme

  • @fatherhilarious.blog 🦋
    • Graeme's Blog
Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #16 on: 02 November, 2018, 04:59:03 pm »
Eats popcorn and waits for Greenbank to publish his algorithm as a webtool I can use. Interesting reading this thread... Even if it is unintelligible to me.

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #17 on: 02 November, 2018, 05:05:32 pm »
doesn't use leaflet. Just uses google maps API

Ah that's a shame, Google is a bit behind the times with their mapping.

Ben T

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #18 on: 02 November, 2018, 05:06:38 pm »
doesn't use leaflet. Just uses google maps API

Ah that's a shame, Google is a bit behind the times with their mapping.

I know, probably would be better in leaflet, but isn't particularly well abstracted so would be a complete rewrite to convert it.

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #19 on: 02 November, 2018, 05:32:04 pm »
Eats popcorn and waits for Greenbank to publish his algorithm as a webtool I can use. Interesting reading this thread... Even if it is unintelligible to me.

Graeme this is a much better (and harder) problem that has been solved. The ultimate pub crawl, of 49,000 pubs

http://www.math.uwaterloo.ca/tsp/uk/index.html

Phil W

Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #20 on: 02 November, 2018, 05:56:50 pm »
Don't know whether you read to the bottom but they hsve solved tsp for two million stars in 3 dimensions. Computational maths marches forward.

We currently have a tour of length 28,884,456.3 parsecs, found with a parallel version of LKH. We also know, via a parallel application of the cutting-plane method, that there is no tour shorter than 28,883,773.4 parsecs. That means our tour is at most 1.000024 times longer than a optimal route through the two million stars.

Graeme

  • @fatherhilarious.blog 🦋
    • Graeme's Blog
Re: Grid filling algorithm (to get you warmed up for AoC)
« Reply #21 on: 02 November, 2018, 06:15:04 pm »
Eats popcorn and waits for Greenbank to publish his algorithm as a webtool I can use. Interesting reading this thread... Even if it is unintelligible to me.

Graeme this is a much better (and harder) problem that has been solved. The ultimate pub crawl, of 49,000 pubs

http://www.math.uwaterloo.ca/tsp/uk/index.html

#PicksJawUpFromFloor.