Intersection of Line Segments (from CGA FAQ)

Intersection of two line segments
involves the following cases:

  • Segments are parallel
  • Segments are collinear/coincident
  • One segment intersects the extension of the other
  • Extension of one segment intersects the extension of the other
  • Segments intersect each other.

Intersection of Two Line Segments

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: The function cgafaq::intersect takes 4 points — the start and end points of each of the lines. r and s are output parameters calculated as described in the FAQ.

Disclaimer: This post and the code provided are not endorsed by any of the contributors to the CGA FAQ.

C++ Windows GUI Wrapper

App0 is a C++ wrapper over Windows API calls for a typical windowed application. This is similar to the framework used in curve. The design is mostly drawn from Win32 Programming by James M. Newcomer and Brent Rector.

The BaseWnd class wraps around a HWND. CreateWindowEx is called in the constructor. Before the CreateWindowEx call, I register the window class if it has not already been registered.

Since the WindowProc cannot be a member function, I use two non-members: InitWndProc is used till a WM_CREATE is received and BaseWndProc is used for the rest of the windows lifetime.

InitWndProc forwards all messages except WM_CREATE to DefWindowProc. WM_CREATE is forwarded to BaseWnd_OnCreate which saves the object pointer (passed to CreateWindowEx) at GWL_USERDATA and also replaces the window procedure (currently InitWndProc) with BaseWndProc.

BaseWndProc forwards all messages to the static BaseWnd::WndProc method which retrieves the object pointer and forwards messages to the BaseWnd::WndProc instance method. The instance method behaves like a typical WindowProc and forwards selected messages to other instance methods (OnWmClose, OnWmDestroy) while relegating all other messages to DefWindowProc.

Call stack for message handler
Call stack for message handler

I use InitWndProc initially because until WM_CREATE the object pointer has not yet been attached to the HWND and BaseWndProc depends on the object pointer.

Download source here.


I often need to construct perpendiculars in my code and found a very elegant solution to this problem in CGAL source.

Given points A(xa, ya) and B(xb, yb), perpendiculars BBccw and BBcw to the line AB can be constructed at B using either of the following points:

Bccw(xb – (yb – ya), yb + (xb – xa)) // such that ABBccw is oriented counter-clockwise


Bcw(xb + (yb – ya), yb – (xb – xa)) // such that ABBcw is clockwise.

This follows from the fact that the product of the slopes of perpendicular lines is -1.

Here is code to return either of these points.