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…

Inspiring Jargon

I read:

"Arianespace… announced […] that two satellites it had tried to launch to join the European Space Agency's Galileo constellation, had entered a "non-nominal injection orbit"—in other words, gone wrong"  

You probably now know how to better say "I got a bug" (when it is just a "non-nominal behavior")!

Choices in a logical tree view – WPF sample

Using check boxes in TreeView control is a handy way for presenting choices in their logical tree-like structure.

In real life, though, choices can be a mix of inclusive (check-box) and exclusive (radio-button) options.

I expose here a solution for using that mix of option types in one same tree view.

The problem

The problem is divided into three main subjects:

  • How to use a mix of checkbox / radio button nodes in the same tree view control
  • How to get a radio button to be toggled from checked to unchecked status: Checkboxes are, 'naturally', able to be toggled from checked to unchecked status. This is not the case for Radio buttons. The result is that when you use radio button in a tree view, you will be able to check it but not to get it uncheck!
  • How to handle exclusive choices selection. That is when an exclusive option gets selected (checked), for instance,we must unselect all other exclusive sibling options.

 

To solve the first question, we will use:

  • A tree node object which indicates its option type (exclusive / inclusive)
  • Hierarchical control templates for each choice type
  • A template selector which will select the correct template according to the node object choice type

 

To solve the second, we will simply create a new Toggled Radio Button (which derives from RadioButton) and get this new object handle the Click event to toggle its selection status.

 

 

public class RadioToggleButton : RadioButton
{
    protected override void OnClick()
    {
        IsChecked = !IsChecked;
    }
}

 

 

The third question will be solved by implementing the required behaviors within our special tree node object.

 

The TreeNode object

The TreeNode object exposes few properties:

  • A Title
  • A Parent node (TreeNode)
  • A list of Children (List of TreeNode items)
  • A boolean flag which indicates if the node represents an exclusive choice option
  • A boolean flag which indicates if the node is selected

Through these properties, TreeNode object can expose other properties like its Root node, the First exclusive parent or descendant… etc.

 

The TreeNode Hierarchical data template

 

<UserControl.Resources>
…
…
    <!-- hierarchical template for checkbox treeview items -->
    <HierarchicalDataTemplate x:Key="checkBoxTemplate" 
        DataType="{x:Type app:TreeNode}"
        ItemsSource="{Binding Children}">
        <StackPanel Orientation="Horizontal">
            <CheckBox Focusable="False"
                VerticalAlignment="Center"
                IsChecked="{Binding IsSelected, Mode=TwoWay}" />
            <TextBlock Text="{Binding Title}" />
        </StackPanel>
    </HierarchicalDataTemplate>
 
    <!-- hierarchical template for (toggled) radio buttons treeview items -->
    <HierarchicalDataTemplate x:Key="radioButtonTemplate" 
            DataType="{x:Type app:TreeNode}"
            ItemsSource="{Binding Children}">
        <StackPanel Orientation="Horizontal">
            <ctrl:RadioToggleButton Focusable="False"
            VerticalAlignment="Center"
            IsChecked="{Binding IsSelected, Mode=TwoWay}" />
            <TextBlock Text="{Binding Title}" Margin="4, 1, 0, 0" />
        </StackPanel>
    </HierarchicalDataTemplate>
</UserControl.Resources>

 

 

The TreeView node's Item template selector

 

public class TreeNodeXTemplateSelector : DataTemplateSelector
{
    public override DataTemplate SelectTemplate(
                object item, DependencyObject container)
    {
        FrameworkElement    element = container    as FrameworkElement;
        TreeNode    node    = item  as TreeNode;
 
        if (element != null && node != null)
        {
            if (node.IsExclusive)
                return element.FindResource("radioButtonTemplate")
                                 as HierarchicalDataTemplate;
            return element.FindResource("checkBoxTemplate")
                                as HierarchicalDataTemplate;
        }
        return null;
    }
}

 

 

We can now use an ItemTemplateSelector to tell the Tree view control to select the adequate data template for each item according the tree node choice selection type (exclusive / inclusive)

 

<UserControl.Resources>
    <app:TreeNodeXTemplateSelector	x:Key="templateSelector" />
    …
    …
</UserControl.Resources>

 

<TreeView x:Name="treeview1" ItemsSource="{Binding Root.Children}"
                  ItemTemplateSelector="{StaticResource templateSelector}"/>

 

 

Exclusive node selection behavior

TreeNode selection behavior can be summarized as follows:

  • If the node is inclusive: do nothing (just set the selected flag)
  • If the node is exclusive (and selected):
    • Unselect all exclusive siblings (siblings = Parent's Children)
    • Select all inclusive child nodes
    • Select the first exclusive child node if any

 

public void UpdateSelection()
{
    if(! _isExclusive)
        return;
 
    if(_isSelected == true)
    {
        UnSelectSiblings();
    }
 
    SelectChildren(_isSelected);
}

 

 

 

protected void SelectChildren(bool selected)
{
    if(! selected)
    {
        UnSelectChildren();
        return;
    }
 
    TreeNode firstEx = FirstExclusiveChild;
 
    if(firstEx != null)
        firstEx.IsSelected = selected;
 
    foreach(TreeNode node in _children)
    {
        if(node.IsExclusive)
            continue;
 
        node.SetSelection(value: selected, updateChildren: true);
    }
}

 

 

Sample screenshot

 

Download the sample code TreeViewRadioAndCheckButtons.zip (67.88 kb)

Microsoft case: going monochrome

On the Windows Phone 8, the latest MSFT phone OS, you have a nice Theme selection option, which says:

"Change your phone's background and accent color to suit your mood today, this week or all month"

Quite attractive!

The feature proposes two settings:

  • Background
  • Accent color

 

On 'Background', you have two options: Light / Dark

On 'Accent color', you have a palette of 21 colors (which seems to be a pretty little choice on a device that, according to the manufacturer, can display 65000 colors or more!)

I should admit, that not having a choice is in a way less time consuming. May be this was the initial OS designer's intended objective.

 

Now let us leave WP and go back to the desktop machine to have a look at Microsoft Office 2013.

Here too, you have a nice feature to select your theme.

You have the choice between:

  • White
  • Light gray
  • Dark grey

 

The difference between the three is really too subtle:

I tried them all, and ended up by selecting 'Dark': a little more readable!

On another point: after all the literature about the 'user interface design guidelines', it now seems that Microsoft Office apps are the only applications that can keep being outside of any graphical constraints. Those guys are really too spoiledJ

 

Conclusion

It seems that someone at MSFT has decided to re-form our education about colors. The 'monochrome' seems to be the new MSFT User Interface Strategy (you can check yourself: Windows Phone, Windows 8, Office 2013…)

Some people may find this abusive… but, in a way, we are much less embarrassed with this new reduced theme strategy… we may gain more time to think about things more useful!

Of recipes and methods – Agile and agile rituals

Let me first clarify:

Learning that the square root of 144 = 12 is a 'recipe'.

Learning how to retrieve the square root of a number is a 'method'.

Recipes represent one application of a method in a specific context.

They are efficient and straightforward, gratifying, easier to retain and easier to sell !

Still they most likely apply to a context and can hardly be useful if elements of the context change.

Methods are less easy to retain and assimilate. They also often need to be ascertained through applications in various contexts before being accepted.

The bad thing with recipes is that they are sealed, and tend sometimes to occult the openness of their originating method.

One good demonstrative example of this is the Agile principles (method) vs. the multitude of – more or less ridiculous – rituals (recipes) falsely attributed to the originating method.

Some of the rituals may have been correctly applied in specific contexts producing suitable results. But, no doubt, with different context, the same 'successful' rituals may be disastrous.

It is easier to retain rituals than to understand principles… even easier to retain those rituals that you may find attractive!

Meta-models: towards a universal dependency injection framework

Intro

I joined an interesting presentation today about unit tests. Part of the presentation was related to dependency injection usage for unit testing. That brought to my mind again the benefits of meta-models.

The problem

Unit testing often faces the problem of having to instantiate objects that may impact the test itself or simply make the test impossible.

A sound example of this is when the method to be tested requires the instantiation of an object requiring, for instance, a database connection.

In this schema, we have 3 actors

  • The function
  • The caller
  • The object (SomeObject) which cannot be instantiated.

 

Traditional recipe

One, now traditional, recipe is to use an Interface (instead of the specific object) as a function parameter. And, according to the context, instantiate and use an object that implements the defined interface. The figure below illustrates this.

 

Good solution… a little acrobatic, but OK… good.

 

A problem, though. We now have 6 actors (to code and maintain):

  • The Function
  • The caller
  • The original 'true' object (SomeObject)
  • The Interface
  • The interface implementations (=2)!

 

On the other hand, testing a function may also need to instantiate a 'true' object context. In which case, we would have to rewrite (and recompileJ) our test code to instantiate a 'true' implementation when required.

A third point: in this solution, we defined the Interface to represent an abstraction of the original object. What if the original object itself was, for instance, a database record? This would then introduce a new actor in our playgroundJ

 

As Bjarne Stroustrup puts it:

"Any verbose and tedious solution is error-prone because programmers get bored" J

 

Meta-models may be a better way

In the current case, meta-models (see my previous posts) can be used to more simply describe all actors (object structures / methods / properties…).

An illustration:

 

 

Reminder: meta-models are closely related and enforced by Reflection (assemblies' meta-data). Through meta-models AND Reflection (namespace System.Reflection) developers can gain more flexibility to create versatile and scalable software.

 

In our present case, meta-models not only expose less actors to code and maintain, but also lower the complexity level of involved actors (for instance: maintaining database records instead of hard coding implementation).

 

The main goal for this approach is to ultimately write fewer universal methods to invoke and instantiate any object!

Will try to deliver a code sample in a future post. In the meantime, you may download meta-model sample code here!

TFS & SQL Server 2008R2 msxmlsql issues

I recently went through another new issue with TFS:

I had the TFS database and Data warehouse both installed on a SQL Server 2008 instance.

After installing a new SQL Server 2008R2 instance, TFS just stopped working complaining about database access.

It took me a while to re-discover that the source of annoyance was – again - the msxmlsql.dll and msxmlsql.rll files located at:

\Program Files\Microsoft SQL Server\100\Shared

And

\Program Files\Microsoft SQL Server\100\Shared\Resources\1033

respectively.

 

For some reason (seems useless to spend time searching J) the versions to use are with TFS are:

msxmlsql.dll (1,311,256 bytes); 07/10/2008; file version: 2007.100.1600.22

msxmlsql.rll (52 248 bytes); 07/10/2008

 

The files that caused my problem:

msxmlsql.dll (1 308 000 bytes bytes); 04/03/2010; file version: 2009.100.1600.1

msxmlsql.rll (48 992 bytes); 04/03/2010

 

 

 

 

MOD: Mur Oriented Development

MOD est un pattern connu de gestion de projets. Il s'agit de réussir son entrée dans le mur !

Sa pratique est assez simple : elle consiste justement à éviter, au dernier moment, de rentrer dans le mur. Adopter MOD est facile. Le maîtriser et le réussir est une autre affaire !

Champollion: 20 months and 20 days in ancient Egypt

 

Jean-François Champollion who made the first translation of the ancient hieroglyph (in 1822-1824, before ever going to Egypt) made his first (and last) journey to Egypt in 1828-1829. He spent 20 months and 20 days in this journey (of which the last 60 days in quarantine in Toulon when he was back homeJ).

An amazing book "Lettres écrites d'Égypte et de Nubie en 1828 et 1829 by Jean-François Champollion" (there should be an English translation… don't really know) contains a collection of letters - written to his friends, family and some officials- that recount this journey in a very smooth and pedagogic way. In an annex, the book contains a very dense description of the History of ancient Egypt and neighboring civilizations.

Champollion was evidently passionate about ancient Egypt. During this journey, he seems to be revisiting places and events that he knew quite well. And he recounts all of this in a fascinating way.

One thing that may seem a little strange for us, is the time spent in travelling. For instance: it took him several months to travel from Paris to Luxor (in the south of Egypt)… which really seems too long now (probably unacceptable!).

In the same time, he could compose (with his small team), in less than 2 months, more than 600 entire exact colorful drawing copies of all the monuments he visited (including endless hieroglyphic texts!). All in quite harsh travelling conditions between the Nile cataracts.

Near the end of his journey, he heard that Jerusalem's Archbishop decided to honor him with a distinguished prize (Croix de chevalier du saint-sépulcure). He recounts that getting hold of the prize was too expensive for him (200 Louis)!

The book is also available in an audio version (in French) on the great Free Litérature audio web site.

(Not sure you can write code while hearing such a bookJ)