# Rectangle Intersection Test (with C#)

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>
/// <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
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.

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.

# WPF crashes on exit

So, I’m working on my WPF application and everything runs fine, but when I close it, I get this error message (together with this doesn’t-say-me-anything stacktrace):

```[System.ComponentModel.Win32Exception]	{"Invalid window handle"}
WindowsBase.dll!MS.Win32.HwndWrapper.DestroyWindow(object args) + 0x11a bytes
WindowsBase.dll!MS.Win32.HwndWrapper.Dispose(bool disposing, bool isHwndBeingDestroyed) + 0x8c bytes
WindowsBase.dll!MS.Win32.HwndWrapper.Dispose() + 0x14 bytes
PresentationCore.dll!System.Windows.Interop.HwndSource.Dispose(bool disposing) + 0x1f6 bytes
PresentationCore.dll!System.Windows.Interop.HwndSource.WeakEventDispatcherShutdown.OnShutdownFinished(object sender, System.EventArgs e) + 0x33 bytes
PresentationFramework.dll!System.Windows.Application.RunDispatcher(object ignore) + 0x17 bytes
PresentationFramework.dll!System.Windows.Application.RunInternal(System.Windows.Window window) + 0x6f bytes
PresentationFramework.dll!System.Windows.Application.Run(System.Windows.Window window) + 0x26 bytes
PresentationFramework.dll!System.Windows.Application.Run() + 0x1b bytes
GuideDock.exe!GuideDock.App.Main() + 0x94 bytes
mscoreei.dll!__CorExeMain@0()  + 0x38 bytes
mscoree.dll!748c7f16()
[Frames below may be incorrect and/or missing, no symbols loaded for mscoree.dll]
mscoree.dll!748c4de3()

This problem seemed to appear only randomly until I figured it out today. The problem can be reproduce by this XAML/C# code (together with a WPF window):

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 ``` ```public partial class MainWindow : Window {   public MainWindow() {     InitializeComponent();       this.m_touchCanvas.MouseLeave += (s, e) => CrashAppOnClose();   }     private void CrashAppOnClose() {     Window wnd = Window.GetWindow(this.m_touchCanvas);     // This line throws a Win32Exception with "Ivalid window handle".     wnd.PointToScreen(new Point());   } }```

Now, when the user closes the window (without using the mouse; eg. with Alt+F4) while the mouse is still in the window, the call to `wnd.PointToScreen()` (line 11) results in the `Win32Exception` above. Unfortunately, the doesn’t seem to be any way to check whether this exception will be thrown – I already tried `Window.IsLoaded` as suggested here with no luck.

What’s more annoying is that the call to `PointToScreen()` does not appear in the stacktrace. I can’t even imaging how this is possible. That’s why it took me ages to figure this one out.

Btw: I’d like to send a bug report to Microsoft but they haven’t got my account working in three months.

• The problem only arises on 64-bit Windows system. A correct exception is thrown on 32-bit systems.
• On 64-bit systems the `Win32Exception` can’t be caught in a `try ... catch` block. Both `PointToScreen()` and the point where the exception is thrown are on the same thread.
• I’ve managed to create a bug report for this problem.

Solution/Workaround:
Given the 32-bit error message – which reads “This Visual is not connected to a PresentationSource.” – I found a way to circumvent this problem. You need to use PresentationSource.FromVisual like this:

```private void CrashAppOnClose() {
Window wnd = Window.GetWindow(this.m_touchCanvas);
if (PresentationSource.FromVisual(wnd) != null) {
wnd.PointToScreen(new Point());
}
}```