On Jan 1, 4:15 am, mark mcclure <[email protected]> wrote: > The following two pages use the current API to > display the same polyline with about 9700 points; one is > encoded, the other is standard and the encoded polyline > performance is much better:
http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/proper.html http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/normal.html Try using an array of: [{x:Lon,y:Lat}, ... ,{x:Lon,y:Lat}] Instead of an array of: [new GLatLng(Lat,Lon), ... ,new GLatLng(Lat,Lon)] > > Zoom strings are a basically flawed idea. ... Doing it in > > the API reduces the chance of mistakes. Doing it in the API > > enables averaging between points. Doing it in the API also > > could benefit "on-the-fly" polys. The design decision is attributable to Google not to anyone forced to comply with "fromEncoded" argument requirements. Selective point reduction is a good idea. Zoom strings are a really bad idea. > Doing it in the API also takes time. Compare now the > performance of the following two maps: http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/proper.html http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/exampleGG... > In this second example, the encoding is performed by GGeoXml. > As a result, there is a bit of delay in the loading of the > file. Now, it's not much, but an example with say 50,000 or > 500,000 points would show a much bigger delay. The file: http://facstaff.unca.edu/mcmcclur/GoogleMaps/EncodePolyline/DirectionsLA-NY.kml contains a lot of other stuff not related to the encoded poly. It also uses a less aggressive zoom string. A fair test ought to compare similar polys without the extras. The zoom strings ought to agree also. To convert to JSON, try: www.polyarc.us/gx Enter the KML file name. Click "Load". > > Douglas-Peucker for zoom strings is overkill. > > I chose to adapted the Douglas-Peucker algorithm to polyline > encoding for three reasons: > 1) It's the industry standard. ArcGIS, for example, has > this algorithm for polyline simplification. > 2) There is a very simple geometric correspondence between > the DP algorithm and the encoding process. > 3) It's relatively fast. I mean this in a quite > quantitative sense; it's expected time complexity is > O(n*log(n)). My first version of the polyline encoder was > based on the simpler and faster vertex reduction algorithm > (O(n)), but the result was not of equal quality. I wonder what Google uses for GGeoXml poly encoding. I doubt it is Douglas-Peucker. > > Douglas-Peucker was designed for polylines not for polygons. > > This is just not true; there's no reason you can't apply DP > to a polyline whose first and last coordinates are the same. The selection of the first point is arbitrary. It will always find the most distant first pivot point which may or may not be a good candidate for further point reduction. Adjacent polys sharing common boundaries like states / counties / townships will not match because different sets of pivot points are used. A single pass algorithm based on the height of local triangles eliminates the issue. It can be done quickly. It produces good results. It is deterministic. > > If applied to Lat/Lon coordinates rather than to pixel > > coordinates, it will produce biased results. > > This is simply an issue involving map projection and arises > in many similar applications. There's no reason you can't > project first and then apply DP. You could also take John > and Marcelo's approach and use spherical distance rather > than Cartesian. Of course, either of these will slow things > down. But the API already has to do the projection in order to draw the poly. It seems like the API could perform point reduction during projection. The X & Y components can be weighted equally. Integers are more suitable for analysis than floating point numbers. A simple XOR of their X & Y pixel offsets will yield the zoom level in which divergence occurs. Again, I am in favor of point reduction according to zoom level but not zoom strings. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Google Maps API" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/Google-Maps-API?hl=en -~----------~----~----~----~------~----~------~--~---
