programming – Page 2

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.

The details of the solution can be found in the CGA FAQ linked above. A C++ implementation can be found here: http://code.google.com/p/curve-project/source/browse/trunk/lab/cgafaq/cgafaq.h 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.

  BaseWnd::BaseWnd(void): hwnd(0)
  {
    if(wndClassAtom == 0){
      if(Register() == 0)
        throw app0_exception(ERR_CLASS_REGISTRATION_FAILED);
    }

    hwnd = CreateWindowEx(WS_EX_OVERLAPPEDWINDOW,
      MAKEINTATOM(wndClassAtom), WINDOW_TITLE,
      WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, 0, 0,
      GetModuleHandle(0), this);

    if(hwnd == 0)
      throw app0_exception(ERR_WINDOW_CREATION_FAILED);
  }

BaseWnd::BaseWnd(void): hwnd(0)

{

if(wndClassAtom == 0){

if(Register() == 0)

throw app0_exception(ERR_CLASS_REGISTRATION_FAILED);

}

hwnd = CreateWindowEx(WS_EX_OVERLAPPEDWINDOW,

MAKEINTATOM(wndClassAtom), WINDOW_TITLE,

WS_OVERLAPPEDWINDOW, CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, 0, 0,

GetModuleHandle(0), this);

if(hwnd == 0)

throw app0_exception(ERR_WINDOW_CREATION_FAILED);

}

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.

  LRESULT CALLBACK InitWndProc(HWND hwnd, UINT msg,
    WPARAM wParam, LPARAM lParam){

    if(msg == WM_CREATE){
      return HANDLE_WM_CREATE(hwnd, wParam, lParam, App0::BaseWnd_OnCreate);
    }
    else
      return ::DefWindowProc(hwnd, msg, wParam, lParam);
  }

LRESULT CALLBACK InitWndProc(HWND hwnd, UINT msg,

WPARAM wParam, LPARAM lParam){

if(msg == WM_CREATE){

return HANDLE_WM_CREATE(hwnd, wParam, lParam, App0::BaseWnd_OnCreate);

}

else

return ::DefWindowProc(hwnd, msg, wParam, lParam);

}

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.

  LRESULT CALLBACK BaseWndProc(HWND hwnd, UINT msg,  // non-member
    WPARAM wParam, LPARAM lParam){

    return BaseWnd::WndProc(hwnd, msg, wParam, lParam);
  }

  // static member
  LRESULT BaseWnd::WndProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam){
    LONG_PTR ptr = ::GetWindowLongPtr(hwnd, GWL_USERDATA);
    BaseWnd* window = reinterpret_cast<BaseWnd*>(ptr);
    if(window == 0)
      throw app0_exception(_T("Object pointer is 0."));

    return window->WndProc(msg, wParam, lParam);
  }

  LRESULT BaseWnd::WndProc(UINT msg, WPARAM wParam, LPARAM lParam){
    switch(msg){
      HANDLE_MSG(hwnd, WM_CLOSE, OnWmClose);
      HANDLE_MSG(hwnd, WM_DESTROY, OnWmDestroy);
    }

    return ::DefWindowProc(hwnd, msg, wParam, lParam);
  }

LRESULT CALLBACK BaseWndProc(HWND hwnd, UINT msg, // non-member

WPARAM wParam, LPARAM lParam){

return BaseWnd::WndProc(hwnd, msg, wParam, lParam);

}

// static member

LRESULT BaseWnd::WndProc(HWND hwnd, UINT msg, WPARAM wParam, LPARAM lParam){

LONG_PTR ptr = ::GetWindowLongPtr(hwnd, GWL_USERDATA);

BaseWnd* window = reinterpret_cast(ptr);

if(window == 0)

throw app0_exception(_T("Object pointer is 0."));

return window->WndProc(msg, wParam, lParam);

}

LRESULT BaseWnd::WndProc(UINT msg, WPARAM wParam, LPARAM lParam){

switch(msg){

HANDLE_MSG(hwnd, WM_CLOSE, OnWmClose);

HANDLE_MSG(hwnd, WM_DESTROY, OnWmDestroy);

}

return ::DefWindowProc(hwnd, msg, wParam, lParam);

}

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.

Perpendiculars

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

Given points A(x_a, y_a) and B(x_b, y_b), perpendiculars BB_ccw and BB_cw to the line AB can be constructed at B using either of the following points:

B_ccw(x_b – (y_b – y_a), y_b + (x_b – x_a)) // such that ABB_ccw is oriented counter-clockwise

B_cw(x_b + (y_b – y_a), y_b – (x_b – x_a)) // such that ABB_cw 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.

#include <cstdio>

struct P2 {
  float x;
  float y;

  P2(float x, float y) : x(x), y(y) {
  }
};

P2 PerpendicularCW(const P2& a, const P2& b){
  return P2(b.x + (b.y - a.y), b.y - (b.x - a.x));
}

P2 PerpendicularCCW(const P2& a, const P2& b){
  return P2(b.x - (b.y - a.y), b.y + (b.x - a.x));
}

int main(){
  P2 a(20, 20), b(80, 60);
  P2 pccw = PerpendicularCCW(a, b);
  P2 pcw = PerpendicularCW(a, b);

  printf("a(%f,%f),b(%f,%f)\n";, a.x, a.y, b.x, b.y);
  printf("pccw(%f,%f)\n", pccw.x, pccw.y);
  printf("pcw(%f,%f)\n", pcw.x, pcw.y);

  return 0;
}

#include

struct P2 {

float x;

float y;

P2(float x, float y) : x(x), y(y) {

}

};

P2 PerpendicularCW(const P2& a, const P2& b){

return P2(b.x + (b.y - a.y), b.y - (b.x - a.x));

}

P2 PerpendicularCCW(const P2& a, const P2& b){

return P2(b.x - (b.y - a.y), b.y + (b.x - a.x));

}

int main(){

P2 a(20, 20), b(80, 60);

P2 pccw = PerpendicularCCW(a, b);

P2 pcw = PerpendicularCW(a, b);

printf("a(%f,%f),b(%f,%f)\n";, a.x, a.y, b.x, b.y);

printf("pccw(%f,%f)\n", pccw.x, pccw.y);

printf("pcw(%f,%f)\n", pcw.x, pcw.y);

return 0;

}

Output:

a(20.000000,20.000000),b(80.000000,60.000000)
pccw(120.000000,0.000000)
pcw(40.000000,120.000000)

a(20.000000,20.000000),b(80.000000,60.000000)

pccw(120.000000,0.000000)

pcw(40.000000,120.000000)