Taoffi's blog

prisonniers du temps

Deep Zoom follow-up - optimizing displayed (KML) polygon points

DeepZoom has been one of the most inspiring projects/technologies in last years. Its approach is now extensively used in various domains, notably in mapping applications.

I think DeepZoom approach still have more application areas to explore.

In this article, I will explore one question where the DeepZoom approach can be quite useful.

KML Polygons

KML (Keyhole Markup Language) is an XML-notation-based 'language' now widely used to describe geographic data. Among many types of data, KML includes Polygons, which describe point locations on a map. A polygon may, for instance describe the contour of political frontiers of a country or a seashore…, which may thus contain a large number of point-coordinates.

As each of the polygon's points may be associated with more or less large data objects, processing the polygon information may become a challenging operation either on a server or on a client machine. Reducing manipulated polygon data size and required processing efforts is thus an important performance question.

One of the techniques often used is to compress (zip) the KML transmitted files' data (to produce .kmz files instead of .kml). But there should be a better approach in simply transferring (or processing) only significant point's data.

 

Zoom level and view port

When we view or display a map, we in fact view in a zoom level. According to this zoom level, two points may have a significant distance or be confused into one same point.

The following figures illustrate this:

  • At the first zoom level, point 1 and point 2 are clearly distinct
  • The more we zoom-out, the less distinctive they become
  • Until both can be considered as one same point

Conclusion: according to the zoom-level, we may transfer (or manipulate/process) only one of those points instead of both.

 

Zoom level1

Zoom-out1

Zoom-out2

 

This can also be illustrated by the DeepZoom 'pyramid' approach:

 

 

A map is also viewed into a 'View Port' (the window through which we view the map).

For the two points of the previous example, at certain zoom-in level (or view port coordinates change), one (or both) of them may be located out of the view port.

 

 

Another conclusion: we don't need to transfer (or manipulate/process) polygon points which may be located outside of the current view port.

The delivered code sample

The downloadable code includes the data of a polygon composed of a large array of points.

The sample uses several parameters to determine which points to be considered for transfer or processing:

  • The view port coordinates: used to select only points inside the view port
  • The zoom level: associated with a ratio used to compare the significance of points' coordinates variations

 

The ZoomPortView object exposes few properties: a Name, a ZoomRatio, TopLeft and BottomRight points (Width and Height are calculated according to those points' coordinates).

 

The ZoomPolygon object exposes few properties: a list of polygon's Points. For the sake of current demonstration, the object also exposes PointsOutOfPortView which is a list of points that are out of the current port view.

ZoomPolygon class offers a static method which parses an array of points according to a given port view, returning the related new ZoomPolygon object.

 

public static ZoomPolygon Parse(Point[] points, ZoomPortView portView)
{
    ZoomPolygon        polygon        = new ZoomPolygon(portView);
    ObservableCollection<Point> pointList = new ObservableCollection<Point>();
    ObservableCollection<Point> pointsOutPortView = new ObservableCollection<Point>();
    double    zoomRatio = portView.ZoomRatio;
 
    double maxX    = portView.Width,
            maxY    = portView.Height;
    Point    point,
            last    = new Point();
 
    for(int index = 0; index< points.Length; index++)
    {
        point = points[index];
 
        if( ! portView.IsPointInPortview(point))
        {
            pointsOutPortView.Add(point);
            goto next_point;
        }
 
        if (pointList.Count <= 0)
        {
            pointList.Add(point);
            goto next_point;
        }
 
        if( Math.Abs( (point.X - last.X) / maxX) >= zoomRatio
            || Math.Abs( (point.Y - last.Y) / maxY) >= zoomRatio)
            pointList.Add(point);
next_point:
        last = point;
    }
 
    polygon.Points = pointList;
    polygon.PointsOutOfPortView = pointsOutPortView;
    return polygon;
}
 

 

Note: the code above can of course be more compact using Linq. This version seems more illustrative of the logic to include / exclude polygon points.

 

Sample screen shots

 

Download the sample code

KmlOptimizerSample.zip (1.28 mb)

Acknowledgement

Thanks to all my friends at Thomson Reuters' iMap Project with whom I learnt much about kml and maps in general: Benoît, Florent, Catalin, Christophe, Ronan, John, Geffe, Calum…

Object Visibility and learning cycle… just a vision of

In everyday work, we come through new tools or new versions of tools we knew before.

The cycle of playing with and manipulating these tools’ objects to attain a reasonable level of mastering… is often daunting!

To minimize the learning cycle of tools, some helpful features have been introduced: like documentation, tooltips… etc.

Documentation is of course important, but, for me, tooltips are much more helpful. They just appear when I need them in the context of using the object or the property.

The thing is: when you manipulate an object for the first time, you really know few things about its composition and, even less, about its role in the global mechanics of the tool in question. You just know it is there, and it should be there for some reason and that you should spend some time to understand: its role, its structure, and finally how can it be useful for you (if at all it could be!)

One way to shorten this learning cycle is to let others show you how to use the tool and its object. Quite useful, but, on one hand, this occults some side of self-experience (important)… and also negatively interferes in your critical view of the tool (which is often useful for the tool’s enhancement itself)

What we do to know about (most) simple toys seems more rational: You just set something on or off (left/right or up/down…)… then put the toy on work and see... after some cycles you end up by figuring out what is the ‘best’ position for your needs (or mood!).

Another representation, which may also give an interesting slant related to this subject, is the DeepZoom technology used in maps applications where you can first see the whole world map, and then, zooming-in on the map you get more details about a given country, city, streets, buildings… etc.

A good path for reducing the time and effort needed to learn a subject or a tool would be:

  • To be able to see (explore) the global image of the subject or tool’s structure in action;
  • Be able to zoom-in on its objects and see their properties (progressively detailed according to your zoom level);
  • Be able to change the value of a give object’ property… and perceive the impact of the change on the global behavior.

This proposed path cannot of course be applied in all situations or contexts, but can be useful in many (most) cases.

We may, for instance, need to create a simulation context inside which we can ‘run’ the specific tool or object. An approach which may also be useful for product tests and benchmarking.

Some interesting works have been done on some aspects (like The Property Grid project)… More is to be done on the visualization of objects and properties by zoom level. Will try to write a sample on this in a future post.