Waiting for multiple threads

Nice post on implementing a lock with timeout.

Though the code has two areas I would consider enhancing:
1) use WaitHandle.WaitAll to reflect the intent (and likelyhood) to aquire all locks or none [reason: performance]

2) There is a pathological case that two threads running at the same time will keep failing, if they hit the code for aquiring the locks in the for loop at the same time (since this is the case the code is written to handle it needs changing) - by implementing a variable amount of sleep time, thus ensuring that two threads that go to sleep at the same time don't wake up at the same time [reason: functional]

Anaglyphs and 3D vision

Oh a post about vision systems (about time!)

So you can write alot of code to try and interpret the 3D space in images or you can cheat and use the same technique that the brian uses (well it probably does not use pointers but thats another conversation)

So if you have two cameras you can position them side by side like eyes, and using a bit of DirectX coding take some pictures at the same time:

In the pictures above you can see that the images are slightly offset from each other (the wall on the left is not visible in the right picture), and from this you can generate Anaglyph image:

Now if you put your 3D spec's on (the kind that came with Shrek 3D DVD) you can see it in 3D!

The code? something like this does the trick (cue screams of fear! its unsafe code! it's got pointers and stuff! hide behind the sofa!

unsafe public Bitmap MakeAnaglyph()
  {
   Bitmap result = (Bitmap)_right.Clone();

   FastBitmap fbitRight = new FastBitmap(result, ImageLockMode.ReadWrite);
   FastBitmap fbitLeft = new FastBitmap(_left);

   FastBitmap.PixelData* pPixelRight;
   FastBitmap.PixelData* pPixelLeft;

   for (int y = 0; y < _right.Height; y++)
   {
    for (int x = 0; x < _right.Width; x++)
    {
     pPixelRight = fbitRight[x, y];
     pPixelLeft = fbitLeft[x, y];

     pPixelRight->red = pPixelLeft->red;
     pPixelRight->green = (byte)(pPixelRight->green * .82);
     pPixelRight->blue = (byte)(pPixelRight->blue * .95);
    }
   }

   fbitRight.Dispose();
   fbitLeft.Dispose();

   return result;
  }

This code uses my FastBitmap class, which justs makes working with the raw data a bit more obvious:

unsafe class FastBitmap: IDisposable
 {
  Bitmap _source;
  Rectangle _bounds;
  BitmapData _lockedBitmap;
  byte* _pBase;
  int _stride;

  [StructLayout(LayoutKind.Sequential)]
  public struct PixelData
  {
   public byte blue;
   public byte green;
   public byte red;
  }

  public FastBitmap(Bitmap source): this(source, ImageLockMode.ReadOnly)
  {
  }

  public FastBitmap(Bitmap source, ImageLockMode mode)
  {
   _source = source;
   _bounds = Bounds;
   _lockedBitmap = _source.LockBits(_bounds, mode, source.PixelFormat);
   _pBase = (byte*)(void*)_lockedBitmap.Scan0;
   _stride = _lockedBitmap.Stride;
  }
  public PixelData* this[int x, int y]
  {
   get
   {
    // Format32bppArgb - Specifies that the format is 32 bits per pixel; 
    // 8 bits each are used for the alpha, red, green, and blue components
    const int bytesPerPixel = 4; 

    PixelData* result = (PixelData*)(_pBase + (y * _stride) + (x * bytesPerPixel));

    return result;
   }
  }

  public Rectangle Bounds
  {
   get
   {
    GraphicsUnit unit = GraphicsUnit.Pixel;
    RectangleF bounds = _source.GetBounds(ref unit);

    Rectangle result = SizeToRectangle(bounds.Location, bounds.Size.ToSize());

    return result;
   }
  }


  private Rectangle SizeToRectangle(Size size)
  {
   return SizeToRectangle(new Point(0, 0), size);
  }

  private Rectangle SizeToRectangle(Point point, Size size)
  {
   return new Rectangle(point, size);
  }

  private Rectangle SizeToRectangle(PointF point, Size size)
  {
   return new Rectangle(new Point((int)point.X, (int)point.Y), size);
  }

  #region IDisposable Members

  public void Dispose()
  {
   if (_lockedBitmap != null)
   {
    _source.UnlockBits(_lockedBitmap);
    _lockedBitmap = null;
   }
  }

  #endregion
 }

How does this get you nearer to 3D vision? hint: red-blue differencing of the result...

Fibonacci and Big-Oh reduction

I was asked to write some C# to implement a Fibonacci sequence, which falls into two parts: 1) generate a single number in the sequence, 2) generating the whole sequence.

Note that most examples of this sequence generator have a nasty bug in them. Most examples use the int data type, whilst this code uses the long data type, otherwise this function overflows around n=47.

The naive way to implement this is recursively:

  /// <summary>
  /// slow version of fib calc for testing - warning
  /// runs in O(1.618..n) 
  /// </summary>
  internal long Fibonacci(int n)
  {
   if (n < 2)
    return n;
   else
    return Fibonacci(n - 1) + Fibonacci(n - 2);
  }

And a more optimal approach is:

  /// <summary>
  /// returns the Fibonacci number for N
  /// </summary>
  public long Fibonacci(int n)
  {
   // returns N where n < 2, for higher values of N
   // avoids recursive solution by keeping track
   // of previous results

   long fn = 0;

   if (n < 0) // offset must be positive
    throw new NotSupportedException("Fibonacci sequence offset must be positive");
   else if (n < 2) // returns N where N < 2
    fn = n;
   else // use caching technique for higher values of N
   {
    long fnMinusTwo = 0;
    long fnMinusOne = 1;

    for (long ni = 2; ni <= n; ni++)
    {
     // effectively: fn = Fibonacci(n - 1) + Fibonacci(n - 2)
     fn = fnMinusOne + fnMinusTwo;

     fnMinusTwo = fnMinusOne;
     fnMinusOne = fn;
    }
   }

   return fn;
  }

The latter approach is much more efficient O(n) vs O(1.618..ⁿ). However its not as simple as the former. Another approach is to take the former solution and use a local cache:

  /// <summary>
  /// caching version of fib calc
  /// </summary>
  Dictionary<int, long> fibCache = new Dictionary<int, long>();
  internal long Fibonacci(int n)
  {
   long fn = 0;

   // use value from cache if already calculated
   if (fibCache.ContainsKey(n))
    return fibCache[n];

   // not cached, need to work it out
   if (n < 2)
    fn = n;
   else
    fn = Fibonacci(n - 1) + Fibonacci(n - 2);

   // add to cache
   fibCache.Add(n, fn);

   return fn;
  }

This gives us an O(n) runtime with a reasonably simple implementation. This is of course the classic trade-off of time vs. space - we have increased space used (the dictionary) to decrease time.

Finally we want to generate the whole sequence, which we can do in a lazy evaluation way using the yield keyword:

  /// <summary>
  /// returns the first N items in the Fibonacci sequence
  /// </summary>
  public static IEnumerable<long> FibonacciSequence(int n)
  {
   for (int fn = 0; fn < n; fn++)
    yield return Fibonacci(fn);
  }

OpenStreetMap into SQL Server 2008 first steps

So as I said in my previous post "OpenStreetMap - show me some data" the next step in evaluating the use of the OSM data was to see how SQL Server 2008 Spatial features might help.

The first thing I wanted to look at was how to define the structure in SQL and work with it from C#. This was mainly to get a feeling for the data types involved. In SQL I created a database (UKGeo) and a table:

CREATE TABLE [dbo].[Nodes](
 [id] [int] NOT NULL,
 [location] [geography] NOT NULL,
 CONSTRAINT [PK_Nodes] PRIMARY KEY CLUSTERED 
(
 [id] ASC
)WITH (PAD_INDEX  = OFF, STATISTICS_NORECOMPUTE  = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
) ON [PRIMARY]

The key point is to note the datatype "geography" being used for the location field, this datatype can handle a number of GIS related structures. We also need a stored procedure to load the data:

CREATE PROCEDURE [dbo].[sp_NodeCreate]
 @id int, 
 @location geography
AS
BEGIN
 -- SET NOCOUNT ON added to prevent extra result sets from
 -- interfering with SELECT statements.
 SET NOCOUNT ON;

 INSERT INTO Nodes(id, location) VALUES (@id, @location);
END

Once again it's a simple enough procedure, with the use of "geography" being the only complexity. From C# we just need to create a command pointing to this stored procedure:

   string sql = "sp_NodeCreate";
   SqlCommand command = new SqlCommand(sql, connection);
   command.CommandType = CommandType.StoredProcedure;

and when setting up the parameters we need to specify that the @location parameter is a Udt (user defined type), in this case geography is already registered in SQL, so we can just name it:

   SqlParameter idParam = new SqlParameter("@id", SqlDbType.Int);
   SqlParameter geoParam = new SqlParameter("@location", SqlDbType.Udt);
   geoParam.UdtTypeName = "geography";
   command.Parameters.Add(idParam);
   command.Parameters.Add(geoParam);

and finally a function to call the procedure:

 private void CreateNodeInDatabase(string id, string longtitude, string latitude)
  {
   SqlGeographyBuilder builder = new SqlGeographyBuilder();
   builder.SetSrid(4326);

   builder.BeginGeography(OpenGisGeographyType.Point);

   builder.BeginFigure(double.Parse(longtitude), double.Parse(latitude));
   builder.EndFigure();

   builder.EndGeography();

   SqlGeography geo = builder.ConstructedGeography;

   command.Parameters["@id"].Value = id;
   command.Parameters["@location"].Value = geo;

   command.ExecuteNonQuery();
  }

This code uses the SqlGeographyBuilder to create an instance of type Point, which is what we want location to contain. I'm sure this code is not the best way to do this, but it serves as a starting point for understanding the relationship between SQL and CLR implementations of spatial information.

OpenStreetMap - show me some data

Project Colbolt requires some understanding of space (actually another project does as well, but one thing at a time!) so I am going to use OpenStreetMap, as it gives me access to the underlying data. I'm not sure I can go the whole way using this - I will have to read the copyright and terms.

 

However, the first part of the plan is to take the OSM data and start to understand it. What I already like is that this is a real sized data set, the UK alone is ~1.2gb of XML, the world is 5.3gb as a zip file. So I'm looking forward to some proper coding. Since I worked in direct marketing a few years ago large geographical datasets are great fun for me (sad git).

 

The stats say that the dataset for the world contains :

• nodes 278 millon;
• ways 23 millon;
• relations 41 thousand.

Node = GPS point (long/lat)

Way = a list of nodes describing a map feature (streets, fields etc)

Relation = a more complex grouping, normally of ways

 

My first step was to play with just the UK data, (always start with a small dataset that you know roughly what it should look like).

 

I wrote a little C# application to read the UK file, which gave me back some stats:

• nodes 6,441,456;
• ways 873,054;
• relations 1,362

So this means we can apply a rough estimate that anything about the UK data can be sized up to the world by multiplying it by 42 (thanks for all the fish!).

Knowing there was no sensible way to try and load the whole XML file into memory (especially when we come back to the world data) I used an XmlReader to process the data. A quick scan which processed all the tags and added up these counts takes less than 30 secs for the UK - so the rule of 42 says it would take about 20 minutes to read the whole world.

 

A stripped down node (removing editing information) looks like:

 

<node id="int" lat="float" long="float">

 

In terms of trying to hold it in memory, stuffing the UK nodes into a List<float[2]> as a pair of floats required 150mb of memory, a sparse array fell over after 1gb and a Dictionary<int, float[2]> used 379 mb.

 

The List<float[2]> approach would lose the node id, which is not really a valid comparison, though I could just use a BitArray to hold the id (as big as the largest ID, a 1 indicating if its in the List<float[2]>, and the number of 1s before it indicating its offset) - this would require another 1mb of memory, but would be slower that the Dictionary approach (not validated this). In either case this is all moot as the rule of 42 shows we would need 7gb just to hold the nodes for the world - and at this stage I'm not doing that!. So we are going to need a storage system...

 

The code so far, is skeletal, but shows what we have to do to process the OSM format - note I could have skipped most of the data, but I wanted to get a fair idea of what reading the data takes:

 

 

  static void Main(string[] args)
  {
   XmlReader reader = XmlReader.Create(@"k:\geo\uk-081015.osm");

   Importer importer = new Importer(reader);
  }

and the Importer class:

 public class Importer
 {
  int nodes = 0;
  int ways = 0;
  int relations = 0;

  public Importer(XmlReader reader)
  {
   // skip boring stuff
   reader.MoveToContent();

   reader.ReadStartElement("osm");

   while (reader.IsStartElement())
   {
    string name = reader.Name;

    switch (name)
    {
     case "bounds":
      ReadBound(reader);
      break;
     case "node":
      ReadNode(reader);
      break;
     case "way":
      ReadWay(reader);
      break;
     case "relation":
      ReadRelation(reader);
      break;
     default:
      throw new Exception("Unknown element encounterd " + name);
    }
   }

   reader.ReadEndElement(); // osm

   Console.WriteLine("nodes {0} ways {1} relations {2}", nodes, ways, relations);
  }

  private void ReadBound(XmlReader reader)
  {
   reader.ReadStartElement();
   reader.Skip();
  }

  private void ReadNode(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");
   string latitude = reader.GetAttribute("lat");
   string longtitude = reader.GetAttribute("lon");

   reader.ReadStartElement(); // node
   reader.Skip();
   nodes++;

   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // node
  }

  private void ReadWay(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");

   reader.ReadStartElement(); // way
   reader.Skip();
   ways++;

   while (reader.Name == "nd")
   {
    reader.ReadStartElement();
    reader.Skip();
   }
   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // way
  }

  private void ReadRelation(XmlReader reader)
  {
   // get attributes
   string id = reader.GetAttribute("id");

   reader.ReadStartElement(); // relation
   reader.Skip();
   relations++;

   while (reader.Name == "member")
   {
    reader.ReadStartElement();
    reader.Skip();
   }
   while (reader.Name == "tag")
   {
    reader.ReadStartElement();
    reader.Skip();
   }

   if (reader.NodeType == XmlNodeType.EndElement)
    reader.ReadEndElement(); // relation
  }

So as a first pass I'm going to stick it into SQL Server 2008 and see what the spatial features can do...

Markov chain code

A follow up to my markov chain posts, here's the code for a generic markov chain in C#:

A markov chain:

 /// <summary>
 /// Chain implements a markov chain for a type T
 /// allows the generation of sequences based on
 /// a sample set of T items
 /// </summary>
 /// <typeparam name="T">the type of elements</typeparam>
 public class Chain<T>
 {
  Link<T> root = new Link<T>(default(T));
  int length;

  /// <summary>
  /// creates a new chain
  /// </summary>
  /// <param name="input">Sample set</param>
  /// <param name="length">window size for sequences</param>
  public Chain(IEnumerable<T> input, int length)
  {
   this.length = length;
   root.Process(input, length);
  }

  /// <summary>
  /// generate a new sequence based on the samples first entry
  /// </summary>
  /// <param name="max">maximum size of result</param>
  /// <returns></returns>
  public IEnumerable<T> Generate(int max)
  {
   foreach (Link<T> next in root.Generate(root.SelectRandomLink().Data, length, max))
    yield return next.Data;
  }

  /// <summary>
  /// generate a new sequence based on the sample
  /// </summary>
  /// <param name="start">the item to start with</param>
  /// <param name="max">maximum size of result</param>
  /// <returns></returns>
  public IEnumerable<T> Generate(T start, int max)
  {
   foreach (Link<T> next in root.Generate(start, length, max))
    yield return next.Data;
  }
 }

consists of links:

 /// <summary>
 /// parts of a chain (markcov)
 /// </summary>
 /// <typeparam name="T">link type</typeparam>
 internal class Link<T>
 {
  T data;
  int count;
  // following links
  Dictionary<T, Link<T>> links;

  private Link()
  {
  }

  /// <summary>
  /// create a new link
  /// </summary>
  /// <param name="data">value of the item in sequence</param>
  internal Link(T data)
  {
   this.data = data;
   this.count = 0;

   links = new Dictionary<T, Link<T>>();
  }

  /// <summary>
  /// process the input in window sized chunks
  /// </summary>
  /// <param name="input">the sample set</param>
  /// <param name="length">size of sequence window</param>
  public void Process(IEnumerable<T> input, int length)
  {
   // holds the current window
   Queue<T> window = new Queue<T>(length);

   // process the input, a window at a time (overlapping)
   foreach (T part in input)
   {
    if (window.Count == length)
     window.Dequeue();
    window.Enqueue(part);

    ProcessWindow(window);
   }
  }

  /// <summary>
  /// process the window to construct the chain
  /// </summary>
  /// <param name="window"></param>
  private void ProcessWindow(Queue<T> window)
  {
   Link<T> link = this;

   foreach (T part in window)
    link = link.Process(part);
  }

  /// <summary>
  /// process an item following us
  /// keep track of how many times
  /// we are followed by each item
  /// </summary>
  /// <param name="part"></param>
  /// <returns></returns>
  internal Link<T> Process(T part)
  {
   Link<T> link = Find(part);

   // not been followed by this
   // item before
   if (link == null)
   {
    link = new Link<T>(part);
    links.Add(part, link);
   }

   link.Seen();

   return link;
  }

  private void Seen()
  {
   count++;
  }

  public T Data
  {
   get
   {
    return data;
   }
  }

  public int Occurances
  {
   get
   {
    return count;
   }
  }

  /// <summary>
  /// Total number of incidences after this link
  /// </summary>
  public int ChildOccurances
  {
   get
   {
    // sum all followers occurances
    int result = links.Sum(link => link.Value.Occurances);

    return result;
   }
  }

  public override string ToString()
  {
   return String.Format("{0} ({1})", data, count);
  }

  /// <summary>
  /// find a follower of this link
  /// </summary>
  /// <param name="start">item to be found</param>
  /// <returns></returns>
  internal Link<T> Find(T follower)
  {
   Link<T> link = null;

   if (links.ContainsKey(follower))
    link = links[follower];

   return link;
  }

  static Random rand = new Random();
  /// <summary>
  /// select a random follower weighted
  /// towards followers that followed us
  /// more often in the sample set
  /// </summary>
  /// <returns></returns>
  public Link<T> SelectRandomLink()
  {
   Link<T> link = null;

   int universe = this.ChildOccurances;

   // select a random probability
   int rnd = rand.Next(1, universe+1);

   // match the probability by treating
   // the followers as bands of probability
   int total = 0;
   foreach (Link<T> child in links.Values)
   {
    total += child.Occurances;

    if (total >= rnd)
    {
     link = child;
     break;
    }
   }

   return link;
  }

  /// <summary>
  /// find a window of followers that
  /// are after this link, returns where
  /// the last link if found, or null if
  /// this window never occured after this link
  /// </summary>
  /// <param name="window">the sequence to look for</param>
  /// <returns></returns>
  private Link<T> Find(Queue<T> window)
  {
   Link<T> link = this;

   foreach (T part in window)
   {
    link = link.Find(part);

    if (link == null)
     break;
   }

   return link;
  }

  /// <summary>
  /// a generated set of followers based
  /// on the likelyhood of sequence steps
  /// seen in the sample data
  /// </summary>
  /// <param name="start">a seed value to start the sequence with</param>
  /// <param name="length">how bug a window to use for sequence steps</param>
  /// <param name="max">maximum size of the set produced</param>
  /// <returns></returns>
  internal IEnumerable<Link<T>> Generate(T start, int length, int max)
  {
   var window = new Queue<T>(length);

   window.Enqueue(start);

   for (Link<T> link = Find(window); link != null && max != 0; link = Find(window), max--)
   {
    var next = link.SelectRandomLink();

    yield return link;

    if (window.Count == length-1)
     window.Dequeue();
    if (next != null)
     window.Enqueue(next.Data);
   }
  }
 }

which can be called:

static void Main(string[] args)
{
 // sample data set
 string seed = Tidy(@"Twinkle, twinkle, little star,
 How I wonder what you are!
 Up above the world so high,
 Like a diamond in the sky!

 When the blazing sun is gone,
 When he nothing shines upon,
 Then you show your little light,
 Twinkle, twinkle, all the night.

 Then the traveller in the dark,
 Thanks you for your tiny spark,
 He could not see which way to go,
 If you did not twinkle so.

 In the dark blue sky you keep,
 And often through my curtains peep,
 For you never shut your eye,
 Till the sun is in the sky.

 As your bright and tiny spark,
 Lights the traveller in the dark,—
 Though I know not what you are,
 Twinkle, twinkle, little star.
 ");

 // tokenise the input string
 var seedList = new List<string>(Split(seed.ToLower()));
 // create a chain with a window size of 4
 var chain = new Chain<string>(seedList, 4);

 // generate a new sequence using a starting word, and maximum return size
 var generated = new List<string>(chain.Generate("twinkle", 2000));
 // output the results to the console
 generated.ForEach(item => Console.Write("{0}", item));
}

// tokenise a string into words (regex definition of word)
private static IEnumerable<string> Split(string subject)
{
 List<string> tokens = new List<string>();
 Regex regex = new Regex(@"(\W+)");
 tokens.AddRange(regex.Split(subject));

 return tokens;
}

Giving output such as:

twinkle, little star,
how i know not twinkle so.

in the sky.

as your tiny spark,
lights the sky!

when the night.

then the traveller in the dark blue sky you never shut your eye,
till the sky.

as your eye,
till the sun is gone,
when he nothing shines upon,
then you are!
up above the dark,
thanks you did not what you are,
twinkle, twinkle, all the sky!

One of the interesting side-effects of tokenizing using a simple regex is that if the input stream is HTML the Markov chain will treat HTML as words as well and therefore not only generate text that looks like the input, but is also formatted like the input - this also works for punctuation.

Rotating a string

Code snippet to rotate a string:

static void Main(string[] args)
{
 string subject = "abcdefg";

 // test harness, check it handles multiples of size and negatives and zero
 for (int amount = -subject.Length * 3; amount < subject.Length * 3; amount++)
 {
  string result = RotateStringTest(subject, amount);

  char[] inplace = subject.ToCharArray();

  RotateString(inplace, amount);

  if (amount % subject.Length == 0)
   Debug.Assert(result.CompareTo(subject) == 0);
  Debug.Assert(result.CompareTo(new String(inplace)) == 0);
 }
}

/// <summary>
/// Rotates a string
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static void RotateString(char[] subject, int amount)
{
 int length = subject.Length;

 // negate rotations can be re-expressed as positive amounts
 if (amount < 0)
  amount = length - (-amount % length);

 // 0 rotation mean return unchanged
 if (amount % length == 0)
  return;

 int dest = amount;
 char prev = subject[0];

 do
 {
  dest %= length;

  Swap(ref subject[dest], ref prev);

  dest += amount;
 } while (dest != amount);
}

/// <summary>
/// swaps two chars wihout using temp variable
/// </summary>
private static void Swap(ref char a, ref char b)
{
 a ^= b;
 b ^= a;
 a ^= b;
}

/// <summary>
/// Rotates a string test (slow)
/// </summary>
/// <param name="subject">string to rotate</param>
/// <param name="amount">&lt; 0 left, 0 none, &gt; 0 right</param>
/// <returns></returns>
private static string RotateStringTest(string subject, int amount)
{
 char[] result = subject.ToCharArray();
 int length = subject.Length;

 // negate rotations can be re-expressed as positive amounts
 if (amount < 0)
  amount = length - (-amount % length);

 // 0 rotation mean return unchanged
 if (amount % length != 0)
 {
  for (int pos = 0; pos < length; pos++)
  {
   int dest = (pos + amount) % length;

   result[dest] = subject[pos];
  }
 }

 return new String(result);
}

ps this post was really just to test this javascript code hightlighter.. It seems to work very well for both Xaml and C# - cool!

Silverlight Eyes (Seyes) : eyes follow the mouse in Silverlight (aka xeyes)

Silverlight Eyes (Seyes) watches what you do and reports it to the Boss:



This code uses two main mechanism to achieve the effect

1. It uses Polar coordinates to calculate where the focal point is relative to the centre of each eyeball. (Often the problem people look for as finding the angle between two points). The code uses the angle to calculate what direction the pupil should be facing, and uses the radius (or distance) to proportionally move the pupil away from the centre.


2. It uses clipping to ensure that the pupil is always within the eye ball, which is accomplished by grouping the shapes into a canvas with a clipping region the same size of the eyeball.

The code also allows the user to visualize the calculations taking place by checking/unchecking the checkbox in the top left hand corner. Checking this shows the focal point, the lines of sight from each eye and the key values at the top (angle, distance, start point, end point)

There are a number of implementations of eye movement on the web, however a lot of them do not proportionally move the pupil away from the centre, this means the pupil in these animations are generally stuck at the edge of the eye. If you play with the application you will see that a proportional movement is more realistic - human brains are very good at calculating what other people are looking at based on the pupil positions.

Clipping can be seen in this picture:


The Xaml is as expected with the complication of grouping the parts of the eye together using a Canvas, with a Canvas.Clip to stop drawing outside of the eyeball:

<UserControl x:Class="Eyes.Page"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    >
    <Canvas x:Name="LayoutRoot" Background="White" MouseMove="LayoutRoot_MouseMove" Cursor="Arrow">
    <TextBlock Name="TextDebug" Canvas.Left="10" Canvas.Top="0" Width="1000" Height="100" />
    <CheckBox Name="ShowCalculation" Canvas.Left="0" Canvas.Top="0"
           Checked="CheckBox_Changed" Unchecked="CheckBox_Changed" Canvas.ZIndex="7"
           Cursor="Arrow"/>

    <Ellipse Canvas.Left="300" Canvas.Top="100" Width="230" Height="300" Stroke="Black" Name="Face" Fill="WhiteSmoke" Canvas.ZIndex="1"/>

    <Canvas Canvas.Left="340" Canvas.Top="200" Canvas.ZIndex="2" >
      <Ellipse Canvas.Left="0" Canvas.Top="0" Width="60" Height="40" Stroke="Black" Name="LeftEye" Fill="White" Canvas.ZIndex="2" />
      <Ellipse Canvas.Left="10" Canvas.Top="10" Width="20" Height="20" Fill="Green" Name="LeftPupil" Canvas.ZIndex="2" />
      <Canvas.Clip>
        <EllipseGeometry Center="30,20" RadiusX="30" RadiusY="20" />
      </Canvas.Clip>
    </Canvas>

    <Canvas Canvas.Left="420" Canvas.Top="200" Canvas.ZIndex="2" >
      <Ellipse Canvas.Left="0" Canvas.Top="0" Width="60" Height="40" Stroke="Black" Name="RightEye" Fill="White"  Canvas.ZIndex="2" />
      <Ellipse Canvas.Left="10" Canvas.Top="10" Width="20" Height="20" Fill="Green" Name="RightPupil" Canvas.ZIndex="2" />
      <Canvas.Clip>
        <EllipseGeometry Center="30,20" RadiusX="30" RadiusY="20" />
      </Canvas.Clip>
    </Canvas>

    <Ellipse Canvas.Left="395" Canvas.Top="270" Width="30" Height="40" Stroke="Black" Name="Nose" Fill="DarkGray" Canvas.ZIndex="1"/>

    <Ellipse Canvas.Left="380" Canvas.Top="320" Width="60" Height="30" Stroke="Black" Name="Mouth" Fill="DarkGray" Canvas.ZIndex="1"/>

    <Ellipse Canvas.Left="10" Canvas.Top="60" Width="10" Height="10" Fill="Red" Name="FocusPoint" Canvas.ZIndex="6" />
    <Line Stroke="Red" Name="LineSightLeft"  Canvas.ZIndex="5" StrokeDashArray="2 5" />
    <Line Stroke="Red" Name="LineSightRight"  Canvas.ZIndex="5" StrokeDashArray="2 5" />
  </Canvas>
</UserControl>

The code behind simply responds to the mouse moving, for each eye calculates the polar coordinates and then moves the eyeball proportionally towards the mouse:

public partial class Page : UserControl
{
 bool showCalcs;

 public Page()
 {
  InitializeComponent();

  // default to showing calculations
  ShowCalculation.IsChecked = this.showCalcs = true;
 }

 private void LayoutRoot_MouseMove(object sender, MouseEventArgs e)
 {
  // update UI based on cursor location
  Point cursorPoint = e.GetPosition(LayoutRoot);

  UpdateUI(cursorPoint);
 }

 private void UpdateUI(Point cursorPoint)
 {
  // calculate the location of the focus based using the center of the circle
  Point centerPoint = new Point(cursorPoint.X, cursorPoint.Y);

  if (this.showCalcs)
   FocusPoint.PointSet(new Point(cursorPoint.X - (FocusPoint.Width / 2), cursorPoint.Y - (FocusPoint.Height / 2)));

  // focus eyes on point
  FocusEye(centerPoint, LeftEye, LeftPupil, LineSightLeft);
  FocusEye(centerPoint, RightEye, RightPupil, LineSightRight);
 }

 private void FocusEye(Point pointFocus, Ellipse eye, Ellipse pupil, Line sight)
 {
  // the centre of the eye needs to be converted to a global coordinate
  // which it's parent has
  Point pointStart = new Point(eye.Parent.PointGet().X + (eye.Width / 2), eye.Parent.PointGet().Y + (eye.Height / 2));
  Point pointEnd = pointFocus;
  
  // cartesian to polar conversion
  double angle = Trigonometry.CalculateAngleInDegreesBetween(pointStart, pointEnd);
  double distance = Trigonometry.CalculateDistanceBetween(pointStart, pointEnd);

  if (this.showCalcs)
   TextDebug.Text = String.Format("  {2:N1}deg  {3:N1}    {0}    {1}", new object[] { pointStart, pointEnd, angle, distance });

  // maximum focal distance
  const double MAX_DISTANCE = 500d;

  // the eye will move away from the center
  // of the eye ball proportionally to its maxim view
  // reduced by π to keep some of it visible
  double pupilDistance = (eye.Width / Math.PI) * (distance / MAX_DISTANCE);

  // polar to cartesian conversion
  Point pointPupilOffset = Trigonometry.ConvertPolarToPoint(pupilDistance, angle);

  // adjust for centre of eyeball and pupil
  Point pupilLocation = new Point(
    (eye.Width / 2) + pointPupilOffset.X - (pupil.Width / 2),
    (eye.Height / 2) - pointPupilOffset.Y - (pupil.Height / 2));

  pupil.PointSet(pupilLocation);

  if (this.showCalcs)
  {
   sight.X1 = pointStart.X;
   sight.Y1 = pointStart.Y;
   sight.X2 = pointEnd.X;
   sight.Y2 = pointEnd.Y;
  }
 }

 private void CheckBox_Changed(object sender, RoutedEventArgs e)
 {
  // show calculations visually
  this.showCalcs = ShowCalculation.IsChecked ?? false;

  Visibility visibility = (this.showCalcs) ? Visibility.Visible : Visibility.Collapsed;

  FocusPoint.Visibility = visibility;
  LineSightLeft.Visibility = visibility;
  LineSightRight.Visibility = visibility;
  TextDebug.Visibility = visibility;

  if (this.showCalcs)
   LayoutRoot.Cursor = Cursors.None;
  else
   LayoutRoot.Cursor = Cursors.Arrow;
 }
}

The code uses some extension methods, as I started doing in my previous blog entry:

public static class XamlExtensions
{
 public static Point PointGet(this DependencyObject sobj)
 {
  Point point = new Point((double)sobj.GetValue(Canvas.LeftProperty), (double)sobj.GetValue(Canvas.TopProperty));

  return point;
 }

 public static void PointSet(this DependencyObject shape, Point newLocation)
 {
  shape.SetValue(Canvas.LeftProperty, newLocation.X);
  shape.SetValue(Canvas.TopProperty, newLocation.Y);
 }

 public static Point GetCenterPoint(this Shape shape)
 {
  Point location = shape.PointGet();

  Point centerPoint = new Point(location.X + (shape.Width / 2), location.Y + (shape.Height / 2));

  return centerPoint;
 }
}

and a helper class for doing the trig:

public class Trigonometry
{
 public static double DegreesToRadians(double angle)
 {
  return ((angle * Math.PI) / 180f);
 }

 public static double RadiansToDegrees(double angle)
 {
  return ((angle * 180) / Math.PI);
 }

 public static double CalculateAngleInDegreesBetween(Point pointStart, Point pointEnd)
 {
  // difference between points on Y-Axis
  // Silverlight Y axis needs to be inverted of cartesian coordinates
  double dy = -(pointEnd.Y - pointStart.Y);
  // difference between points on X-Axis
  double dx = (pointEnd.X - pointStart.X);

  // angle of the vector defined by dy, dx
  double angleRadians = Math.Atan2(dy, dx);

  // results in (-π,π], which needs mapping to [0,2π) by adding 2π to negative 
  if (angleRadians < 0)
   angleRadians += 2 * Math.PI;

  double angleDegrees = RadiansToDegrees(angleRadians);

  return angleDegrees;
 }

 public static double CalculateDistanceBetween(Point pointStart, Point pointEnd)
 {
  double dySquared = Math.Pow(pointEnd.Y - pointStart.Y, 2);
  double dxSquared = Math.Pow(pointEnd.X - pointStart.X, 2);

  double distance = Math.Sqrt(dySquared + dxSquared);

  return distance;
 }


 internal static Point ConvertPolarToPoint(double radius, double angleDegrees)
 {
  double angleRadians = DegreesToRadians(angleDegrees);
  
  double x = radius * Math.Cos(angleRadians);
  double y = radius * Math.Sin(angleRadians);

  return new Point(x, y);
 }
}

Moving shapes in Silverlight

Having written the same code too many times, I thought I better start making life more easy for myself. In Silverlight you often want to change the location of a shape (or more correctly a DependancyObject)

The code I kept writing was move the location of a shape, such as in drag-n-drop.

I've written this as an Extension method, giving:

public static class XamlExtensions
{
  public static void PointSet(this DependencyObject shape, Point newLocation)
  {
    shape.SetValue(Canvas.LeftProperty, newLocation.X);
    shape.SetValue(Canvas.TopProperty, newLocation.Y);
  }
}

which allows:

shape.PointSet(cursorPoint);

rather than

PointSet(shape, cursorPoint);

Simple Kinetics in silverlight

Simple kinetics (mechanical) in silverlight, some exploding balls:



XAML:

<UserControl x:Class="SimpleKinetics.Page"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Width="500" Height="350">
    <Grid x:Name="LayoutRoot" Background="White">
  <Canvas x:Name="Container">
   <Button x:Name="ButtonAdd" Canvas.Top="10" Canvas.Left="8" ClickMode="Release" Content="New balls" Click="ButtonAdd_Click" />
   <Rectangle x:Name="Controls" Canvas.Top="0" Canvas.Left="0" Width="75" Height="300">
   </Rectangle>
  </Canvas>
 </Grid>
</UserControl>

code behind:

public partial class Page : UserControl
{
  List<Vector> vectors = new List<Vector>();
  const int RADIUS = 5;
  Random rand = new Random();

  public Page()
  {
    InitializeComponent();

    DispatcherTimer timer = new DispatcherTimer();

    timer.Interval = new TimeSpan(0, 0, 0, 0, 30);

    timer.Tick += new EventHandler(OnTick);

    timer.Start();
  }

  private void OnTick(object sender, EventArgs e)
  {
    List<Vector> deads = new List<Vector>();
    foreach (Vector vector in vectors)
    {
      vector.Transition();
      if (vector.IsDead)
        deads.Add(vector);
    }

    deads.ForEach(dead =>
    {
      vectors.Remove(dead);
      Container.Children.Remove(dead.ellipse);
    });
  }

  private void ButtonAdd_Click(object sender, RoutedEventArgs e)
  {
    for (int explosions = 0; explosions < rand.Next(10)+1; explosions++)
      GenerateExplode();
  }

  private void GenerateExplode()
  {
    Point point = new Point(rand.Next((int)Width), rand.Next((int)Height));
    for (int i = 0; i < 100; i++)
    {
      Ellipse ellipse = new Ellipse();
      ellipse.Width = RADIUS;
      ellipse.Height = RADIUS;
      Vector vector = new Vector(rand.Next(360), (rand.Next(30) / 10D) + 0.5D, ellipse);
      vectors.Add(vector);

      // make it a random colour
      ellipse.Fill = new SolidColorBrush(
        Color.FromArgb(
          255,
          GetRandomColour(),
          GetRandomColour(),
          GetRandomColour()));

      // add it to the interface
      Container.Children.Add(ellipse);

      // put it in a random location
      vector.Point = point;
    }
  }

  private byte GetRandomColour()
  {
    return (byte)rand.Next(byte.MaxValue);
  }

  private Point Offset(Point inpoint, double offset)
  {
    Point point = new Point(inpoint.X + offset, inpoint.Y + offset);

    return point;
  }

  private static Point GetPoint(DependencyObject sobj)
  {
    Point point = new Point((double)sobj.GetValue(Canvas.LeftProperty), (double)sobj.GetValue(Canvas.TopProperty));

    return point;
  }
}

which depends on my Vector class:

internal class Vector
{
  public double direction;
  public double magnitude;
  public Ellipse ellipse;

  public Vector(double direction, double magnitude, Ellipse ellipse)
  {
    this.direction = direction;
    this.magnitude = magnitude;
    this.ellipse = ellipse;
  }

  public Point Point
  {
    get
    {
      Point point = new Point((double)ellipse.GetValue(Canvas.LeftProperty), (double)ellipse.GetValue(Canvas.TopProperty));

      return point;
    }
    set
    {
      ellipse.SetValue(Canvas.LeftProperty, value.X);
      ellipse.SetValue(Canvas.TopProperty, value.Y);
    }
  }

  internal void Transition()
  {
    Point newPoint = CalculateNextPosition();

    Point = newPoint;

    double fade = ((magnitude * magnitude) / magnitude) / 800d;
    ellipse.Fill.Opacity -= fade;
  }

  public bool IsDead
  {
    get
    {
      return !(ellipse.Fill.Opacity > 0);
    }
  }

  private double DegreesToRadians(double angle)
  {
    return ((angle*Math.PI) / 180f);
  }

  private double RadiansToDegrees(double angle)
  {
    return ((angle*180) / Math.PI);
  }

  private Point CalculateNextPosition()
  {
    double vx = magnitude * Math.Cos(DegreesToRadians(direction));
    double vy = magnitude * Math.Sin(DegreesToRadians(direction));

    Point current = this.Point;
    double x = current.X + vx;
    double y = current.Y + vy;

    CheckCollision(vx, vy, x, y);
   
    Point newPoint = new Point(x, y);

    return newPoint;
  }

  private void CheckCollision(double vx, double vy, double x, double y)
  {
    const int maxX = 500;
    const int maxY = 500;

    if (x < 0  x > maxX)
      vx *= -1;
    if (y < 0  y > maxY)
      vy *= -1;

    magnitude = Math.Sqrt((vx * vx) + (vy * vy));
    direction = RadiansToDegrees(Math.Atan2(vy, vx));
  }
}

Alliteration algorithm

A function to determine is a string is an alliteration, for example
" as albert asked Anna, an antelope appeared!" is considered to be one.

private static bool IsAnAlliteration(string subject)
{
  bool result = true;

  char lead = default(char);

  bool inWord = false;

  foreach (char c in subject)
  {
    char current = char.ToLower(c);

    bool isLetter = char.IsLetter(current);
    // lead contains first character in string
    // all words should start with lead character
    if (lead == default(char) && isLetter)
      lead = current;

    if (!inWord && isLetter && lead != current)
      result = false; // start of new word, but does not start with lead char
    else if (!inWord && isLetter && lead == current)
      inWord = true; // start of new word starts with lead char
    else if (inWord && char.IsWhiteSpace(current))
      inWord = false; // end of word found

    if (!result)
      break;
  }
  // did we find at least one word
  result &= (lead != default(char));

  return result;
}

Permutations and Anagrams

I needed to generate some anagrams, which I know falls into the area Permutations (combinations being altogether the wrong thing for this). There is a nice code sample on Wikipedia that shows how to generate these for an unordered collection.

I implemented a generic class to carry out permutations for me, I changed it to be based on an iterator pattern as often you don't want to generate the whole set, mainly because of the big-oh O(n!), class is therefore:

class Permutation<T>
{
  IEnumerable<T> set;

  private Permutation()
  {
  }

  public Permutation(IEnumerable<T> set)
  {
    this.set = set;
  }

  public IEnumerable<IEnumerable<T>> Mutations
  {
    get
    {
      int length = set.Count();

      int factorialK = (int)Factorial(length);

      for (int k = 0; k < factorialK; k++)
        yield return GeneratePermutation(k, set, length);

    }
  }

  private static IEnumerable<T> GeneratePermutation(long k, IEnumerable<T> set, int length)
  {
    T[] result = set.ToArray();
    for (int j = 2; j <= length; j++)
    {
      k = k / (j - 1);
      int dest = (int)(k % j);
      int source = j - 1;
      if (source != dest)
        Swap(ref result[dest], ref result[source]);
    }

    return result;
  }

  private static void Swap(ref T a, ref T b)
  {
    T temp = a;
    a = b;
    b = temp;
  }

  private static long Factorial(int n)
  {
    long result = 1L;

    for (int integer = 2; integer <= n; integer++)
      result *= integer;

    return result;
  }
}

which allowed me to write the following code to generate ananagrams:

static void Main(string[] args)
{
  string word = "ape";

  List<string> anagrams = GenerateAnagrams(word);

  anagrams.Sort();

  Console.WriteLine("{0} anagrams", anagrams.Count);
  anagrams.ForEach(anagram => Console.WriteLine(anagram));
}

private static List<string> GenerateAnagrams(string word)
{
  List<string> sets = new List<string>();

  Permutation<char> perm = new Permutation<char>(word);
  foreach (char[] combo in perm.Mutations)
    sets.Add(combo.ToString());

  return sets;
}

note that we are taking advantage of string being a char[], for other types such as int would need to be passed as an array, list or similar IEnumerable<T>

Finding duplicates in an array

One of the problems I stumbled across recently was writing an efficient way to detect if a non-sorted integer array contains duplicates. Or more formally: an unsorted array of size N that contains values between 0 and N-1, find if it contains duplicated elements.

The trick being to avoid having to sort the array, or O(N²) loop within loops.

My solution was to use a bit array the size of N, which would flag if we had seen a value or not - we run through all the values in the array and check its position in the bit array, if it contains a 0 we have not seen it before, or a 1 if we have (duplicate). If we have not seen it before we set its position to 1 and continue.

In C# the is a great class that makes bit manipulation even easier "BitArray", it provides an efficient array class for handling bit operation.

The code:

static void Main(string[] args)
{
  int[] numbers = { 1, 2, 3, 1, 5 };

  bool duplicates = IsArrayDuplicated(numbers);
}

private static bool IsArrayDuplicated(int[] numbers)
{
  bool result = false;

  BitArray bits = new BitArray(numbers.Length+1);

  foreach (int n in numbers)
  {
    result = !bits[n];

    if (!result)
      break;

    bits[n] = true;
  }

  return result;
}

Rotating an array

Over at polymathprogrammer there is an article about rotating an array, which was a response to Mr Chen's entry on an interview question

Reading the answers got me thinking as I had recently written a roate method in order in implement tic-tac-toe (don't ask why). My solution then had been along the lines of one of the suggested solutions:

for (int y = 0; y < n; y++)
  for (int x = 0; x < n; x++)
    output[n - y - 1,x] = input[x,y];

though I used a mapping intead of a direct move.

What was interesting was that someone else had suggested that you could just do it using two mirror operations (mirror horizontal and then a diagonal) which was a very elegant way of doing it.

I liked this and it made me think was there another way to do it (as in how many ways can this problem be solved. And I came up with this, which takes advantage of using a single dimension array for holding two dimensional data:

1 &124; 2 &124; 3
-----------
4 &124; 5 &124; 6
-----------
7 &124; 8 &124; 9

stored as

int[] array = new int[] { 1, 2, 3, 4 , 5, 6, 7, 8, 9};

which if rotated looks likes:

int[] array = new int[] { 7, 4, 1, 8, 5, 2, 9, 6, 3};

which looks like the mapping:

destinationOffset += w;
if (destinationOffset > l)
  destinationOffset = destinationOffset % w;

in effect, offset its new position by the width of the matrix (3) and wrap overflows back to the start. This looked good until number 4 as it collided with 1, so I just moved it back a step if it collided. Problem solved for 90° right:

gives:

7 &124; 4 &124; 1
-----------
8 &124; 5 &124; 2
-----------
9 &124; 6 &124; 3

Now you could just apply the function multiple times for 180°, 270° rotations, but looking at the resultant arrays shows two things:
180°: results is the original array in reverse order
270°: results is the 90° array in reverse order

So it looks like reversing an array is the same as a diagonal mirror! which means you need just two functions, a rotate and an array reverse (which is part of most array implementations, .Net as Arrray.Reverse)

Code for just the single rotation is:

int size = 3*3;
int[] array = new int[size];
for (int i = 0; i < size; i++)
 array[i] = i + 1;

int l = array.Length;
int w = (int)Math.Sqrt(array.Length);

int[] destination = Rotate(array, l, w);


private static int[] Rotate(int[] array, int l, int w)
{
  int[] destination = new int[l];
  int destinationOffset = -1;
  for (int sourceOffset = 0; sourceOffset < l; sourceOffset++)
  {
    destinationOffset += w;

    // wrap around
    if (destinationOffset > l)
    {
      destinationOffset %= w;
      // collision avoidance
      destinationOffset--;
    }

    destination[destinationOffset] = array[sourceOffset];

  }

  return destination;
}

and of course given we know the size of the array, and we can use XOR to do swaps in place

swap(a, b) =>
  a = a ^ b; // a^= b;
  b = b ^ a; // b ^= a;
  a = a ^ b; // a ^= b;

then the fast version (without working at a bit level) might be:

private static void RotateInPlace4by4(int[] array)
{
  // corners (1,4 moves around)
  swap(ref array[3], ref array[15]);
  swap(ref array[0], ref array[3]);
  swap(ref array[0], ref array[12]);

  // left inner (2 moves around)
  swap(ref array[7], ref array[14]);
  swap(ref array[1], ref array[7]);
  swap(ref array[1], ref array[8]);

  // right inner (3 moves around)
  swap(ref array[11], ref array[13]);
  swap(ref array[2], ref array[11]);
  swap(ref array[2], ref array[4]);

  // middle square (6,7,10,11)
  swap(ref array[5], ref array[9]);
  swap(ref array[6], ref array[10]);
  swap(ref array[6], ref array[9]);
}

private static void swap(ref int a, ref int b)
{
  a ^= b;
  b ^= a;
  a ^= b;
}

Lambda expressions with multiple parameters

After writing the calling code for the heap I realised that I could have used a Lambda Expression:

var heap3 = new Heap<char>(first, second => second.CompareTo(first));

but that does not work as it the compiler complains about "The name 'first' does not exist in the current context". The solution to this is to wrap it with brackets:

var heap3 = new Heap<char>((first, second) => second.CompareTo(first));
foreach (char c in data)
  heap3.Push(c);
while (heap3.Count != 0)
  Console.WriteLine(heap3.Pop());

Generic Heap and prioritized queues in C#

One of the systems I'm writing required a heap data structure so I've implemented it as a generic as its quite useful for guaranteed sort times and for prioritized queues.

which can be used:

string data = "an out of order string";


var heap = new Heap<char>();
foreach (char c in data)
  heap.Push(c);

// in order becomes
while (heap.Count != 0)
  Console.WriteLine(heap.Pop());

// or in reverse order, using a custom order

Comparison<char> comparison = delegate(char first, char second)
{
  return second.CompareTo(first);
};

var heap2 = new Heap<char>(comparison);
foreach (char c in data)
  heap2.Push(c);
while (heap2.Count != 0)
  Console.WriteLine(heap2.Pop());

implemented as:

using System;
using System.Collections.Generic;
using System.Text;

namespace Heaps
{

/// <summary>
/// heap data stucture, guaranteed O(nlog n), acts as a priority queue
/// </summary>
/// <typeparam name="T">data to hold in heap tree</typeparam>
class Heap<TValue> where TValue : IComparable
{
  // functions return if item not found
  public const int NOTFOUND = -1;
  // root offset
  const int ROOT = 0;
  // forward, backward step direction
  const int FORWARD = 1;
  const int BACKWARD = -FORWARD;
  // storage of values
  List<TValue> values = null;
  // allow parameterisation of ordering and (min/max heap)
  Comparison<TValue> comparison = null;

  /// <summary>
  /// creates a new heap, with ordering
  /// defined by T : IComparable
  /// </summary>
  public Heap()
  {
    values = new List<TValue>();
  }

  /// <summary>
  /// creates a new heap, with ordering
  /// defined by Comparison<T>
  /// </summary>
  /// <param name="comparison"></param>
  public Heap(Comparison<TValue> comparison): this()
  {
    this.comparison = comparison;
  }

  /// <summary>
  /// return the value at offset position in the tree (pre-order traversal)
  /// </summary>
  /// <param name="position">offset in tree</param>
  /// <returns></returns>
  public TValue this[int position]
  {
    get
    {
      return values[position];
    }
  }

  /// <summary>
  /// number of values in tree
  /// </summary>
  public int Count
  {
    get
    {
      return Length();
    }
  }

  /// <summary>
  /// returns the offset of the parent
  /// </summary>
  /// <param name="position">the value position to find parent of</param>
  /// <returns>offset of parent in tree</returns>
  public int ParentOf(int position)
  {
    int result = NOTFOUND;
    if (position > 0)
      result = ((position+1) / 2) - 1;

    return result;
  }

  /// <summary>
  /// return the offset of the left child
  /// </summary>
  /// <param name="position">the value offset position to find the left child of</param>
  /// <returns>offset of left child in tree</returns>
  public int Left(int position)
  {
    int result = NOTFOUND;

    result = (position * 2) + 1;

    result = EnsureNotBeyond(result);

    return result;
  }

  /// <summary>
  /// return the offset of the right child
  /// </summary>
  /// <param name="position">the value offset position to find the right child of</param>
  /// <returns>offset of right child in tree</returns>
  public int Right(int position)
  {
    // right node is 1 more than the left
    int result = Left(position);

    if (result != NOTFOUND)
      result++; // one position beyond left

    result = EnsureNotBeyond(result);

    return result;
  }

  /// <summary>
  /// returns the root value
  /// </summary>
  public TValue Root
  {
    get
    {
      if (Length() == 0)
        throw new InvalidOperationException("No items in heap");

      return values[ROOT];
    }
  }

  /// <summary>
  /// returns the value with highest priority
  /// </summary>
  /// <returns>the value</returns>
  public TValue Pop()
  {
    TValue result = Root;

    int lastItem = EnsureNotBeyond(Length() - 1);

    if (Length() > 1)
      values[ROOT] = values[lastItem];

    values.RemoveAt(lastItem);

    MaintainHeapProperty(FORWARD);

    return result;
  }

  /// <summary>
  /// add the value to the tree
  /// </summary>
  /// <param name="value">value to add</param>
  public void Push(TValue value)
  {
    values.Add(value);

    MaintainHeapProperty(BACKWARD);
  }

  /// <summary>
  /// number of nodes
  /// </summary>
  /// <returns>length</returns>
  private int Length()
  {
    return values.Count;
  }

  /// <summary>
  /// ensures a  position is not beyond the tree storage
  /// </summary>
  /// <param name="position">offset</param>
  /// <returns>offset, or NOTFOUND if out of bounds</returns>
  private int EnsureNotBeyond(int position)
  {
    if (position >= Length())
      position = NOTFOUND;

    return position;
  }

  /// <summary>
  /// adjusts tree to ensure heap property maintained after a push or pop
  /// </summary>
  /// <param name="direction">FORWARD for push, BACKWARD if pop</param>
  private void MaintainHeapProperty(int direction)
  {
    int start = (direction == FORWARD) ? ROOT : Length();
    int end = (direction == FORWARD) ? Length() : NOTFOUND;

    for (int pos = start; pos != end; pos += direction)
    {
      int left = Left(pos);
      int right = Right(pos);

      // ensure this value is greater than chidren
      if (left != NOTFOUND && Compare(pos, left) < 0)
        Swap(pos, left);
      if (right != NOTFOUND && Compare(pos, right) < 0)
        Swap(pos, right);
    }
  }

  /// <summary>
  /// return integer indicating order
  /// </summary>
  /// <param name="first">offset of first</param>
  /// <param name="second">offset of second</param>
  /// <returns>.lt. zero=first,second;zero=first==second;.gt. zero=second,first</returns>
  private int Compare(int first, int second)
  {
    int result = 0;

    // if comparison delegate provided us it to compare
    if (comparison != null)
      result = comparison(values[first], values[second]);
    else // default TValue compare
      result = values[first].CompareTo(values[second]);

    return result;
  }

  /// <summary>
  /// swaps two offsets
  /// </summary>
  /// <param name="first">first offset</param>
  /// <param name="second">second offset</param>
  private void Swap(int first, int second)
  {
    TValue temp = values[first];
    values[first] = values[second];
    values[second] = temp;
  }

  public override string ToString()
  {
    StringBuilder sb = new StringBuilder();

    sb.Append("[");
    foreach (TValue value in values)
      sb.Append(value.ToString());
    sb.Append("]");

    return sb.ToString();
  }
}

}

You say NURB I say Poly Quadratic Bezier curves

A small step forward from the last post, to using multi control segment lines.

Looking at PolyQuadraticBezierSegment you might think it allows multiple control points - unfortunately it should really be called QuadraticBezierPolySegments, its a collection of segments with their own distinct control points rather a one segment with multiple control points.

Having said that it still allows you to create:

(use the "+" key to add new segments)

The XAML is very similar, though I have removed the points as they are created dynamically by the C# code now:

<UserControl x:Class="DragDropMulti.Page"
    xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
    xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
    Width="400" Height="300">
    <Grid x:Name="LayoutRoot" Background="White">
  <Canvas x:Name="Container">
   <Path StrokeThickness="1" Canvas.ZIndex="-1">
    <Path.Stroke>
     <LinearGradientBrush SpreadMethod="Pad">
      <GradientStop Color="DarkGreen" Offset="0"/>
      <GradientStop Color="Black" Offset="0.5"/>
      <GradientStop Color="DarkRed" Offset="1"/>
     </LinearGradientBrush>
    </Path.Stroke>
    <Path.Data>
     <PathGeometry>
      <PathFigure x:Name="Path" StartPoint="100,10">
       <PolyQuadraticBezierSegment x:Name="Segment" Points="200,200,300,10" />
      </PathFigure>
     </PathGeometry>
    </Path.Data>
   </Path>
  </Canvas>
 </Grid>
</UserControl>

The class variables have changed to manage a dynamic list of control pointss, and a random generator:

public Page()
{
 InitializeComponent();

 // create first point for start point
 CreateNewPoint();
 // create two control points
 CreateControlPointSet();

 this.KeyUp += new KeyEventHandler(Page_KeyUp);
 // make sure the bezier reflects our gui control points
 UpdateBezier();
}

private void CreateControlPointSet()
{
 CreateNewPoint();
 CreateNewPoint();
}

private void CreateNewPoint()
{
 // create a new circle
 Ellipse ellipse = new Ellipse();
 ellipse.Width = RADIUS * 2;
 ellipse.Height = RADIUS * 2;

 // make it a random colour
 ellipse.Fill = new SolidColorBrush(
  Color.FromArgb(
   255,
   GetRandomColour(),
   GetRandomColour(),
   GetRandomColour()));

 // add it to the interface
 Container.Children.Add(ellipse);

 // put it in a random location
 MoveShape(ellipse, new Point(rand.Next((int)Width), rand.Next((int)Height)));

 // keep a track of them for control points
 ellipses.Add(ellipse);

 // let the user move it, and indicate they can
 AttachEventHandlers(ellipse);
 ellipse.Cursor = Cursors.Hand;
}

private byte GetRandomColour()
{
 return (byte)rand.Next(byte.MaxValue);
}

void Page_KeyUp(object sender, KeyEventArgs e)
{
 if (e.Key == Key.Add)
 {
  CreateControlPointSet();
  UpdateBezier();
 }
}

private void AttachEventHandlers(Ellipse point)
{
 point.MouseLeftButtonDown += new MouseButtonEventHandler(Point_MouseLeftButtonDown);
 point.MouseLeftButtonUp += new MouseButtonEventHandler(Point_MouseLeftButtonUp);
 point.MouseMove += new MouseEventHandler(Point_MouseMove);
}

private void UpdateBezier()
{
 this.Path.StartPoint = Offset(GetPoint(ellipses[0]), RADIUS);
 PointCollection points = new PointCollection();

 this.Segment.Points.Clear();
 ellipses.ForEach(ellipse =>
 {
  // not start point (already set as path StartPoint)
  if (ellipse != ellipses[0])
   points.Add(Offset(GetPoint(ellipse), RADIUS));
 });

 // just changing the points in the collection does not work (clear, add)
 // appears to be a bug, so we just replace the whole collection of points
 this.Segment.Points = points;

}

The rest of the code is the same as before for the utility and event handlers. Note the last comment about a bug (by design?) which means making changes to the points collection in place has no effect. I'm thinking bug rather than feature...

Silverlight and bezier curves

Starting to learn Silverlight, so I implemented a simple interface to allow the control points for a Quadratic bezier segment to be controlled via drag-and-drop.


(note it works in Googles chrome, just does not redraw properly)

<UserControl x:Class="DragDrop.Page"
 xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
 xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
 Width="400" Height="300">
 <Grid x:Name="LayoutRoot" Background="White">
  <Canvas>
   <Ellipse x:Name="PointStart" Canvas.Left="100" Canvas.Top="10" Width="20" Height="20" Fill="DarkGreen" Cursor="Hand"/>
   <Ellipse x:Name="PointMiddle" Canvas.Left="200" Canvas.Top="100" Width="20" Height="20" Fill="Black" Cursor="Hand"/>
   <Ellipse x:Name="PointEnd" Canvas.Left="300" Canvas.Top="10" Width="20" Height="20" Fill="DarkRed" Cursor="Hand"/>

   <Path StrokeThickness="10" Canvas.ZIndex="-1" StrokeDashArray="1,1">
    <Path.Stroke>
     <LinearGradientBrush SpreadMethod="Pad">
      <GradientStop Color="DarkGreen" Offset="0"/>
      <GradientStop Color="Black" Offset="0.5"/>
      <GradientStop Color="DarkRed" Offset="1"/>
     </LinearGradientBrush>
    </Path.Stroke>
    <Path.Data>
     <PathGeometry>
      <PathFigure x:Name="Path" StartPoint="100,10">
       <QuadraticBezierSegment x:Name="Segment" Point1="200,100" Point2="300,10" />
      </PathFigure>
     </PathGeometry>
    </Path.Data>
   </Path>
  </Canvas>
 </Grid>
</UserControl>

with C# behind:

namespace DragDrop
{
  public partial class Page : UserControl
  {
    bool isDragging = false;

    public Page()
    {
      InitializeComponent();

      AttachEventHandlers(PointStart);
      AttachEventHandlers(PointMiddle);
      AttachEventHandlers(PointEnd);

      // make sure the bezier reflects our gui control points
      UpdateBezier();
    }

    private void AttachEventHandlers(Ellipse point)
    {
      point.MouseLeftButtonDown += new MouseButtonEventHandler(Point_MouseLeftButtonDown);
      point.MouseLeftButtonUp += new MouseButtonEventHandler(Point_MouseLeftButtonUp);
      point.MouseMove += new MouseEventHandler(Point_MouseMove);
    }

    private void UpdateBezier()
    {
      double radius = this.PointStart.Width / 2;

      Path.StartPoint = Offset(GetPoint(PointStart), radius);
      Segment.Point1 = Offset(GetPoint(PointMiddle), radius);
      Segment.Point2 = Offset(GetPoint(PointEnd), radius);
    }

    private Point Offset(Point inpoint, double offset)
    {
      Point point = new Point(inpoint.X + offset, inpoint.Y + offset);

      return point;
    }

    private static Point GetPoint(DependencyObject sobj)
    {
      Point point = new Point((double)sobj.GetValue(Canvas.LeftProperty), (double)sobj.GetValue(Canvas.TopProperty));

      return point;
    }

    void Point_MouseMove(object sender, MouseEventArgs e)
    {
      if (!isDragging)
        return;

      Ellipse point = sender as Ellipse;
      Point newLocation = e.GetPosition(this);

      MoveShape(point, newLocation);

      UpdateBezier();
    }

    private static void MoveShape(DependencyObject shape, Point newLocation)
    {
      shape.SetValue(Canvas.LeftProperty, newLocation.X);
      shape.SetValue(Canvas.TopProperty, newLocation.Y);
    }

    void Point_MouseLeftButtonUp(object sender, MouseButtonEventArgs e)
    {
      if (!isDragging)
        return;

      isDragging = false;
      Ellipse point = sender as Ellipse;
      point.ReleaseMouseCapture();
    }

    void Point_MouseLeftButtonDown(object sender, MouseButtonEventArgs e)
    {
      Ellipse point = sender as Ellipse;
      isDragging = true;
      point.CaptureMouse();
    }
  }
}