Corridor Polygon Generation

by Gong Liu February 13, 2011 14:13

Problem Statement

Being able to search POI (points of interest) along a route within certain lateral range is a desirable feature for location based services. It makes the search result more relevant. For example, we may prefer a gas station that is 10 miles down on our route to a gas station that is 5 miles deviated from our route. Also, in geofencing applications we want to limit a vehicle, say a truck transporting hazardous materials, to travel only in a corridor area encompassing a predefined route. In this post, I will show you how to generate a corridor polygon for a given route and a radius - the lateral distance on each side of the route. 

Formulation

Consider a route consisting of a series of line segments. Take any two adjacent segments such as AB and BC and form a rectangle around each segment such as D'DEE' and G'GHH' as shown in Fig. 1.

 

Fig. 1. Two Adjacent Line Segments

If line segments AB and BC are not exactly in the same line, the two rectangles will have an overlapping region BE'F'G' on one side of the route and a gap BEFG on the other side. If we can find the intersecting points F and F', we can form the polygon D'DFHH'F'D' that closes the gap and eliminates the overlapping region. To do so, we first find the the coordinates of the four corners of the rectangle D'DEE' in terms of coordinates of points A and B and the radius r, as shown in Fig. 2.

Fig. 2. Coordinates of D, D', E and E'

Similarly, we can find the four corners of the rectangle G'GHH' in terms of coordinates of B and C and r, as shown in Fig. 3.

Fig. 3. Coordinates of G', G, H, and H'

The order of the points is important when dealing with polygons. We always order our points clockwise. Note that point F is the intersecting point of lines DF and HF, which can be expressed as follows:  

Fig. 4. Equations for Lines DF and HF

This is based on the fact that line DF has same slope as that of line AB and line HF has same slope as that of line BC. Now substitute point F in both equations and solve them for its coordinates:  

Fig. 5. Coordinates of Point F

Similarly, we can obtain the coordinates of the intersecting point F':

Fig. 6. Coordinates of Point F'

There are some special cases to consider, including when the slope of one of the two segments is infinity, the slopes of both segments are infinity, and the slopes of both segments are equal but not infinity. All of these cases can be solved easily with above formulas in some reduced forms, so I will not cover them here in detail. 

For a route with complex shape and many line segments, finding the corridor polygon is not as easy as just tracking the corner points and intersecting points because the corridor polygon may tangle or intersect itself or may even form holes inside it. To deal with these possible situations we need to apply our formulas in conjunction with polygon union operation. The basic idea is that once we find the intersecting points F and F', we treat D'DFF' and F'FHH' as two separate polygons, which will be called segment polygons, and remove their intersecting line FF' to form a single polygon, which will be called union polygon, through polygon union operation. We can devise an algorithm that applies the idea repeatedly to all adjacent segments of a route. Here is a high-level description of the algorithm:

  1. Find the first and the second segment polygons, a and b;
  2. Assign a to a variable u, representing the current union polygon;
  3. Assign b to a variable p, representing the polygon to be unioned with u;
  4. Find the next pair of adjacent segments' segment polygons, a and b; (Note: if current pair are the 1st and 2nd segments, the next pair will be the 2nd and 3rd, and the next next pair will be the 3rd and 4th, and so on.)
  5. Replace p's two vertexes with a's two corresponding vertexes;
  6. Union p with u and assign the result to u;
  7. Repeat steps 3 to 6 until the second last segment;
  8. Union b, which is by now the last segment polygon, with u and assign the result to u.

At the end of the process u becomes our final result. If at any point during the process a segment polygon may tangle or form holes with u, the polygon union algorithm will take care of it.       

I should point out that the corridor polygon D'DFHH'F'D' is only an approximate encompassing polygon due to the fact that FB > r, meaning some points in the polygon actually have a distance from the route greater than the radius. This problem gets worse when lines AB and BC forms a sharp angle. We could insert an arc with radius r between E and G (Fig. 7), but that changes the nature of a polygon and thus polygon operation, such as union, would not be applicable. Or, we could find point K, where BK = r, and redefine our segment polygon to include this point, instead of point F, as one of the vertexes. This would be a better approximation.

 

Fig. 7. Close the Gap with Arc EKG

Implementation

I wrote a small program in C# to implement the proposed corridor polygon generation algorithm. Fig. 8 shows the user interface of the program:

 

Fig. 8. Corridor Polygon Generator UI 

Here are some highlights about the implementation.

  • The program takes a route KML file as input and produces a corridor polygon KML as output. The reason for this is that we can visualize the result in Google Earth or Google Maps. In a POI search application, we would probably want to write the corridor polygon to a database so that it can be used in a SQL query to get POIs in the corridor.
  • The program uses General Polygon Clipping (GPC) library by The University of Manchester for polygon union operation. You can get more information about the library here.  
  • For a long, complex route the number of points used to describe the shape of the route (called shape points) can be huge. Lots of points are used to describe small turns, ramps and other trivial road features. Depending on the application, this level of detail may not be needed. If this is the case we can reduce the number of shape points dramatically (while still keeping the basic shape of the route) through a polyline reduction algorithm. In this program the Douglas-Peucker polyline reduction algorithm is used. Polyline Reduction Tolerance controls how severe you want the reduction to be. The bigger the number, the more points are removed from the original data set. Please refer to my earlier post regarding the Douglas-Peucker polyline reduction algorithm here.  
  • The idea of a "dog bone" shaped polygon is based on the thinking that once you are at the origin or destination of your route, you may want to look at POIs in a wider area. The feature is implemented by first creating two squares centered at the origin and destination, and then unioning them with the corridor polygon.  
  • The program supports 3D KML output. This is particular useful for visualization of a geo-fence. 

Examples

The following screenshots of Google Earth show the results from the Corridor Polygon Generator program. You can also view them "live" in Google Earth or Google Maps by clicking corresponding links at the bottom of each screenshot. 

Fig. 9 shows a corridor polygon of a simple route. The route consists of only 7 points, as shown under the Route Points folder in the left pane as well as in the map. The corridor polygon is actually drawn as a KML path.

Fig. 9. Corridor Polygon of a Simple Route

Fig. 10 shows a corridor polygon with a hole. In this case the corridor polygon and the hole are drawn as two separate paths as shown in the left pane. If there are more holes, each will be drawn separately.  

Fig. 10. Corridor Polygon with a Hole

Fig. 11 shows a corridor polygon for a complex route. To exam how well our algorithm works with a route that has a lot of twists and turns, I select a route that contains a section of highway 330 that passes through San Bernardino National Forest. Notice that the big spike is caused by the sharp angle formed by points 46, 47 and 48. If we have more shape points to describe the route more closely, we can expect that the sharp points will get smoothed out. This is exactly the case demonstrated in Fig. 12.

Fig. 11. Corridor Polygon of a Complex Route

Fig. 12. Corridor Polygon of a Complex Route with More Shape Points (less reduction)

Fig. 13. Dog Bone Shaped Corridor Polygon

Fig. 14. 3D Corridor Polygon Useful for Visualization of a Geo-fence

Download

You can download the executable of the program and all the example route files below. The download also includes the GPC library (gpc.dll). You need to install the .exe and .dll to the same folder. The C# wrapper of the GPC library depends on Microsoft Visual C++ run-time libraries (msvcr71.dll). So make sure it exists on your computer. 

CorridorPolygon.zip (36.1 kb)

A TreeView Based Options Component for Windows Mobile

by Gong Liu September 12, 2009 18:08

This article is also published on The Code Project. Please vote it there! 

Problem Statement 

Many Windows Mobile applications use an Options or a Settings dialog box to manage application level settings. The dialog box usually consists of a tab control with one or more regular controls on each tab such as labels, check boxes, radio buttons, dropdown lists, updowns, text boxes, etc. The following screenshots show some examples.

 

 

When designing such a dialog box, we need to consider carefully what kind of controls to use, how many controls on each tab, and how to layout the controls so that they look good and operatable in different screen resolutions, sizes and orientations (portrait and landscape). The layout issue becomes even trickier if we have to pop up a soft keyboard to collect user input. One way to deal with the layout issue is to design for the lowest common denominator - the lowest resolution and the smallest screen size. But often times we end up with using more tabs and fewer controls on each tab, a waste of valuable screen real estate if a user happens to have a device with higher resolution and/or bigger screen size. The following screenshots from a 480x800 WVGA device demonstrate the point. 

 

Application settings managed by an Options dialog box need to be persisted to a data store. In full .Net Framework, this is usually done with a Settings file, which corresponds to the <userSettings> section in the app.config file. At design time the Settings file is used to generate a Settings class (derived from System.Configuration.ApplicationSettingsBase) which provides strongly-typed accessors for each setting and the ability to save the settings to a user-specific file (user.config). Unfortunately, the Settings file mechanism does not exist in .Net Compact Framework. We have to either store the settings in the registry, which is prone to deployment and security issues, or devise our own way to store the settings, as did in AppSettings Implementation for Compact Framework by pbrooks and .NET Compact Framework ConfigurationManager by Shawn Miller. Both employed an XML file similar to the <appSettings> section of the app.config file. They treated application settings as "flat" key-value pairs with no structural support on how the settings might be organized.    

TreeView Based Options Component

In this article I propose using a TreeView control coupled with an XML file to manage application settings. The following screenshots show the component in action.

 

From UI point of view, the TreeView based Options component has these advantages:

  • No more layout headaches. It works well no matter how many options we have, and what screen resolution, size and orientation we use.
  • Options can be organized in groups, subgroups, etc.
  • Intuitive and joystick friendly (so a user can operate it with a single hand).
    • Move the joystick up and down to move the selection cursor (gray color) up and down.
    • Move the joystick to the right to expand a node.
    • Move the joystick to the left to collapse a node.
    • When current node is a value node, press the joystick down to select it.
    • When current node is a collapsed group or option node, press the joystick down to expand it.
    • When current node is a expanded group or option node, press the joystick down to collapse it.
  • Selected values are highlighted (in yellow).
  • Efficient use of screen area. No need to flip through different tabs or screens just to find the right option.
  • Consistent multiple-choice style operation for all options. Users don't need to learn different and sometimes confusing UIs.

The only requirement for using the component is that each option or setting must have a value selected from a set of discrete values, or like a multiple-choice. This isn't too restrict. UI controls such as radio buttons, dropdown list, updowns and check boxes are, in fact, multiple-choice type of controls. A text box, which is usually used for a continuous value option such as distance, weight, cache size, etc., should be avoided at any cost because it is such a hassle to input to a text box in a mobile device. So when dealing with a continuous value option, we should think of a way to discretize it instead. Can it be described reasonably well by a set of representative values in the particular context of our mobile application? Is it possible to break it down into several ranges, for example? An added benefit of discretization of all our options: we don't need input validation any more, as all the values are carefully selected and valid. 

The data used to populate the TreeView is stored in an XML file. The particular XML file has only three node types except the root node: group, option and value. An example of the XML file is shown below: 

<?xml version="1.0" encoding="utf-8" ?>
<options>
  <group name="General">
    <option name="TimeZone" displayName="Time zone">
      <value name="EST" selected="true" />
      <value name="CST" selected="false" />
      <value name="MST" selected="false" />
      <value name="PST" selected="false" />
    </option>
    <option name="UpdateInterval" displayName="Update interval">
      <value name="10" displayName="10 sec" selected="false" />
      <value name="30" displayName="30 sec" selected="true" />
      <value name="60" displayName="1 min" selected="false" />
      <value name="300" displayName="5 min" selected="false" />
      <value name="600" displayName="10 min" selected="false" />
    </option>
    <option name="CacheSize" displayName="Cache size">
      <value name="32" displayName="32 MB" selected="true" />
      <value name="64" displayName="64 MB" selected="false" />
      <value name="128" displayName="128 MB" selected="false" />
    </option>
    <option name="CheckInterval" displayName="Check for app update">
      <value name="0" displayName="Every time app starts" selected="true" />
      <value name="1" displayName="Every day" selected="false" />
      <value name="7" displayName="Every week" selected="false" />
      <value name="30" displayName="Every month" selected="false" />
      <value name="365" displayName="Every year" selected="false" />
    </option>
  </group>
  <group name="Appearance">
    <option name="Skin">
      <value name="Classic" selected="true" />
      <value name="IceFusion" displayName="Ice Fusion" selected="false" />
      <value name="Monochrome" selected="false" />
    </option>
    <option name="ShowToolbar" displayName="Show toolbar">
      <value name="true" selected="true" />
      <value name="false" selected="false" />
    </option>
    <option name="ShowStatusBar" displayName="Show status bar">
      <value name="true" selected="true" />
      <value name="false" selected="false" />
    </option>
  </group>
  <group name="SecurityPrivacy" displayName="Security &amp; Privacy">
    <option name="EnablePassword" displayName="Enable password protection">
      <value name="true" selected="true" />
      <value name="false" selected="false" />
    </option>
    <group name="SharedContents" displayName="Shared contents">
      <option name="ContactInfo" displayName="Contact info">
        <value name="true" selected="false" />
        <value name="false" selected="true" />
      </option>
      <option name="Photos">
        <value name="true" selected="true" />
        <value name="false" selected="false" />
      </option>
      <option name="Posts">
        <value name="true" selected="true" />
        <value name="false" selected="false" />
      </option>
    </group> 
  </group>
</options> 

There are some rules about this XML.

  • Each node type has a name and a displayName attributes. name, which is required, is used or referenced in our program. displayName, which is optional, is used in the TreeView for presentation. If a displayName is missing, the corresponding name is used for presentation.
  • group can contain zero or more option nodes and group nodes (or subgroups). We can have as many levels of embedded group nodes as we want. 
  • option must only contain one or more value nodes.
  • Only one of the multiple value nodes of an option can have a selected attribute of "true", indicating that it is the current value of the option.

From programming point of view, using such an XML as data store for our Options component has these advantages:

  • Both XML and TreeView are based on tree structure. One for storage and one for presentation. This perfect match makes programming easy.
  • Organizing options in groups and subgroups is inherently supported.
  • It makes it easy to manage both the selected values and all the available values. With the traditional Settings file, only selected values are persisted, whileas the available values are either in a separate resource file or hard-coded in the program.
  • To a certain extent we can change the options without having to recompile our program. It is also possible to update the XML remotely.
  • It makes localization easy. Just translate all the displayName attributes to different languages.

Implementation

For maximum flexibility I didn't make the Options "component" a user control or a class library. Just a simple class that you can copy and paste to your project.

public class OptionsManager
{
    private const string optionValueSeparator = ": ";
    private static XmlDocument xdoc = null;
    private static string theFile = null;
    private static Color selectedValueBackColor = Color.Yellow;
    private static bool isChanged = false; //is there any difference between xdoc and theFile

    static OptionsManager()
    {
        theFile = Path.GetDirectoryName(System.Reflection.Assembly.GetExecutingAssembly().
            GetName().CodeBase) + @"\Options.xml";
        xdoc = new XmlDocument();
        if (File.Exists(theFile))
            xdoc.Load(theFile);
        else
        {
            LoadDefault();
            Save();         //create theFile
        }
    }

    //load default options from embeded resource
    public static void LoadDefault()
    {
        using (StreamReader sr =new StreamReader(Assembly.GetExecutingAssembly().
            GetManifestResourceStream("TreeviewOptions.Options.Options.xml")))
        {
            xdoc.LoadXml(sr.ReadToEnd());
            sr.Close();
            isChanged = true;
        }
    }

    //Persist xdoc to theFile
    public static void Save()
    {
        if (isChanged)
        {
            xdoc.Save(theFile);
            isChanged = false;
        }
    }

    //Cancel changes to xdoc (DOM) by reloading it from theFile 
    public static void Cancel()
    {
        if (isChanged)
        {
            xdoc.Load(theFile);
            isChanged = false;
        }
    } 

    //Load xdoc to the specified TreeView
    public static void LoadToTreeView(TreeView tvw)
    {
        tvw.Nodes.Clear();
        XmlNode root = xdoc.DocumentElement;
        DoLoading(tvw, root);
    }

    //treeviewNode can be a TreeView or a TreeNode object
    private static void DoLoading(object treeviewNode, XmlNode xmlNode)
    {
        XmlNodeList xmlSubnodes = xmlNode.ChildNodes;
        foreach (XmlNode xsn in xmlSubnodes)
        {
            NodeType nodeType = GetXmlNodeType(xsn);
            if (nodeType == NodeType.Group)
            {
                string groupDisplayName = GetXmlNodeDisplayName(xsn);
                TreeNode tn = null;
                if (treeviewNode is TreeView)
                {
                    tn = ((TreeView)treeviewNode).Nodes.Add(groupDisplayName);
                    tn.Tag = string.Format("/group[@name='{0}']",
                        ((XmlElement)xsn).GetAttribute("name"));
                }
                else
                {
                    tn = ((TreeNode)treeviewNode).Nodes.Add(groupDisplayName);
                    tn.Tag = tn.Parent.Tag + string.Format("/group[@name='{0}']",
                        ((XmlElement)xsn).GetAttribute("name"));
                }
                DoLoading(tn, xsn);
            }
            else if (nodeType == NodeType.Option)
            {
                string optionDisplayName = GetXmlNodeDisplayName(xsn);
                TreeNode tn = null;
                if (treeviewNode is TreeView)
                {
                    tn = ((TreeView)treeviewNode).Nodes.Add(optionDisplayName);
                    tn.Tag = string.Format("/option[@name='{0}']",
                        ((XmlElement)xsn).GetAttribute("name"));
                }
                else
                {
                    tn = ((TreeNode)treeviewNode).Nodes.Add(optionDisplayName);
                    tn.Tag = tn.Parent.Tag + string.Format("/option[@name='{0}']",
                        ((XmlElement)xsn).GetAttribute("name"));
                }
                XmlNodeList values = xsn.ChildNodes;
                string selectedValueName = null;
                foreach (XmlNode v in values)
                {
                    string valueDisplayName = GetXmlNodeDisplayName(v);
                    TreeNode vtn = tn.Nodes.Add(valueDisplayName);
                    vtn.Tag = tn.Tag + string.Format("/value[@name='{0}']",
                        ((XmlElement)v).GetAttribute("name"));
                    if (((XmlElement)v).GetAttribute("selected") == "true")
                    {
                        vtn.BackColor = selectedValueBackColor;
                        selectedValueName = valueDisplayName;
                    }
                }
                tn.Text += optionValueSeparator + selectedValueName;
            }
        }
    }

    private static string GetXmlNodeDisplayName(XmlNode node)
    {
        string dName = ((XmlElement)node).GetAttribute("displayName");
        if (string.IsNullOrEmpty(dName))
            dName = ((XmlElement)node).GetAttribute("name");
        return dName;
    }

    //if tn is a value node, update tn.Parent display and corresponding xml value node selection
    public static void ChangeValue(TreeNode tn)
    {
        if (IsValueNode(tn))
        {
            //update tn.Parent display
            string parentDisplayName = Regex.Split(tn.Parent.Text, optionValueSeparator)[0];
            tn.Parent.Text = parentDisplayName + optionValueSeparator + tn.Text;
            tn.BackColor = selectedValueBackColor;
            TreeNodeCollection valueNodes = tn.Parent.Nodes;
            foreach (TreeNode vn in valueNodes)
            {
                vn.BackColor = (vn == tn) ? selectedValueBackColor : Color.Empty;
            }

            //update xml value node selection
            XmlNode option = xdoc.DocumentElement.
                SelectSingleNode("/options" + tn.Tag).ParentNode;
            XmlNodeList values = option.ChildNodes;
            foreach (XmlNode v in values)
                ((XmlElement)v).SetAttribute("selected", "false");
            ((XmlElement)xdoc.DocumentElement.SelectSingleNode("/options" + tn.Tag)).
                SetAttribute("selected", "true");

            isChanged = true;
        }
    }

    //If the XPath stored in tn.Tag ends with a value tag, then tn is a value treenode
    public static bool IsValueNode(TreeNode tn)
    {
        string path = (string)tn.Tag;
        string[] parts = path.Split("/".ToCharArray());
        return (parts[parts.Length - 1].StartsWith("value"));
    }

    //optionXPath is the XPath to the option whose value (name attribute) is to be retrieved.
    //The root /options can be omitted. 
    public static string GetOptionValue(string optionXPath)
    {
        if (!optionXPath.StartsWith("/options"))
            optionXPath = "/options" + optionXPath;
        XmlNode option = xdoc.DocumentElement.SelectSingleNode(optionXPath);
        if (option != null)
        {
            XmlNodeList values = option.ChildNodes;
            foreach (XmlNode v in values)
            {
                if (((XmlElement)v).GetAttribute("selected") == "true")
                    return ((XmlElement)v).GetAttribute("name");
            }
        }
        return null;
    }

    private static NodeType GetXmlNodeType(XmlNode node)
    {
        switch (node.Name)
        {
            case "options":
                return NodeType.Root;
            case "group":
                return NodeType.Group;
            case "option":
                return NodeType.Option;
            case "value":
                return NodeType.Value;
            default:
                throw new ApplicationException("Unknow Xml node type.");
        }
    }

    private enum NodeType
    {
        Root,
        Group,
        Option,
        Value
    }
}

Some highlights about the code:

First of all we need to make the XML file, Options.xml, an embedded resource by setting its Building Action property to Embedded Resource in Visual Studio. As indicated in the static constructor of our OptionsManager class, at the very first time the application starts, the XML file is loaded to memory from the embedded resource via the LoadDefault method and saved to the location where our application executable resides. In subsequent times, since the XML file already exists in our application root, we simply load it from there.  

The LoadToTreeView method loads the XML document to a specified TreeView control. Since we can have many levels of embedded group nodes, we need to do the loading recursively, as indicated in the private method DoLoading. For a group node, we show its displayName in the TreeView. For an option node, we show its displayName and its currently selected value's displayName (separated by ": "). For a value node, we show its displayName and if it is currently selected, we also set its background color to selectedValueBackColor. For each tree node, we construct an XPath to the corresponding XML node and store it to the tree node's Tag property. Later on we can easily match a tree node to an XML node with this XPath. As an example, the following table shows what the XPath looks like for a particular tree node:

Tree Node XPath
General/Time zone
option
/group[@name='General']/option[@name='TimeZone']
General/Time zone/PST
value
/group[@name='General']/option[@name='TimeZone']/value[@name='PST']

The ChangeValue method is called whenever we want to change the selected value of an option. This is usually triggered by the event of pressing down the joystick. We need to do two things in this method. First, in the TreeView control we need to update the display of the corresponding option node and change the highlighter to the value node that becomes currently selected. Second, in the underlying XML document we need to update the selected attribute of the value nodes of corresponding option to reflect which value is currently selected.    

The GetOptionValue method returns the selected value (the value's name attribute to be exact) of an option given the option's XPath. Since we know the details of our Options.xml file, it's up to us to cast the retrieved string value to a proper data type.

Using the OptionsManager Class

Here are the steps to use our OptionsManager class in a Windows Mobile project:

1. Create the Options.xml file and make it an embedded resource. Tips: Use the sample Options.xml file as a template. Make sure the namespace reference to the Options.xml file in the LoadDefault method is correct.

2. Add a Windows Form, OptionsForm, to the project. This will be our Options dialog box.

3. Add a TreeView control and the following four menu items or buttons to the OptionsForm:

  • Done - save changes to the options and close the Options dialog box
  • Cancel - cancel changes to the options and close the Options dialog box
  • Default - restore the options to their default values (as specified in the Options.xml stored in the embedded resource)
  • Change Value - change corresponding option's value to the value indicated by the TreeView selection cursor 

4. Wire up the Load and Closed event handlers of the OptionsForm like so:

private void OptionsForm_Load(object sender, EventArgs e)
{
    LoadTreeView();
}

private void OptionsForm_Closed(object sender, EventArgs e)
{
    if (this.DialogResult == DialogResult.OK)
        OptionsManager.Save();
    else
        OptionsManager.Cancel();
}

private void LoadTreeView()
{
    OptionsManager.LoadToTreeView(treeView1);

    //expand the first level
    TreeNodeCollection nodes = treeView1.Nodes;
    foreach (TreeNode n in nodes)
        n.Expand();

5. Wire up the KeyPress and AfterSelect event handlers of the TreeView control like so:

private void treeView1_KeyPress(object sender, KeyPressEventArgs e)
{
    if (OptionsManager.IsValueNode(treeView1.SelectedNode))
    {
        OptionsManager.ChangeValue(treeView1.SelectedNode);
    }
    else
    {
        if (treeView1.SelectedNode.IsExpanded)
            treeView1.SelectedNode.Collapse();
        else
            treeView1.SelectedNode.Expand();
    }
}

private void treeView1_AfterSelect(object sender, TreeViewEventArgs e)
{
    //make the Change Value menu item available only when the current tree node is a value node
    menuMenuChangeValue.Enabled = OptionsManager.IsValueNode(treeView1.SelectedNode);

6. Wire up the Click event handlers of the four menu items or buttons like so:

private void menuDone_Click(object sender, EventArgs e)
{
    this.DialogResult = DialogResult.OK;  
}

private void menuMenuCancel_Click(object sender, EventArgs e)
{
    this.DialogResult = DialogResult.Cancel;
}

private void menuMenuDefault_Click(object sender, EventArgs e)
{
    OptionsManager.LoadDefault();
    LoadTreeView();
}

private void menuMenuChangeValue_Click(object sender, EventArgs e)
{
    OptionsManager.ChangeValue(treeView1.SelectedNode);
}

7. Call the GetOptionValue method for any option value anywhere in the project. E.g.

int cacheSize = int.Parse(OptionsManager.GetOptionValue(
    "/group[@name='General']/option[@name='CacheSize']"));
bool sharePhotos = bool.Parse(OptionsManager.GetOptionValue(
    "/group[@name='SecurityPrivacy']/group[@name='SharedContents']/option[@name='Photos']"));

Further Improvements

The Options component can be further improved in following areas: 

  • Validate the Options.xml against an XSD schema.
  • Add icons to tree nodes through an ImageList control.
  • Allow only one of the same level group or option nodes to expand at a time. This mode is desirable for small screen sizes. 

Conclusions

A TreeView based Options component for Windows Mobile is proposed and implemented. It has several advantages over the traditional way of designing an Options dialog box. These includes elimination of layout issues, efficient use of screen area, intuitive and consistent UI, and sound structural support on persisting and organizing application settings. 

You can download the source code below:

TreeviewOptions.zip (49.31 kb)

Enum Pattern

by Gong Liu July 29, 2009 20:49

This article is also published on The Code Project. 

Introduction 

A programmer often has to deal with a fixed number of cases in his program. For example, if your program is about emergency management, you may consider following cases:

  1. Fire,
  2. Injured,
  3. Burglary,
  4. Blue Screen of Death,
  5. Run out of Beer

and your program may look like:

    int emergency = 3;
    switch (emergency)
    {
        case 1:
        case 2:
        case 3:
            Console.WriteLine("Call 911");
            break;
        case 4:
            Console.WriteLine("Sue Microsoft");
            break;
        case 5:
            Console.WriteLine("Brew your own");
            break;
    }

Here, each emergency case is assigned a number. The problem with it is that the program becomes hard to read if the reader doesn't know what each number stands for. This is where enum comes to the rescue:

    enum Emergency
    {
        Fire = 1,
        Injured,
        Burglary,
        Blue_Screen_of_Death,
        Run_out_of_Beer
    }

    Emergency emergency = Emergency.Injured;
    switch (emergency)
    {
        case Emergency.Fire:
        case Emergency.Injured:
        case Emergency.Burglary:
            Console.WriteLine("Call 911");
            break;
        case Emergency.Blue_Screen_of_Death:
            Console.WriteLine("Sue Microsoft");
            break;
        case Emergency.Run_out_of_Beer:
            Console.WriteLine("Brew your own");
            break;
    }

So enum is just a way of naming numbered cases. It makes your program more readable. In .Net it's very easy to get the names of numbered cases as strings:

    Console.WriteLine(emergency.ToString());
    //output: Injured
    Console.WriteLine(string.Join(",", Enum.GetNames(typeof(Emergency))));
    //output: Fire,Injured,Burglary,Blue_Screen_of_Death,Run_out_of_Beer 

However, in principle, you should reject the temptation of using enum names in the presentation layer, as the names are meant for the convenience of programmers, not for the users of your program. "Blue_Screen_of_Death" or even "BSoD" is perfectly fine in your program, but when presented to the users, it's just not that user friendly.

What if you do want to associate a user-friendly string to each enumerated case? Muaddubby in his article A Perfect C# String Enumerator was trying to do just that. He claims his string enumerator has all the right behaviors of a real enum. But he fails to address the fact that his enumerator is not a value type constant so it can't be used in a switch statement, nor can it do flag bit operations. So it is not that perfect after all. A better approach, as described in String Enumerations in C# by Matt Simner and Enum With String Values In C# by Stefan Sedich, is to leverage existing enum. They associate a string to an enumerated case by way of a custom attribute, and use reflection to gain access to the string via an extension method.

Enum Pattern 

From previous efforts of devising a string enumerator, it's evident that we need a general design pattern of associating a string, or any object for that matter, to an enumerated case. In fact, Matt Simner and Stefan Sedich in their articles have demonstrated a special case of the pattern. We just need to make it a little bit more generic so it can handle any object, not just a string. Here is what is involved:

Step 1, we need to define a base class that represents the attribute of an enumerated case.

    [AttributeUsage(AttributeTargets.Field, AllowMultiple = false, Inherited = true)]
    public class EnumAttr : Attribute
    {
        public EnumAttr()
        {
        }    
    } 

Since the attribute can be any object, we don't want it to have any particular behaviors by implementing methods or properties, except that it must apply to an enum field no more than once.

Step 2, we define the following extension method to gain access to the attribute object associated with an enum field:

    public static class EnumExtension
    {
        public static EnumAttr GetAttr(this Enum value)
        {
            Type type = value.GetType();
            FieldInfo fieldInfo = type.GetField(value.ToString());
            var atts = (EnumAttr[])fieldInfo.GetCustomAttributes(typeof(EnumAttr), false);
            return atts.Length > 0 ? atts[0] : null;
        }
    }

Step 3, define your own attribute class derived from EnumAttr.

Step 4, define your enum and add an instance of your attribute class in Step 3 to each enum field. Your enum can be regular or flagged.

Step 5, use your enum as usual. Whenever you need to access the attribute data of an enum field, just call the GetAttr() extension method.

Examples

The other day I was looking for something on Craig's List and wondered around to the personal classified ad section. To my surprise (well, not that surprised) I found that there were a lot more categories than just man-seeking-woman and woman-seeking-man. Here is a partial list:

    public class SexInterestAttr : EnumAttr
    {
        public string Desc { get; set; }
    }

    public enum SexInterest
    {
        [SexInterestAttr(Desc = "woman seeking man")]
        w4m,
        [SexInterestAttr(Desc = "man seeking man")]
        m4m,
        [SexInterestAttr(Desc = "man seeking woman")]
        m4w,
        [SexInterestAttr(Desc = "woman seeking woman")]
        w4w,
        [SexInterestAttr(Desc = "couple seeking couple")]
        mw4mw,
        [SexInterestAttr(Desc = "couple seeking woman")]
        mw4w,
        [SexInterestAttr(Desc = "couple seeking man")]
        mw4m,
        [SexInterestAttr(Desc = "woman seeking couple")]
        w4mw,
        [SexInterestAttr(Desc = "man seeking couple")]
        m4mw,
        [SexInterestAttr(Desc = "woman seeking lesbian couple")]
        w4ww,
        [SexInterestAttr(Desc = "man seeking gay couple")]
        m4mm,
        [SexInterestAttr(Desc = "gay couple seeking man")]
        mm4m,
        [SexInterestAttr(Desc = "lesbian couple seeking woman")]
        ww4w,
        [SexInterestAttr(Desc = "lesbian couple seeking man")]
        ww4m,
        [SexInterestAttr(Desc = "gay couple seeking woman")]
        mm4w,
        [SexInterestAttr(Desc = "man seeking lesbian couple")]
        m4ww,
        [SexInterestAttr(Desc = "woman seeking gay couple")]
        w4mm,
    }

Here, our attribute class, SexInterestAttr, contains only one property Desc, a user-friendly string to describe the sex interest. Notice that in our SexInterest enum we can use the object initializer syntax to create instance of SexInterestAttr. The following code snip shows how to use the enum and its attribute:

    var interests = (SexInterest[])Enum.GetValues(typeof(SexInterest));
    Console.WriteLine(string.Join(System.Environment.NewLine,
        interests.Select(i => string.Format("{0} - {1}", i.ToString(),
            ((SexInterestAttr)i.GetAttr()).Desc)).ToArray()));
Output:
    w4m - woman seeking man
    m4m - man seeking man
    m4w - man seeking woman
    w4w - woman seeking woman
    mw4mw - couple seeking couple
    mw4w - couple seeking woman
    mw4m - couple seeking man
    w4mw - woman seeking couple
    m4mw - man seeking couple
    w4ww - woman seeking lesbian couple
    m4mm - man seeking gay couple
    mm4m - gay couple seeking man
    ww4w - lesbian couple seeking woman
    ww4m - lesbian couple seeking man
    mm4w - gay couple seeking woman
    m4ww - man seeking lesbian couple
    w4mm - woman seeking gay couple

Adding attribute to enum doesn't alter its value type. We can still use it as usual such as in a switch statement:

    var interest = SexInterest.w4m;
    switch (interest)
    {
        case SexInterest.m4m:
            Console.WriteLine("you are a gay");
            break;
        case SexInterest.w4w:
            Console.WriteLine("you are a lesbian");
            break;
        case SexInterest.m4w:
        case SexInterest.w4m:
            Console.WriteLine("you are a hetero");
            break;
        default:
            Console.WriteLine("whatever. it's a free country");
            break;
    }
    //ourput: you are a hetero

As a side point, one of the advantages of using extension method is that it seemingly becomes part of our enum type and actually shows up in the IntelliSense:   

 

The above example is quite simple. We only associate a string to each enumerated case. Now let's take a look at a more complex example. Assume we have an enumeration of US presidents and each president can be described with the following PresidentAttr class:

    public class PresidentAttr : EnumAttr
    {
        public PresidentAttr(string name, string party, int yearTookOffice,
            int yearBorn, int yearDied)
        {
            Name = name;
            Party = party;
            YearTookOffice = yearTookOffice;
            YearBorn = yearBorn;
            YearDied = yearDied;
        }
        public string Name { get; set; }
        public string Party { get; set; }
        public int YearTookOffice { get; set; }
        public int YearBorn { get; set; }
        public int YearDied { get; set; }
        public bool IsAlive { get { return (YearDied <= 0); } }
        public int AgeTookOffice { get { return YearTookOffice - YearBorn; } }
    } 

Our President enum is defined as:

    public enum President
    {
        [PresidentAttr("George Washington", "No Party", 1789, 1732, 1799)]
        GeorgeWashington,
        [PresidentAttr("John Adams", "Federalist", 1797, 1735, 1826)]
        JohnAdams,
        [PresidentAttr("Thomas Jefferson", "Democratic-Republican", 1801, 1743, 1826)]
        ThomasJefferson,
        ...  
      
        [PresidentAttr("Bill Clinton", "Democratic", 1993, 1946, 0)]
        BillClinton,
        [PresidentAttr("George W. Bush", "Republican", 2001, 1946, 0)]
        GeorgeWBush,
        [PresidentAttr("Barack Obama", "Democratic", 2009, 1961, 0)]
        BarackObama
    } 

Now we can have some funs with our President enum:

    var presidents = (President[])Enum.GetValues(typeof(President));
    Console.WriteLine(string.Join(System.Environment.NewLine,
        presidents.Select(p => (PresidentAttr)p.GetAttr()).
        Select(a => string.Format("{0} ({1}-{2}), took office in {3}",
            a.Name, a.YearBorn, (a.YearDied<=0)? "" : a.YearDied.ToString(),
            a.YearTookOffice)).ToArray()));

Output:
    George Washington (1732-1799), took office in 1789
    John Adams (1735-1826), took office in 1797
    Thomas Jefferson (1743-1826), took office in 1801
    ...
    Bill Clinton (1946-), took office in 1993
    George W. Bush (1946-), took office in 2001
    Barack Obama (1961-), took office in 2009

    Console.WriteLine("There are {0} Democratic presidents",
        presidents.Count(p => ((PresidentAttr)p.GetAttr()).Party == "Democratic"));
    Console.WriteLine("They are:");
    Console.WriteLine(string.Join(System.Environment.NewLine,
        Array.FindAll(presidents, p => ((PresidentAttr)p.GetAttr()).Party == "Democratic").
        Select(p => ((PresidentAttr)p.GetAttr()).Name).ToArray()));

Output:
    There are 16 Democratic presidents
    They are:
    Andrew Jackson
    Martin Van Buren
    James K. Polk
    Franklin Pierce
    James Buchanan
    Andrew Johnson
    Grover Cleveland
    Grover Cleveland (2nd term)
    Woodrow Wilson
    Franklin D. Roosevelt
    Harry S. Truman
    John F. Kennedy
    Lyndon B. Johnson
    Jimmy Carter
    Bill Clinton
    Barack Obama

    Console.WriteLine("Presidents still alive: {0}",
        string.Join(",", Array.FindAll(presidents, p =>
            ((PresidentAttr)p.GetAttr()).IsAlive).Select(p =>
                ((PresidentAttr)p.GetAttr()).Name).ToArray()));

Output:
    Presidents still alive:
        Jimmy Carter,George H. W. Bush,Bill Clinton,George W. Bush,Barack Obama

    int maxAge = presidents.ToList().Max(p =>((PresidentAttr)p.GetAttr()).AgeTookOffice);
    var maxPAttr = (PresidentAttr)Array.Find(presidents, p =>
        ((PresidentAttr)p.GetAttr()).AgeTookOffice == maxAge).GetAttr();
    Console.WriteLine("The oldest president was {0}, a {1}, who took office at age {2}.",
        maxPAttr.Name, maxPAttr.Party, maxPAttr.AgeTookOffice);

Output:
    The oldest president was Ronald Reagan, a Republican, who took office at age 70.

In our last example we will demonstrate President enum with [Flags] attribute, or PresidentFlagged. Here is its definition:

    [Flags]
    public enum PresidentFlagged : long
    {
        [PresidentAttr("George Washington", "No Party", 1789, 1732, 1799)]
        GeorgeWashington = 0x1,
        [PresidentAttr("John Adams", "Federalist", 1797, 1735, 1826)]
        JohnAdams = 0x2,
        [PresidentAttr("Thomas Jefferson", "Democratic-Republican", 1801, 1743, 1826)]
        ThomasJefferson = 0x4,
        ...
        [PresidentAttr("Bill Clinton", "Democratic", 1993, 1946, 0)]
        BillClinton = 0x20000000000,
        [PresidentAttr("George W. Bush", "Republican", 2001, 1946, 0)]
        GeorgeWBush = 0x40000000000,
        [PresidentAttr("Barack Obama", "Democratic", 2009, 1961, 0)]
        BarackObama = 0x80000000000,
        _MostInfluential = AbrahamLincoln | FranklinDRoosevelt | GeorgeWashington
            | ThomasJefferson | AndrewJackson | TheodoreRoosevelt,
        _DiedInOffice = WilliamHenryHarrison | ZacharyTaylor | AbrahamLincoln | JamesAGarfield
            | WilliamMcKinley | WarrenGHarding | FranklinDRoosevelt | JohnFKennedy,
        _Assassinated = AbrahamLincoln | JamesAGarfield | WilliamMcKinley | JohnFKennedy,
    } 

Notice that we need to assign an integer number to each enum field in the order of 2^n in order for the flag bit operation to work. Also, we predefine three combined values, _MostInfluential, _DiedInOffice and _Assassinated. I prefer to prefix the combined values with an underscore "_" so they can be differentiated from single values and are put on top of the list of all possible values when displayed in the IntelliSense (see image below).

In the example we also need following helper method to parse a combined enum value into individual single enum values:

    private static PresidentFlagged[] ParseValues(PresidentFlagged combinedValue)
    {
        List<PresidentFlagged> values = new List<PresidentFlagged>();
        PresidentFlagged[] allvalues = (PresidentFlagged[])Enum.
            GetValues(typeof(PresidentFlagged));
        return Array.FindAll(allvalues, v =>
            ((combinedValue & v) == v) && !v.ToString().StartsWith("_"));
    } 

Notice when finding individual single values of a combined enum value we exclude the predefined combined values that are identified by the "_" prefix. Now the fun part:

    PresidentFlagged jfk = PresidentFlagged.JohnFKennedy;
    var jfkAttr = (PresidentAttr)jfk.GetAttr();
    Console.WriteLine("Was {0} died in office? {1}", jfkAttr.Name,
        ((PresidentFlagged._DiedInOffice & jfk) == jfk));
    Console.WriteLine("Was he Assassinated? {0}",
        ((PresidentFlagged._Assassinated & jfk) == jfk));

Output:
    Was John F. Kennedy died in office? True
    Was he Assassinated? True

    var Influentials = ParseValues(PresidentFlagged._MostInfluential);
    Console.WriteLine("Most influential presidents:");
    Console.WriteLine(string.Join(System.Environment.NewLine,
        Influentials.Select(p => ((PresidentAttr)p.GetAttr()).Name).ToArray()));

Output:
    Most influential presidents:
    George Washington
    Thomas Jefferson
    Andrew Jackson
    Abraham Lincoln
    Theodore Roosevelt
    Franklin D. Roosevelt

    var myFavorites = ParseValues(PresidentFlagged.AbrahamLincoln
        | PresidentFlagged.FranklinDRoosevelt
        | PresidentFlagged.BillClinton | PresidentFlagged.BarackObama);
    Console.WriteLine("My favorite presidents:");
    Console.WriteLine(string.Join(System.Environment.NewLine,
        myFavorites.Select(p => ((PresidentAttr)p.GetAttr()).Name).ToArray()));
    Console.WriteLine("Are they all Democratic? {0}",
        myFavorites.All(p => ((PresidentAttr)p.GetAttr()).Party == "Democratic"));

Output:
    My favorite presidents:
    Abraham Lincoln
    Franklin D. Roosevelt
    Bill Clinton
    Barack Obama
    Are they all Democratic? False

Conclusions

An enum pattern, in which each enumerated case is associated to an instance of a generic attribute class, is identified and implemented. It is particularly useful in situations where there is a finite number of cases and each case is characterized by a set of constants.

You can download the C# project below.

TestEnum.zip (9.74 kb)

ASP.Net Multithreading in a Web Farm Environment

by Gong Liu July 06, 2009 08:04

This article is also published on The Code Project

In one of my recent projects I have a situation where I need to generate two files on the server based on user input. Both files can be quite big (in terms of mobile devices), and take long time to generate by the server and to download by the user. The two files must be generated sequentially, as the second file depends on the first. One way to implement this would be to generate both files and then return to the user the download URLs in one request-response. The problem with this approach is that the user has to wait very long time before the server finishes the job. An obvious improvement is to return immediately after the first file is generated, and at the same time to spawn a new thread to generate the second file. This way, upon the request responded, the user can start to download the first file while the server is working on the generation of the second file. One problem with this approach is that the user will not know when the second file is ready for download. My solution is to create another page that allows the user to check the status of the second file. If it is ready, the response will include the download URL so the user can start to download it. If it is not ready, the user can either wait or do something else and check the status later. This works fine in my case, as the downloading time for the first file almost always longer than the time needed to generate the second file.

Another problem with this approach is that my ASP.Net application is running in a web farm environment in which I have a shared file store for the generated files and the newly spawned thread does not have proper permissions to write to the shared file store. The following diagram shows my simple web farm of two web servers, WS1 and WS2, and the file store. The file store is just a shared folder on one of the two web servers.

 

I use the steps below to configure the web servers so they can access to the shared folder. These steps apply to Windows 2000 (Advanced) Server OS. Yes! I'm still using Windows 2000 servers Smile

  1. Create a Windows user account, say "SharedUsr", on both WS1 and WS2. 
  2. Add <identity impersonate="true" userName="SharedUsr" password="xxxxxx"/> to web.config on both servers.
  3. Run these commands on both servers to grant "SharedUsr" access to the shared folder used by my ASP.Net application: 
    C:\WINNT\Microsoft.NET\Framework\v2.0.50727>aspnet_regiis -ga WS1\SharedUsr
    C:\WINNT\Microsoft.NET\Framework\v2.0.50727>aspnet_regiis -ga WS2\SharedUsr
  4. Make sure "SharedUsr" has write permission on the shared folder

This, however, does not work if the current thread spawns a new thread to write to the shared folder, because the new thread does not automatically impersonate "SharedUsr". I have to write code to force the impersonation. The following is the code. I have left out some details for clarity.  

......
using System.IO;
using System.Security.Principal;
using System.Threading;

public partial class GenerateFiles : System.Web.UI.Page
{
    private WindowsIdentity wid = null
    protected void Page_Load(object sender, EventArgs e)
    { 
        //Generate file1 ......

        wid = WindowsIdentity.GetCurrent(); //This is "SharedUsr" 
        try
        {
            //Use a thread from the threadpool to generate file2
            if (ThreadPool.QueueUserWorkItem(new WaitCallback(File2Callback),
                new File2Generator(file2Location)))
            {
                //Return file1 URL to user so he can start to download file1
                Response.Write(file1URL); 
            }
            else
            {
                Response.Write("Server too busy. The work item could not be queued.");
            }
        }
        catch (Exception ex)
        {
            Response.Write(ex.Message);
        }  
    }

    private void File2Callback(object o)
    {
        //Set the pooled worker thread's principal to that of wid   
        WindowsPrincipal principal = new WindowsPrincipal(wid);
        Thread.CurrentPrincipal = principal;

        //Make the the pooled worker thread to impersonate 'SharedUsr'
        WindowsImpersonationContext wic = wid.Impersonate();

        //Generate file2
        File2Generator f2gen = (File2Generator)o;
        f2gen.Generate();

        //Undo impersonation before return to threadpool
        wic.Undo();
    }
}

In the begining of Page_Load, we assume file1 has been generated. Then we use a worker thread from the threadpool to queue the generation of file2 for execution. The QueueUserWorkItem method has two parameters. The first parameter specifies the function to be called when the worker thread has its turn. The second parameter is the data to be passed to the function. In our case, it's an instantce of File2Generator class, which encompasses necessary data and functionality to generate file2. The implementation of File2Generator is not listed here because the detail is not important for making the point.

The callback function, File2Callback, will be executed on the worker thread that has the Windows identity "ASPNET", not "SharedUsr". So in it we need to change the worker thread's impersonation before calling the Generate method of File2Generator.

About

A seasoned computer professional. A tofu culture evangelist...
more >>

Tag Cloud

Calendar

<<  April 2017  >>
MoTuWeThFrSaSu
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

View posts in large calendar
Copyright © 2008-2011 Gong Liu. All rights reserved. | credits | contact me
The content on this site represents my own personal opinions, and does not reflect those of my employer in any way.