Home » Posts tagged 'Algorithms'

Tag Archives: Algorithms

Implementing a moving average

18th June 2019 / 2 Comments on Implementing a moving average

Known by many names, such as as Cumulative Moving Average, Rolling Average, Running Average, Moving Mean or Rolling Mean, the object is to update an average value on receipt of a new value over a set window size.

Example:

Imagine we have accumulated 10 values and our window size is 10.
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
The average of this sequence is (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) / 10 = 5.5

We now add a new sample, 11 to the sequence. As the windows size is 10, we drop the first value.

[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
The average of this sequence is (2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) / 10 = 6.5

Now, averaging over 10 samples each time is not that big an issue, but what if it’s 1000 or 10,000? Then, the overhead, both in processing time and storage has statrted to become a little excessive. In the case of 10,000 samples  of ‘double’ we are looking at 10,000 additions + 1 division each time a sample is added and a likely storage requirement of 80,000 bytes!
So we have an algorithm that has processing and storage complexity of O(N).

So let’s look at the problem again.
There are many ways of getting the same average:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] = Average of 5.5
[ 7, 7, 7, 7, 7, 4, 4, 4, 4, 4 ] = Average of 5.5

But what about this?
[ 5.5, 5.5 , 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5 ] = Average of 5.5

An average of 5.5 can be got from 10 samples of 5.5. So why store 10 samples? We can simply simulate the original sum just by multiplying the current average by the number of samples!

The calculation of the average for adding a new sample becomes this:

((Old_Average * Sample_Size) + New_Sample) / (Sample_Size + 1)

Now we have 1 multiplication, 2 additions and 1 division.

Our algorithm now has a complexity of O(1).

We can average over as large a sample size as we like and it will always take the same amount of time and use the same amount of storage. We can also change the sample size on-the-fly if we wish.

There is one downside in that the average will not exactly match the original version, as the actual oldest value is not being erased from the sum. But for the performance and storage advantages it may be a perfectly suitable solution. You may find that you will need a slightly smaller sample size with the rolling mean to get similar results.

UPDATE:
The multiplication may be elided by re-arranging the formula.

Old_Average + ((New_Sample – Old_Average) / (Sample_Size + 1))

This may produce a negative interim value, which may be a problem if you are using scaled unsigned integral types for the average value.

Designing an efficient and low resource messaging framework. Part 3

12th November 2017 / Leave a comment

In the last post I showed how to shrink the vtable overhead and reduce the coupling of the framework.
This time I shall show how to reduce the vtable hit even further using another technique called the Curiously Recurring Template Pattern or CRTP. This oddly name pattern is a way of replacing runtime virtual calls with compile time dispatch. It achieves this by passing the derived class type as a template type parameter to the base class.

template <typename TDerived>
class Base
{
};

class Derived : public Base<Derived>
{
};

By the use of this technique, the base class can be informed of its concrete type at compile time. This allows the base type to directly call member functions in the derived type thereby avoiding an indirect call though the vtable. If the called functions are deemed suitable by the compiler, then they may well be inlined too.

template <typename TDerived>
class Base
{
  void FunctionBase()
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    derived.FunctionDerived()
  }
};

class Derived : public Base<Derived>
{
  void FunctionDerived()
  {
  }
};

This is the technique that we will use for the third version of the messaging framework.
The messages are defined in the same way as before.

class IMessage
{
public:

  IMessage(int id)
    : messageId(id)
  {
  }

  int GetMessageId() const
  {
    return messageId;
  }

private:

  const int messageId;
};

template <int ID_>
class Message : public IMessage
{
public:

  Message()
    : IMessage(ID_)
  {
  }

  enum
  {
    ID = ID_
  };
};

// Message 1.
class Message1 : public Message<1>
{
};

// Message 2.
class Message2 : public Message<2>
{
};

// Message 3.
class Message3 : public Message<3>
{
};

// Message 4.
class Message4 : public Message<4>
{
};

As is the base message processor interface.

class IMessageProcessor
{
public:

  virtual void Receive(const IMessage& msg) = 0;
};

The difference now is in the definitions of the templated message handlers. The derived message processor type is passed as a template type parameter and used to cast the ‘this’ pointer to the true concrete type, allowing direct calls to the handler functions.

template <typename TDerived, typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class MessageProcessor : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
      case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
      case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
      case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
      case T4::ID: derived.Handle(static_cast<const T4&>(msg)); break;
      default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2, typename T3>
class MessageProcessor<TDerived, T1, T2, T3, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2>
class MessageProcessor<TDerived, T1, T2, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

The derived message processors are very similar to before, with the exception that the derived class is passed as template type parameter to the base.

class Processor1 : public MessageProcessor<Processor1, Message4, Message2, Message1, Message3>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

class Processor2 : public MessageProcessor<Processor2, Message3, Message1>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

We now have a message framework where the processor classes contain just one virtual function and where calls to the handler functions are direct.

The tests are defined exactly as in every previous version of the framework, as is the output.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

Chain Of Responsibility

If the ability to set a successor message processor is added to IMessageProcessor, the framework is then able to implement the Chain Of Responsibility design pattern.


// IMessageProcessor base class
IMessageProcessor* pSuccessor;

void SetSuccessor(IMessageProcessor& successor)
{
  pSuccessor = &successor;
}

// Derived message processor class
template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default:
	{
	  if (pSuccessor)
	  {
	    pSuccessor->Receive(msg);
      }
	  else
	  {
	    derived.Unhandled(msg); break;
	  }
    }
  }
};

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Download the example code

Designing an efficient and low resource messaging framework. Part 2

11th November 2017 / Leave a comment

In the last part I showed a pure C++ scheme for creating a simple message processing framework using ‘double dispatch’ or the Visitor Pattern.

In this part I’m going to show you how we can mitigate some of the issues that were raised by using templates and template specialisation. We will be moving away from a pure C++ solution and partly using an old style C idiom.

This issue we are going to address is the requirement for the message processor interface to not only have to know about all of the messages in existence, but also the fact that the interface will have to be modified each a new one is added.

There is an old C technique for implementing a type of polymorphism. It requires that the ‘base’ type contains an id that specifies what concrete type it actually is. We are going to use this technique (C++ purists will be choking on their breakfast about now).

Like before, there is a base message type.

class IMessage
{
public:

  IMessage(int id)
    : messageId(id)
  {
  }

  int GetMessageId() const
  {
    return messageId;
  }

private:

  const int messageId;
};

Unlike before, there is also an intermediate template type.

template <int ID_>
class Message : public IMessage
{
public:

  Message()
    : IMessage(ID_)
  {
  }

  enum
  {
    ID = ID_
  };
};

Now let’s define the four message types again. You will notice that each message has a unique id.
I’ve used hard coded numbers here, but you would probably use named constants or enums in production code.

// Message 1.
class Message1 : public Message<1>
{
};

// Message 2.
class Message2 : public Message<2>
{
};

// Message 3.
class Message3 : public Message<3>
{
};

// Message 4.
class Message4 : public Message<4>
{
};
Messages

The message processor interface is similar to the previous framework except this time Receive is now pure virtual.

class IMessageProcessor
{
public:

  virtual void Receive(const IMessage& msg) = 0;

protected:

  virtual void Unhandled(const IMessage& msg) = 0;
};

There are now intermediate message processor templates. There is one master template and N specialisations. The value of N depends on the maximum number of messages that a particular processor will be expected to handle. This may seem like a bit of a downside, but the repetitive nature of the code lends itself to automatic code generation from a script.

The master message processor template is defined for the maximum number of messages that a processor may handle. C++ purists who have just recovered from their initial chocking episode may succumb to another when they see the static casts, but they are safe as the lines in question will tend to be written and tested at the creation of the framework. Once proven correct they will be so for all instances. The margin for error will be even less if the code generation is scripted.

// Handle the maximum number of messages
template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class MessageProcessor : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
      case T1::ID: Handle(static_cast<const T1&>(msg)); break;
      case T2::ID: Handle(static_cast<const T2&>(msg)); break;
      case T3::ID: Handle(static_cast<const T3&>(msg)); break;
      case T4::ID: Handle(static_cast<const T4&>(msg)); break;
      default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
  virtual void Handle(const T3& msg) = 0;
  virtual void Handle(const T4& msg) = 0;
};

The specialisations are defined for all of the other instances.

// Three messages
template <typename T1, typename T2, typename T3>
class MessageProcessor<T1, T2, T3, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: Handle(static_cast<const T2&>(msg)); break;
    case T3::ID: Handle(static_cast<const T3&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
  virtual void Handle(const T3& msg) = 0;
};

// Two messages
template <typename T1, typename T2>
class MessageProcessor<T1, T2, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: Handle(static_cast<const T2&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
  virtual void Handle(const T2& msg) = 0;
};

// One message
template <typename T1>
class MessageProcessor<T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    switch (msg.GetMessageId())
    {
    case T1::ID: Handle(static_cast<const T1&>(msg)); break;
    default: Unhandled(msg); break;
    }
  }

protected:

  virtual void Handle(const T1& msg) = 0;
};

Now all a concrete message processor has to do is to specify which messages it would like to handle. This has the advantage in that if a message is specified in the template parameter list, but a handler is not implemented, then a compiler error will result.

Processor1 is configured to handle Message1, Message2, Message3 and Message4. Note that the order of the message types is not important.

class Processor1 : public MessageProcessor<Message4, Message2, Message1, Message3>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

Processor2 will handle Message1 and Message3.

class Processor2 : public MessageProcessor<Message3, Message1>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

Although it may look as though we have considerably increased the amount of code we have to write there are a number important things to note.
The first is that each concrete message processor’s vtable will only be as large as it needs to be. It is not dependent on the total number of messages in the system; only on the number of messages that it must handle.
The second is that the introduction of a new message will not require any of the processor interfaces to be modified.
Another is that the templates do not have to be rewritten every time a message processor framework is required. The base classes and templates may be part of a shared source code library.
One other advantage is that the messages do not have to be able to access any members of the processor interface meaning that the handlers may now be ‘protected’.

The framework is used in exactly the same way as before.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

The output of the example is also the same as before.

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

In the next post I will show how to improve efficiency a little more by eliminating most of the virtual functions.

Download the example code

Designing an efficient and low resource messaging framework. Part 1

11th November 2017 / Leave a comment

I am going to show you three ways in which a messaging framework might be implemented; the first is the ‘proper’ idiomatic C++ way; in the second and third parts, a more efficient blending of C & C++ styles (but may make C++ purists choke on their breakfast).

The specification

  1. There are a set of N messages that can be passed around the application.
  2. The messages are all derived from a base message class.
  3. Objects in the application must be able to receive and process messages.
  4. Objects receiving messages are derived from a base message processor class.
  5. Message processors receive messages as references to the base message class.
  6. They will not all processes the same number or combination of messages.

Let’s start off with the pure object orientated C++ version.

It is usually deemed a ‘code smell’ in C++ programming if code has to interrogate a base object to determine its concrete derived type. As messages are passed to message processors as references to the base message type, some way must be created to steer the message to the correct handler. One way of doing this is to use ‘double dispatch’ or the Visitor Pattern.

Is you are not familiar with this pattern, then hopefully this metaphor will give you the basic idea.

Imagine a salesman visits a company. He meets management, sales, marketing and engineering. He gives out business cards to each person he meets. There is a different telephone help line for each type of recipient, one for management, one for sales etc. Now, he could have a different card for each type of recipient, which would require him to know the job title of each person he meets. He would have to ask them what they did and choose the correct card for each one.

Alternatively, he could have one card with all of the telephone numbers on it and tell each recipient to “call the help line appropriate to your job title”.

This is effectively what the visitor pattern achieves. It says to the message “Here is an interface of overloaded functions that can accept all of the messages. Call the one that matches your concrete type”.

An interface is created that defines a virtual handler function for every message. The handlers in the interface may have default bodies, maybe logging an unhandled message. The concrete message processor inherits from this and implements each of the message handlers it is interested in. When a reference to a base message object is received it will pass itself to the message and the message will call the correct handler in the message processor.
Neat!

Let’s show a little bit of code as an example.

The code below defines a visitor interface that defines virtual handlers for four message types. The virtual handlers have default bodies that send control to an ‘Unhandled’ member (pure virtual). Two message processors are defined, one handling all of the messages, the other just Message1 and Message3.

class IMessageProcessor;

struct IMessage
{
  virtual void Accept(IMessageProcessor& processor) const = 0;
};

struct Message1 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message2 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message3 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

struct Message4 : public IMessage
{
  void Accept(IMessageProcessor& processor) const;
};

class IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    msg.Accept(*this);
  }

  virtual void Handle(const Message1& msg) { Unhandled(msg); }
  virtual void Handle(const Message2& msg) { Unhandled(msg); }
  virtual void Handle(const Message3& msg) { Unhandled(msg); }
  virtual void Handle(const Message4& msg) { Unhandled(msg); }

  virtual void Unhandled(const IMessage& msg) = 0;
};

void Message1::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message2::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message3::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

void Message4::Accept(IMessageProcessor& processor) const
{
  processor.Handle(*this);
}

class Processor1 : public IMessageProcessor
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

class Processor2 : public IMessageProcessor
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

Lets exercise this code.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

The output of this test will be…

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

This is a neat solution and does not require any message processor to interrogate the received message to determine its type.

There an issue with this scheme that may impact the implementation on a resource limited embedded platform. The visitor interface IMessageProcessor must contain a virtual handler function for every message that exists. The vtable for this may become prohibitively large when there are a substantial number of message types. Each derived message processor will have its own copy of the vtable. This will be true even if the derived message processor only handles one message! This may invoke an unacceptable resource overhead.

Also there is the coupling between the visitor interface and the message types. It would be nice if we could make things a little more decoupled.

In part 2 I will describe the first alternative that uses templates and template specialisation to address some of these issues.

Download the example code

Scanning an arbitrarily rotated rectangular region

7th November 2017 / Leave a comment

Quite often in image processing we need to scan a rectangular region in an image. The region is usually aligned to capture a specific feature in the image. You may be presented with a skewed image, necessitating that the region should also be skewed.

If it is not absolutely necessary to scan the region at the angle of skew, then the fastest way to interrogate the pixels is to scan the image horizontally.

As was shown in the previous post, the crossing points between two lines can be easily and efficiently determined.
By moving a reference line down across the region, the start and end x coordinates of each scan line can be found.
Only the y coordinate of the reference line is relevant, though it must have a length of at least 1 unit.

Of course, we must check every line in the rectangle, and every line in the rectangle may produce a crossing point.
The reference line shown below will identify points P1, P2, P3 and P4 as valid crossing points.

The solution is to compare the crossing coordinates against the bounds of the enclosing rectangle. In the example above this would eliminate points P1 and P4.

Vertical scans may be easily achieved by simply having a vertical reference line.
This technique can be applied to any convex hull.

Finding the crossing points of two lines

7th November 2017 / Leave a comment

This is a task that has come up for me many times when creating algorithms for images analysis. Searching the web will invariably turn up the y = Mx + C solution. This is sub-optimal in two ways. First, it has big problems with vertical lines. As the line tends to vertical then m will tend to infinity. This Is Not Good. Secondly, getting any sort of accuracy is impossible without using floating point or large scaling factors.

The code I was modifying at the time was using the y = Mx + C method. It was fairly complex and had to check for lines that were nearly vertical, and flip the axes. It had bugs. I had this gut feeling that must be a better way to solve this, without all of the messing about with edge cases.

Finally after a bit of Googling I came across the lesser used form for describing lines, C = Ax + By. Having lines described in this slightly different form allows a method to find crossing points that is much more code friendly.

Most image processing algorithms I have created work perfectly fine when pixel coordinates are restricted to integral values, allowing integer maths for the following example.

Take two lines, L1 = x1,y1 to x2,y2 and L2 = x3,y3 to x4,y4.

Calculate the values of A, B and C for each line.

For L1:
A1 = y2 – y1
B1 = x1 – x2
C1 = (A1 * x1) + (B1 * y1)

And similarly for L2:

A2 = y4 – y3
B2 = x3 – x4
C2 = (A2 * x3) + (B2 * y3)

Next, work out the determinant.

D = (A1 * B2) – (A2 * B1)

If D is zero then the lines are parallel and there is no crossing point to be found.

If D is not zero then the coordinates of the crossing point may be found thus:

X = ((B2 * C1) – (B1 * C2)) / D
Y = ((A1 * C2) – (A2 * C1)) / D

The two lines do not have to actually cross for this to work. This makes it a great way to find all of the crossing points relative to a reference line.

Next time I will show you how this technique can allow you to scan a rectangular region that is at an arbitrary angle.

Applications of dot and cross products

2nd November 2017 / Leave a comment

The problem

Sometimes in graphical applications there is a need to know the relative position of a point with respect to a line from a reference point.

Where is the target in relation to the reference and its direction?
Dot and cross products can make this an easy task.

Let’s start with a reminder of what dot and cross products are.

Take two vectors x1 , y1 and x2 , y2

The dot product is (x1 * x2) + (y1 * y2) and the cross product is (x1 * y2) – (x2 * y1)

Take the example above. We have a reference object at Xr,Yr facing in the direction of the arrow.
The target is at point Xt,Yt
A arbitrary point on the line from the reference in the specified direction is Xw,Yw

First, find the relative coordinates of the target and waypoint relative to the reference.

dXw = Xw – Xr
dYw = Yw – Yr
dXt = Xt – Xr
dYt = Yt – Yr

Now find the dot and cross products of these vectors.

Dot = (dXw * dXt) + (dYw * dYt)
Cross = (dXw * dYt) – (dXt * dYw)

Assuming the coordinate system is as below.

Dot > 0, Cross < 0 : The target is forward of the reference and to the right.

Dot > 0, Cross > 0 : The target is forward of the reference and to the left.

Dot < 0, Cross < 0 : The target is behind the reference and to the right.

Dot < 0, Cross > 0 : The target is behind the reference and to the left.

‘Forward’, ‘Behind’, ‘Left’ and ‘Right’ are relative to the reference’s direction. This calculation will be correct for any direction.

Other uses

This technique can also be used to determine if a point is within a closed convex hull.

A closed convex hull defined by the lines L1, L2, L3, L4 L5.
Point P1 is inside the hull, point P2 is outside.

For P1, the cross product for all of the lines will indicate that the it is to the right and therefore, must be inside.
For P2, the cross product for L1 will put it on the left hand side and therefore it cannot be inside the hull.

Why does this work?

The dot product of vectors A and B is |A||B|cos(Ø)
The cross product of vectors A and B is |A||B|sin(Ø)
Where Ø is the angle between the vectors A and B. Range +-180°

Therefore the sign of the result indicates the quadrant that target occupies in the circle around the reference, relative to the reference’s direction.