Advanced GPolyline usage
Interactivity and performance issues

Background & Motivation

Working on Maptales (& predecessors) for ~2 years

• Storytelling tool
• Document Routes
• GPS
• Editing

Personal background

• Academic research in Augmented Reality
• Interest in GIS
• Interest in web came back with Google Maps

Overview: GPolyline

2005

• VML on IE, images elsewhere
• No interactivity
• No simplification
• No editing

2007

• SVG on ffx, VML on IE, images elsewhere (Safari)
• Click events
• Encoded polylines
• No editing

Initial approach

What we wanted

• Full interactivity, editing on all browsers
• Acceptable performance even for long & detailed routes

Constraints

• SVG/VML not available on all browsers
• GPolyline does not give us enough control, events

Our approach

• Compose lines of individual "pixel" DIV elements

Drawing lines with DIV's

Bresenham Algorithm

-> Computer Graphics 101, Google, Wikipedia)

• Drawing all pixels would be too costly and did not look nice
• -> Make larger pixels and space them to draw a dotted line
• Still generating 1000's of DIVs?

Spacing the pixels

• Long lines are too costly when spacing is narrow
• Short lines lose detail when spacing is too wide
• -> Adaptive spacing dependent on line length
• Applied interactively, gives a nice "rubberband" effect

Cool: individual pixels can react to DOM events (mouseover, click)
used to implement editing, dragging, dropping and hovering

Apply Bresenham lines to Google Maps

Issues

Lines can get veeeeery long (in pixels) when zoomed in!

• Length doubles with every zoomlevel
  (100 pixels at ZL 8 become 256.000 pixels at ZL 16)
• Even if you do square root spacing you end up with 1600 DIVs at 160px distance
• -> Need clipping (cut off parts outside viewport)

A single segment will always be at least 1 pixel when zoomed out

• Problem for GPS data (Lots of trackpoints = very short straight lines)
• -> Need simplification (Skip trackpoints too close to others)

Clipping & Culling

Calculating intersections of lines with viewport boundaries is computationally expensive!

Cohen-Sutherland Clipping

Two-step approach

• Cull segments that cannot possibly cross the viewport boundaries (both inside or both to one side of the VP)
  • Assign binary "region" codes to andpoints of lines
  • If (code1 & code2 > 0) -> line outside
  • Fast binary operation that eliminates most segments
• Clip segments that (possibly) cross the window boundary

Not the fastest known clipping algorithm, but intuitive and good performance in JavaScript.

Simplification

Simple Approach: use binary search to eliminate segments which are too close

• Start- and endpoint of complete path must always be drawn
• Take median point and check if too close (e.g. 3px)
• If too close, finish, else repeat with the 2 subsegments

Overall Conclusions

• Performance OK, problematic for GPS data esp. on Safari
• Highly intuitive interaction
• Satisfying looks

Things changed

• Performance was sufficient, but problematic on Safari for long lines
• Google released improved polylines (SVG on firefox)
• Encoded polylines solve simplification in a sophisticated way

We decided to switch in June 2007, but

• Does the performance really improve?
• What about interactive editing?
• How to drop stuff on GPolylines?
• What about other cool features that we had implemented in the meantime?

-> Hybrid version!

Hybrid polylines

• Use (encoded) GPolyline for rendering
• Use our implementation for interactive editing
• Implement mouseover, click and drag events

Performance comparison

Very surprising!

• Our implementation was actually faster than GPolyline!
• Polylines with lots of points would freeze safari
• Ecoded polylines even slower for simple lines!
  (but more stable for comples ones)

Conclusions

• You must use encoded GPolylines for complex lines,
  otherwise you may freeze the browser
• Don't add a lot of polylines all at once,
  use timeouts to let the browser "breathe"

Encoded GPolylines

Douglas-Peucker Algorithm

• Sophisticated multi-level simplification based on proximity
• Points for all zoomlevels are calculated in advance
• Implementations for JavaScript, Java, Ruby, Perl, PHP,...
• http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/

Need code on server (for uploaded GPS data)
and client (for updating edited lines)

Interactive GPolylines

GPolylines do not give you any events (mouseover, click, ...)
How to solve this?

Calculating point-line distance

• Line equation: P = P1 + u (P2 - P1)
• Solving minmum distance gives:
  

http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
We can do this (with some optimizations) in real time for segments within viewport!

Following lines

Clipping is not needed for GPolylines, but can be reused to

• Place buttons at the edge
• Pan to the intersection of edge and line (repeatedly)
  

--> The final result

Try out our cool, editable polylines at maptales.com
Or view the screencast first.

Open Q&A

Thanks for your attention!


http://www.maptales.com
http://floledermann.blogspot.com