For a software project I needed to check whether two rectangles intersect (or overlap). What made my problem complicated was that one of the rectangles could be rotated. While this problem seems to be trivial (to a human being), it’s not that simple to implement. It took me a while to find the right answer.

Now, the solution to this problem is called a separating axis test. Basically this means: If I can find an axis (read: line) that separates both rectangles, then they don’t intersect/overlap. (Actually this works for any convex polygon; see below) Of course, if the two rectangles don’t intersect, there are undefinitely many possible separating axes. Fortunately we can use the edges of each rectangle as axes and testing all of the is sufficient.

I won’t get into the details of this algorithm here – it’s sufficiently good described in the article mentioned above – but basically you check for each point on which side of the separating axis it is. If all points of the rectangle A are on one side and all of rectangle B are on the other side, then we’ve found a separating axis.

Here’s the implementation of the method testing where a single edge (represented by points x1 and x2) is a separating axis:

/// <summary>
/// Does axis separation test for a convex quadrilateral.
/// </summary>
/// <param name="x1">Defines together with x2 the edge of quad1 to be checked whether its a separating axis.</param>
/// <param name="x2">Defines together with x1 the edge of quad1 to be checked whether its a separating axis.</param>
/// <param name="x3">One of the remaining two points of quad1.</param>
/// <param name="otherQuadPoints">The four points of the other quad.</param>
/// <returns>Returns <c>true</c>, if the specified edge is a separating axis (and the quadrilaterals therefor don't 
/// intersect). Returns <c>false</c>, if it's not a separating axis.</returns>
bool DoAxisSeparationTest(Point x1, Point x2, Point x3, Point[] otherQuadPoints) {
  Vector vec = x2 - x1;
  Vector rotated = new Vector(-vec.Y, vec.X);

  bool refSide = (rotated.X * (x3.X - x1.X)
                + rotated.Y * (x3.Y - x1.Y)) >= 0;

  foreach (Point pt in otherQuadPoints) {
    bool side = (rotated.X * (pt.X - x1.X) 
               + rotated.Y * (pt.Y - x1.Y)) >= 0;
    if (side == refSide) {
      // At least one point of the other quad is one the same side as x3. Therefor the specified edge can't be a
      // separating axis anymore.
      return false;
    }
  }

  // All points of the other quad are on the other side of the edge. Therefor the edge is a separating axis and
  // the quads don't intersect.
  return true;
}

This method is then called for each edge of each rectangle. If the method returns true, the actual intersection test method can return “not intersecting”. If the method returns false for all edges, the rectangles intersect.

I’ve created an C#/WPF example implementation (under FreeBSD license) that you can download and experiment with.

Rectangle Intersection Test Project (for Visual Studio 2010)

Remarks: The algorithm above works for every convex polygon. Instead of four times two edges you then have n times m edges. For concave polygons, however, this algorithm doesn’t work because there may be no separating axis even though the polygons don’t intersect.

In Android 3.x, Google switched from USB Mass Storage to MTP for files stored in the “external storage”. For any device created before Android 3.x, creating a file and copying it off the device was easy:

File dir = Environment.getExternalStoragePublicDirectory("My App");
File file = new File(dir, "test.txt");
FileUtils.writeStringToFile(file, "Hello File");

This would place a file called test.txt in the directory My App on the SD card/external storage. You then would connect your Android device via USB with your computer, enable USB mass storage, and simply copy the file off the device.

With newer devices (like the Galaxy Nexus I’m using) that’s no longer enough because they use MTP instead of USB Mass Storage. If you’d execute the code above, the file would be created but it wouldn’t show up in the Windows Explorer (or whatever tool you’re using the view the device’s contents).

To make the file show up, after closing it use the following code (API documentation):

MediaScannerConnection.scanFile(ctx, new String[] { file.getAbsolutePath() }, null, null);

After doing this the file should appear immediately in the Windows Explorer.

Notes:

• The external storage is scanned automatically when the Android device is booting (e.g. after a restart).
• If you pass a directory (instead of a file) to scanFile(), the directory will show up as file in Window Explorer, so don’t do this.

For a project I was wondering what’s the performance penalty of using a C# struct (containing only one field) over using a local variable directly; i.e.:

int myVar;

vs.

struct MyStruct {
  int MyVar;
}

The result: There’s no (real) difference!

Here are some stats (“Release” build):

Running each test 50,000,000,000 times

Running 'UseLocalVar'...
Done in 61329.359 ms
Running 'UseStructField'...
Done in 61414.885 ms
Running 'UseStructProperty'...
Done in 121383.416 ms

The first two results are what I was talking about. The third result uses a property instead of a field in the struct. It’s two times slower.

Here’s the code for the benchmark:

using System;
using System.Diagnostics;

class Benchmark {
  const long LOOPS = 50000000000;

  static void Main(string[] args) {
    Benchmark benchmark = new Benchmark();

    Console.WriteLine("Running each test {0:0,0} times", LOOPS);
    Console.WriteLine();

    Console.WriteLine("Running 'UseLocalVar'...");
    Stopwatch stopWatch = Stopwatch.StartNew();
    int test = 0;
    for (long x = 0; x < LOOPS; x++) {
      test += benchmark.UseLocalVar((int)x);
    }
    TimeSpan elapsed = stopWatch.Elapsed;
    Console.WriteLine("Done in {0:0.000} ms", elapsed.TotalMilliseconds);


    Console.WriteLine("Running 'UseStructField'...");
    stopWatch = Stopwatch.StartNew();
    test = 0;
    for (long x = 0; x < LOOPS; x++) {
      test += benchmark.UseStructField((int)x);
    }
    elapsed = stopWatch.Elapsed;
    Console.WriteLine("Done in {0:0.000} ms", elapsed.TotalMilliseconds);


    Console.WriteLine("Running 'UseStructProperty'...");
    stopWatch = Stopwatch.StartNew();
    test = 0;
    for (long x = 0; x < LOOPS; x++) {
      test += benchmark.UseStructProperty((int)x);
    }
    elapsed = stopWatch.Elapsed;
    Console.WriteLine("Done in {0:0.000} ms", elapsed.TotalMilliseconds);
  }

  int UseLocalVar(int val) {
    int test = val;
    test = test + val;
    return test;
  }

  int UseStructField(int val) {
    TestStructField test = new TestStructField(val);
    test.Value = test.Value + val;
    return test.Value;
  }

  int UseStructProperty(int val) {
    TestStructProperty test = new TestStructProperty(val);
    test.Value = test.Value + val;
    return test.Value;
  }

  private struct TestStructField {
    public int Value;

    public TestStructField(int value) {
      this.Value = value;
    }
  }

  private struct TestStructProperty {
    public int Value { get; set; }

    public TestStructProperty(int value) : this() {
      this.Value = value;
    }
  }
}

I’ve been working for quite some time now with Subversion but recently fell in love with Mercurial. Mercurial (like GIT or Bazaar) is a distributed version control system (DVCS). Coming from Subversion, it’s sometimes necessary to convert an existing Subversion repository to Mercurial. And that’s what this post is about.

Read more →

P/Invoke is a way of calling C/C++ functions from a .NET program. It’s very easy to use. This article will cover the basics of using P/Invoke.

Note: This tutorial will focus on Windows and thus use Visual Studio. If you’re developing on another platform or with another IDE, adopting the things in this article should be easy enough.

Read more →