Favourite blogs for Anyone Can Post On The Internet

My favourites » codeMonkey.Weblog();

June 03, 2007

New Blog

Writing about web page http://www.aboutcode.net/

I have started a new blog http://www.aboutcode.net/

After I graduate, this blog will be discontinued. I’ll try to archive the old posts somewhere soon.

March 26, 2007

Pie v1.3.3 released

The new version of Pie (new name still pending) is out.
Download now
Uninstall any previous version first from Control Panel > Add or Remove Programs.

Report any bugs and suggest ideas to andrew@equin.co.uk or leave a comment here.
For the power users out there, the system event log will contain any errors that occurred when reporting it’s helpful to include them.


Podcasts from IE7

My podcast viewer currently runs standalone and as a plug-in for Windows Media Player.
How would people prefer to use it? I would love to make it a ClickOnce application that can be installed without being admin. This however would limit the ability to install the WMP plug-in. On the plus side, you receive automatic updates.
I am investigating ways to make the app ClickOnce install and then register the plug-in later. The problem is that the uninstall would not remove the plug-in for you.

In addition, I need a funky name for the app. PIE is a bit abstract and confusing with other products.
I quite like “PodBouncer”, but I’m open to options. The only real constraint is that the .com domain needs to exist.

equin.co.uk temporarily offline

Due to hard failure at the hosting company I use, my domain equin.co.uk is offline.
This means all my email is probably not working either. I’m as annoyed as you are, but these things do happen! They are restoring from back-ups at the moment. I hope everything is back to normal soon.

March 23, 2007

Prettier Pie

Follow-up to PIE! Podcasts from Internet Explorer from codeMonkey.Weblog();

OK, so the first HTML UI was a bit of a quickie…
I’ve made it a bit nicer now. In future versions you will be able to set your own style sheet as well to completely customise it.

Please send me your thoughts, ideas, comments, etc.

March 22, 2007

PIE! Podcasts from Internet Explorer

Follow-up to Updated Podcasts in Media Player Plugin from codeMonkey.Weblog();

After numerous and continued requests via this blog for a working version of the Windows Media Player podcast viewer plugin, I finally found the time to make it!

I have gone for the name Pie: Podcasts from Internet Explorer
Download it now!

Pie runs as an windows application or as a plug-in for Windows Media Player.
Pie gets the podcasts that have been downloaded by Internet Explorer 7’s feed engine.
You can expand items to read the show notes and click the show title to play.
The playlist button creates and plays a playlist of either all podcasts or just those not yet played.
In addition, an auto-playlist is added to the Windows Media Player library that will have all the podcasts. This is useful if you want to sync them to your MP3 player.
Main Screen
Windows Media Player Plug-in

March 14, 2007

Overriding implementation class members

Follow-up to Implementation Classes Again from codeMonkey.Weblog();

On the way home I thought of a way to override implementation class members in the user class.

class User
  use SomeImpl for IFooBar

  [OverrideImpl(IFooBar)] private SomeMethod() : void
    // specialized code...

class SomeImpl : IFooBar
  public virtual SomeMethod() : void
    // Normal code

The macro can translate this into “real” code by creating a new class inside User that inherits from the implementation class. We override the virtual method and make call to the User method.

The partial expansion then looks like this:

class User
  use SomeImpl_User_Overrides for IFooBar

  private SomeMethod() : void
    // Specialized code

  class SomeImpl_User_Overrides : SomeImpl
    private _user : User
    public this(user : User)
      _user = user

    public override SomeMethod()

So then we use the specialized class as the implementation.

This approach will also work for abstract methods defined in the implementation class that require implementation.

Implementation Classes Again

I’ve been thinking more about traits and implementation classes in OOP.
I put together a quick program in Nemerle to demonstrate the ideas I’m playing with.

I defined a class that implements System.ComponentModel.IEditableObject. It takes a “user” object as a parameter and implements a simple stack based state saver. BeginEdit copies all the fields of the user, pushing them onto the stack. CancelEdit can then restore state by popping the stack and setting the fields back to those saved values. EndEdit simply pops the stack leaving the current values in place.

    class EditableObject[T] : IEditableObject
        private _states : Stack[Dictionary[FieldInfo, object]] = Stack()
        private _user : T

        // We only take the reflection performance hit once per type T.
        private static _fields : array[FieldInfo]
        static this()
            _fields = typeof(T).GetFields(BindingFlags.NonPublic | BindingFlags.Public | BindingFlags.Instance)

        public this(user : T)
            _user = user

        public BeginEdit() : void

        public EndEdit() : void
            if (_states.Count > 0)
                _ = _states.Pop() // Discard top of stack
                throw InvalidOperationException()

        public CancelEdit() : void
            if (_states.Count > 0)
                throw InvalidOperationException()

        private CopyState() : Dictionary[FieldInfo, object]
            def dictionary = Dictionary()
            foreach (f in _fields)
                dictionary[f] = f.GetValue(_user)

        private RestoreState(previous : Dictionary[FieldInfo, object]) : void
            foreach (f in _fields)
                f.SetValue(_user, previous[f])

I now want to use this “implementation” class in many different classes. I do not want to inherit from this class directly. Trying to create an abstract base class purely to stuff lots of different implementation details together is just plain ugly too.
So I used the Nemerle ProxyPublicMembers macro.

    class Person : IEditableObject
        [ProxyPublicMembers] _editable : EditableObject[Person] = EditableObject(this)

        [Accessor(flags=WantSetter)] mutable _firstName : string
        [Accessor(flags=WantSetter)] mutable _surname : string

        public this(firstName : string, surname : string)
            _firstName = firstName
            _surname = surname

        public override ToString() : string
            $"$FirstName $Surname"

With the single line:
[ProxyPublicMembers] _editable : EditableObject[Person] = EditableObject(this)
the three public methods BeginEdit, CancelEdit, EndEdit are inserted into Person and they simply call the respective methods on the _editable instance field.

A simple test of the code is:

    static class Program
        static Main() : void
            def p1 = Person("Andrew", "Davey")

            p1.FirstName = "Foo" 

            p1.Surname = "Smith" 


Andrew Davey
Foo Davey
Andrew Davey
Andrew Smith

One of the advantages of this implementation class approach is the ability to store both instance and static state. The EditableObject only takes the reflection performance hit to get a type’s fields once. The user class never has to know about this state at all.

It would also be possible to enable a form of “overriding” by the user class. Perhaps it needs a special way to save and restore state. We just need a way to tell the implementation class to call the user to do something, rather than doing it itself. Delegates could be passed to the implementation class upon construction. Or perhaps a more declarative approach could be taken by marking “override” methods in a user class with an attribute.

[OverrideImplementation(EditableObject)] private CopyState() : Dictionary[FieldInfo, object]
  // do stuff here

We would just require some macro trickery to get this working I reckon.

As it stands the standard ProxyPublicMethods macro in Nemerle enables an excellent approach to modelling problems in clean OO style. I think an additional macro to tidy up the syntax would make things even nicer.

class Person
  uses EditableObject for IEditableObject


March 02, 2007

Multiple Interface Implementation via Proxy

Nemerle is like C# in that it only has single implementation inheritance and multiple interface inheritance. However when modelling business problems it would be beneficial to have multiple implementation inheritance to allow for better code reuse and modularisation.
For example, consider a PurchaseOrder object. We would like to add rich UI data binding functionality and undo/redo operations to it. The .NET framework contains a number of interfaces that should be implemented to achieve these goals. IEditableObject has methods BeginEdit, EndEdit and CancelEdit. INotifyPropertyChanged has an event PropertyChanged. The implementation of these is fairly standard so we do not want to write it in each class. In C#, we would usually make some kind of abstract base class that implements the interfaces and then inherit our real business classes from that.
Whilst this approach is fine for simple object models, things get a lot more difficult when not all business classes require all interfaces. Maybe some are read-only; maybe others have special auditing requirements. We end up creating many strange abstract base classes that implement different subsets of functionality. This inevitably leads to repeated code and a maintenance nightmare.
If we step back, we realise that we are actually abusing inheritance as an attempt to reduce code repetition. A better approach would be to have implementations of single interfaces as single classes that are then pulled together by the actual business classes. The business classes are then in charge of what implementations they require, rather than relying on a rather fragile base class.
The following Nemerle code demonstrates how this might work:

class PurchaseOrder : IEditableObject
    private _editableObject : IEditableObject
    public this()
        _editableObject = EditableObjectImplementation(this)
    public BeginEdit() : void
    public EndEdit() : void
    public CancelEdit() : void

The constructor creates and instance of some implementation class. Any calls to the interfaces methods are forwarded to the implementation class. Note that we provide the implementation class with the object that is using it. This allows the implementation class to do things like reflection to get all the private state to be saved.
Basically, we are implementing a form of the Proxy design pattern.
The above idea will work fine (even in C# and VB.NET), however it requires lots of “glue” code to be written. This is where Nemerle macros come in handy!
Imagine being able to write something like:

class PurchaseOrder \
    use EditableObjectImplemenation for IEditableObject \
    use NotifyPropChangedImpl for INotifyPropertyChanged
// Look! No glue code at all now!

The “use” macro would expand out to code that includes private instance fields and the glue code that calls those instances.
Of course, the macros have to be quite smart, but there are already working Proxy macros for Nemerle that just need enhancing to support events (they already do properties and methods I believe).
Other enhancements allow an implementation class to place demands on the class using it. An implementation of some interface ICircle could provide members like “Area”, “Circumference” and “Diameter” but require the using class to have a member “Radius”. The implementation class calls back into the using class to get Radius. It can then provide the various additional members using that value. This idea follows from the work done on Traits in OOP, the difference here is that implementation are not mixed into the using class at compile time. By keeping them outside, they can do useful things like have their own state.

The benefits of such infrastructure are:
  • Classes are more logically decomposed.
  • Classes are less fragile.
  • Maintenance is easier.
  • Testing business classes by providing stub implementation is easy.

February 26, 2007

Graph Vectorisation

Initial Network Vectorisation
I combined the junction detector with the line following algorithm. The result is a graph vectoriser! I still need to refine the algorithm so it only uses each junction exit once, but basically it works!

The rest of the week can now be spent building an interaction demo. :D

February 23, 2007

Junction Detection

Recently I have been focusing on detection of junctions and end points on a raster network. It is suprisingly difficult, but I have something that works nicely on test images.
Junctions Sample
The parameters the algorithm uses seem to be quite sensitive at the moment, this mainly due to the point grouping function. I need to come up with a more stable point grouper…

However, with the junction detector working vectorising a network is simple a case of line following out of one junction until reaching another!

February 07, 2007

Installing ClickOnce application as non–admin user

Insight shipped a while ago. It is deployed as a ClickOnce application. The bootstrap setup.exe created by the .NET SDK is excellent in that it detects missing pre-requisites on a user’s machine, downloads and installs them.
The problem is that a non-admin user will not be able to install components such as the .NET Framework, Microsoft Reporting Library, etc.
“Right-click, RunAs admin” on the setup.exe works except that the Start Menu entry for the application is put in the Administrator’s start menu and home directory. This means the user has to run Setup.exe again as themself! Argh, imagine the support calls on that one…

My solution is to make a ZIP file containing setup.exe, Install.bat and part2.bat.
Install.bat contains:

@echo off
set _wd_=%CD%

echo Installing Insight for %_User_%.
runas /u:%COMPUTERNAME%\Administrator "cmd.exe /c CD \"%_wd_%\" && part2.bat \"%_User_%\" \"%_wd_%\""

which upon running prompts:

Installing Insight for WORK\Andrew Davey.
Enter the password for WORK\Administrator: 

The user types the admin password, hits enter. That runs part2.bat:

@echo off
echo Giving %1 temporary Administrator status
net localgroup Administrators %1 /ADD
echo Running Insight install program
runas /u:%1 "cmd.exe /c CD %CD% && setup.exe" 
echo Removing %1's Administrator status
net localgroup Administrators %1 /DELETE

That adds the user to the Administrator group, then runs setup.exe as the user (but now with admin permissions). Afterwards, the user is removed from the Administrator group.

I took the idea from the MakeMeAdmin.cmd batch file. I could not seem to pass the current directory using MakeMeAdmin, so it could not find setup.exe. That’s why I have two batch files.
Maybe someone can point out how it should be done.

So the result is I can tell someone to download the ZIP, extract and double-click Install.bat. Whilst that’s not exactly “ClickOnce” anymore, it slightly better than the alternative! Of course once installed, any later application updates go into the user’s directory so no admin permissions are required.
I hope Microsoft update the bootstrapper in the next version so that it can handle non-admin users better.

February 02, 2007

Problems focusing

How come the best projects always come along at the busiest times? My mate Alex came to visit last weekend and we got talking about a great project. I don’t want to say too much here in case some sneaky bright-spark implements it before us! The project has great potential and really motivated me to get cracking on a prototype. This is the kind of motivation that makes me work until 3am without even realising!
Of course the problem with all this is that I should be working on my 3rd year uni project right now. In addition, I need to prepare for travelling back the Cornwall on the 8th to sell my primary school assessment tracking app “Insight”. I really should be doing reading for my various uni modules as well. I actually turned down some contract work with a regular client because I’m just too busy. I could have really done with the money too.
Uni is seeming less relevant every day. I have to stick it out, don’t I? My plan for when I finish is to start my own software company. I already have one great product, Insight, and this new project with Alex stands to be an awesome success as well. I guess a few more months won’t seem like a big deal in retrospect, but right now it feels like I’m wasting precious time that would better spent developing my company.
Maybe I should find out the university’s policy on defering my final year…
Heh, isn’t the world richest man a college drop out? ;)

January 17, 2007

Network Vectorization

My recent development efforts have focused on vectorizing networks (either graphs or trees). These structures often appear on maps as rivers and roads that branch out. This is a more general problem than simply capturing a single line. However the approach required to vectorize is in some ways simpler.

My algorithm so far is:
  1. Create “waypoints” on the network by repeatedly getting pixels with the most surrounding pixels withing a given radius. These are rough approximations to the center line that should be followed.
    Waypoints on a network
  2. Calculate best-fit lines at each waypoint (images scaled 2x)
    Best-fit lines on a network
  3. For each line-segment, check for intersections with the other lines. These intersections are the nodes of the polylines representing the network.

I am yet to create step 3. The algorithm will need some reasonable smarts to handle junctions well. I imagine something like “if a line-segment has more than two intersections, those intersection are junctions terminals”.

The primary limitation of the algorithm is the reliance on a fixed line width that manifests as a “radius” parameter used to determine nearby pixels. An improvement will be to calculate the line width at each pixel. I think this can be done by repeatedly increasing the radius until doing so actually reduces the amount of valid pixels captured. A negative weight is assigned to invalid pixels. The amount of negative weight really depends on how sensitive to noise the algorithm needs to be.

Thoughts so far

I didn’t get any work done on my project over Christmas. Things were just too busy. However, I did finish my last piece of external work. So I am now free to concentrate fully on university… (in theory!)

I am painly aware of the lack of reading done so far. I keep trying to find relevant papers, but whenever something good turns up I can’t get the damn content! I’m so sick of only reading great sounding abstracts. The library seems to be totally lacking the resources I need. I’m not sure where my tution fees are going!

I discussed this problem with my supervisor, who suggested emailling authors directly. Hopefully this will return some useful material.

My supervisor pointed out that vectorising raster images is a hard problem and told me not to expect great results in the short time available. Lots of work has been done in the area (though I can’t get the damn papers!). I have had lots of ideas myself, but I got the impression I should just be implementing existing ideas and reporting the results… sigh.

November 29, 2006

Point Grouping

Another part of my project is vectorising point objects on an image. The code for this is fairly simple, but I think I may want to re-use it to improve the line follower.
Points on Line

I am thinking about using the closest “point” as a hint to the next heading to take when following a line.

November 23, 2006

Line Follower

My initial line follower is working! It was tricky working out which end of a line segment, created by best fitting points, to follow each time. The code is still not perfect since tight hair-pin corners confuse it. The main assumption is that a line only changes direction gradually. So the line follower always try to continue in a direction close to the previous heading.
Here is a sample of a vectorized line (shown in red):

To improve performance when turning sharp corners I think the algorithm needs to be able to look at the image at different levels. Perhaps it can start with a small radius to capture points and grow it a few times to get a sample of possible headings. This would probably require the erasure of “used” points from the image.

In fact maintaining multiple possible paths could make the algorithm more adaptive. This would make junction handling easy. Both routes are taken, only one has to succeed.

Here is the NextSegment function so far:

        public NextSegment (prevPoint : Point, prevLine : Line) : (Point * Point * Line)
            def points = GetColoredPointsInCircle(prevPoint)
            def (centroid, angle) = BestFit(points)

            def rCosA = Cos(angle) * _radius
            def rSinA = Sin(angle) * _radius
            def startPoint = Point(centroid.X - rCosA, centroid.Y - rSinA)
            def endPoint = Point(centroid.X + rCosA, centroid.Y + rSinA)
            def line = Line(startPoint, endPoint)

            def betterStartPoint = match (line.Intersect(prevLine))
                | Line.Intersection.Point (pt) =>
                    if (PointInLineSegment(pt, startPoint, endPoint))
                | Line.Intersection.Parallel =>
                | Line.Intersection.Coincident =>

            def (next,l) = if (Abs(prevLine.AngleTo(line)) > PI/2)
                (startPoint, Line(line.Point2, line.Point1))
                (endPoint, line)

            _finished =  (next.DistanceTo(_end) < _radius)
            (betterStartPoint, next, l)

The code to choose the correct next point on the polyline is a bit of hack. Basically it has to flip the best fit “line” as well to ensure the heading is maintained. This block will be changed in future versions to include the multiple branching.

Line–Line Intersection

I decided to represent lines as two distinct points. Two lines can either:
  1. Intersect at a single point
  2. Be coincident (i.e. identical)
  3. Be parallel

I created an Intersection function on my Line type. It takes another Line and returns an Intersection value. “Intersection” is a union type representing the above three cases.

Here’s the code:

#pragma indent

using System
using System.Console
using System.Math
using Nemerle.Utility

namespace Prototype

    static class DoubleExtensions
        public static IsTiny(this d : double) : bool
            -double.Epsilon < d && d < double.Epsilon

    [Record] struct Point
        [Accessor] _x : double
        [Accessor] _y : double

        public override ToString () : string
            $"($_x, $_y)" 

        public static @:( pt : int * int ) : Point
            | (x,y) => Point(x,y)

        public static @:( pt : double * double ) : Point
            | (x,y) => Point(x,y)

    [Record] struct Line
        [Accessor] _point1 : Point
        [Accessor] _point2 : Point

        public Intersect (other : Line) : Intersection
            def Det (a,b,c,d)
                a * d - b * c

            def (x1,x2,x3,x4) = (Point1.X, Point2.X, other.Point1.X, other.Point2.X)
            def (y1,y2,y3,y4) = (Point1.Y, Point2.Y, other.Point1.Y, other.Point2.Y)

            def d1 = Det(x1, y1, x2, y2)
            def d2 = Det(x3, y3, x4, y4)
            def denom = Det(x1 - x2, y1 - y2, x3 - x4, y3 - y4)

            if (denom.IsTiny())
                def x = Det(d1, x1 - x2, d2, x3 - x4)
                def y = Det(d1, y1 - y2, d2, y3 - y4)
                if (x.IsTiny() && y.IsTiny())
                def x = Det(d1, x1 - x2, d2, x3 - x4) / denom
                def y = Det(d1, y1 - y2, d2, y3 - y4) / denom

        public variant Intersection
            | Parallel
            | Coincident
            | Point
                pt : Prototype.Point

using Prototype
def l1 = Line((1,1), (10,10))
def l2 = Line((0,1), (12,13))
def l3 = Line((5,1), (1,5))
def l4 = Line((0,0), (12,12))

def foos = [l1.Intersect(l2), l1.Intersect(l3), l1.Intersect(l4)]

foreach (i in foos)
    | Line.Intersection.Point(pt) => WriteLine($"Point $pt")
    | Line.Intersection.Coincident => WriteLine("Coincident")
    | Line.Intersection.Parallel => WriteLine("Parallel")

Some Nemerle gems:
1) Implicit cast from (int * int) to Point. This lets me use (1,3) in place of Point(1,3) – cuts down on the visual noise when building up lists of points!
2) match inside foreach

foreach (x in xs)
  | Foo => ...
  | Bar => ...

very cool!!

November 22, 2006

Line representation

What is the most sensible representation of a line? There are a few possibilities including:
  • Gradient and intercept: (y=mx+c)
  • Two distinct points: (x1,y1) & (x2, y2)
  • r = x cos(a) + y sin(a) : r = the perpendicular distance to the line. a = the angle r makes with the x-axis.

I suppose the actual operations I need to perform on lines should dictate the best represention to ease calculations. Using gradients gets tricky when dealing with vertical lines. Angles are preferable since they range between -Pi/2 and Pi/2.

The line following algorithm relies on calculating the intersection of lines. It produces start and end points of line segments. Therefore representing lines as two distinct points may be the best approach. Calculating the intersection of two lines represented this way is described here

Better Best Fit

As part of my code tidy up I have been thinking again about fitting a line to a set of points.
The new code uses the method described here

#pragma indent

using System
using System.Console
using System.Math
using System.Windows.Forms
using Nemerle.Utility
using Nemerle.Assertions

[Record] struct Point
    [Accessor] _x : double
    [Accessor] _y : double

    public this (x : int, y : int)
        _x = x
        _y = y

    public Offset (x : double, y : double) : Point
        Point(_x + x, _y + y)

    public override ToString () : string
        $"($_x, $_y)" 

module ListPointExts
    private static Sum[T] (items : list[T], f : T -> double) : double
        items.FoldLeft(0.0, (pt, a) => f(pt) + a)

    private static Centroid (points : list[Point]) : Point \
        requires points.Length > 0
        Point(Sum(points, pt => pt.X) / points.Length, Sum(points, pt => pt.Y) / points.Length)

    public static BestFit (this points : list[Point]) : (Point * double)
        def centroid = Centroid(points)
        def pts = points.Map(pt => pt.Offset(-centroid.X, -centroid.Y))

        def xySum = Sum(pts, pt => pt.X * pt.Y)
        def x2_y2Sum = Sum(pts, pt => pt.X * pt.X - pt.Y * pt.Y)

        if (-double.Epsilon < xySum && xySum < double.Epsilon)
            if (-double.Epsilon < x2_y2Sum && x2_y2Sum < double.Epsilon)
                // Points all evenly spaced around centroid
                // HACK: Return horizontal line for now
                (centroid, 0.0)
            else if (x2_y2Sum < 0)
                // Points lie on vertical line
                (centroid, PI / 2)
                // Points lie on horizontal line
                (centroid, 0.0)
            def b = x2_y2Sum / xySum
            def a1 = Atan( (-b + Sqrt(b*b + 4)) / 2 )
            def a2 = Atan( (-b - Sqrt(b*b + 4)) / 2 )

            def SumDistances(a)        
                def cos_a = Cos(a)
                def sin_a = Sin(a)
                def RotateY2(pt)
                    def y = (-pt.X * sin_a) + (pt.Y * cos_a)
                    y * y
                Sum(pts, RotateY2)

            if (SumDistances(a1) < SumDistances(a2))
                (centroid, a1)
                (centroid, a2)

def f = Form()
mutable pts : list[Point] = []

f.MouseUp += fun (_,e)
    if (e.Button == MouseButtons.Left)
        pts = Point(e.X, e.Y) :: pts
        pts = []

f.Paint += fun (_,e)
    when (pts.Length > 0)
        def (c, a) = pts.BestFit()

        def x1 = c.X - Cos(a) * 100
        def y1 = c.Y - Sin(a) * 100
        def x2 = c.X + Cos(a) * 100
        def y2 = c.Y + Sin(a) * 100
        e.Graphics.DrawLine(System.Drawing.Pens.Red, x1 :> int, y1:> int, x2:> int, y2:> int)

    foreach (pt in pts)
        e.Graphics.FillRectangle(System.Drawing.Brushes.Black, pt.X :> int, pt.Y :> int,1,1)


For now the function returns the centroid of the points and the angle of the line. One special case is when there is no “best” fit line because all points are evenly spaced around the centroid. When line following we would want to simply ignore the bogus angle and instead put a line through the centroid from the previous segment end point.
So the BestFit function really needs some kind of tagged union (variant in Nemerle) data type to return. I will create this once the line follower is formalized.