Improve road/line merging II

[nvkelso]

Following up from improvements in #1191...

[nvkelso]

@bcamper said in #1191 (comment):

Here's what I've found (using the new debug stats in tangrams/tangram#544) for a high-complexity NYC view at z12 (#12/40.68636570811375/-73.94691467285234):

Note: line geometry counts here are the number of GL triangles Tangram had to build to render the features (lines decomposed into triangles, etc.), not the number of features in the source data - but for line features, they should scale linearly together.

Tangram master / prod tiles

• Total line geometries: 258,232
• roads 222,512
  • highways 23,810
  • major roads 39,304
  • minor roads 148,756
  • railways 7,812

Tangram master / dev tiles

• Total line geometries: 226,079 (-13% from prod)
• roads 190,294
  • highways 17,884
  • major roads 21,056
  • minor roads 144,110
  • railways 4,556

Tangram merge-multilines / dev tiles

• This branch does additional client-side line merging + simplification
• Total line geometries: 156,359 (additional -30% from dev tiles, -39% from current prod)
• roads 121,198
  • highways 15,212
  • major roads 20,374
  • minor roads 80,086
  • railways 3,168

Summary
It looks like the dev tiles are effectively reducing the numbers of highways, major roads, and railways (these are just the top sub-layers), but aren't really affecting the number of minor roads (only 148k -> 144k in this view) - which are the vast majority at this zoom.

For reference, the client-side code I'm using is here (sorry, it's a bit more complex than it needs to be due to some premature optimization to avoid reallocating/copying LineStrings that never need to be modified). It has two steps:

1. mergeContiguousMultiLineString(): iterates through the LineStrings in a MultiLineString, and merges any LineStrings where the last and first coordinates are equal (iterates in their natural order, so only helps if contiguous segments also happen to be sequential in the feature data!).
2. mergeColinearLineString(): after the above step, iterates through all the coordinates of the merged LineStrings, and removes any coordinates that are within a certain angle tolerance of the line's current direction (measured via the dot product of normalized vectors). This is a more narrow form of simplification to only remove near-colinear coordinates (I also tried running a generic simplification step on the geometry, before trying something more specific to the desired outcome here).

This technique works particularly well for grid systems with lots of straight streets, so this NYC example may be one of the cases of best-realized gains.

[nvkelso]

@zerebubuth said in #1191 (comment):

Cool, thanks!

Do you know how much of the 30% saving over dev tiles is due to mergeContiguousMultiLineString() and how much due to mergeColinearLineString()? If the problem is what I found before (the lack of merging at 4-way junctions) then I'd expect the mergeColinearLineString() pass to be much less effective on minor roads than the mergeContiguousMultiLineString() pass.

[bcamper]

Finally got back to this...

It looks like the two phases are interdependent and both are necessary for any significant savings. Total line geometry counts for:

no additional processing: 226,282
only mergeContiguousMultiLineString(): 224,749
only mergeColinearLineString(): 221,951
both steps: 156,757

[nvkelso]

Is the order of these operations important?

…

On Thu, May 25, 2017 at 12:20 PM, Brett Camper ***@***.***> wrote: Finally got back to this... It looks like the two phases are interdependent and both are necessary for any significant savings. Total line geometry counts for: no additional processing: 226,282 only mergeContiguousMultiLineString(): 224,749 only mergeColinearLineString(): 221,951 both steps: 156,757 — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#1227 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AA0EOy6rPaGq7TBe-FLXEWoVubXqKLIVks5r9aoygaJpZM4NJuQC> .

[bcamper]

Yes - mergeContiguousMultiLineString() has to be done first, because a lot of the resulting joined lines are collinear, and are then simplified with mergeColinearLineString(). If you call them in opposite order, you get 220,432 line geoms.

[zerebubuth]

Thanks! It seems like the two transforms are much less effective individually (saving 0.7% and 2%, respectively) than they are combined (30%). My hunch is that this is because of all those short segments left over between 4-way junctions in "grid pattern" streets such as around NYC.

I think if we rewrite the linemerge function so that it's able to handle 4-way junctions, then we'll get the 30% saving. We currently have an equivalent mergeColinearLineString() step, which is not as effective as it could be due to the equivalent of mergeContiguousMultiLineString() missing some opportunities for merging.

[nvkelso]

Subtask of #1350

[nvkelso]

More feature to be removed in #1331 will result in even more merging!