Hit testing lines

GDI+ is an immediate mode graphics system, this is to say that when you draw on it, then the action is carried out and all record of that action is forgotten, leaving only the changed pixels to show for it. There is no internal storage that can be used to remember where lines or shapes were painted and so testing for a particular shape after it has been drawn is all but impossible.

Most graphical systems that use GDI or GDI+ as output are, in some way or another, retained mode systems that need to store some record of where the lines and shapes will be painted so that when the Paint event comes along, the graphics may be reconstructed again. The actual data stored however is as diverse as the programs that store it and there is no set standard that we, as programmers can follow.

A further complication to the detection of lines and shapes is the shape and style of the pen used to stroke the objects. These may be fat or thin, have dotted lines and shaped end-caps but when the line is drawn, all you provide is the end-points and the pen and hence the line is rendered for you by the system. This means that even when you know where the end-points are, you cannot guarantee that the mouse point is actually in the line.

How then can such a vague association between the description of the line and the actual pixels output by the line renderer ever be analysed to return the correct line from many hundreds drawn on a page?

Happily, GDI+ provides a relatively simple if roundabout method of doing just that.

Your first priority is to create a retained mode graphics system. This is not as daunting as it may sound, you just need to describe the graphical objects and their properties. For example a line could be described very simply by the class shown in listing 1.

You can see that the class itself is very simple just containing a start point, end point and a pen width. It also has a draw method that outputs the line to the graphics object when required.

A number of lines can be kept in an array or specialized collection and then drawn in the OnPaint method as shown in listing 2

private void Form1_Paint(object sender, System.Windows.Forms.PaintEventArgs e)
{
foreach(Line l in Lines)
l.DrawLine(e.Graphics,Color.Black);
}

Now, whatever lines are stored in the Lines collection will be reproduced on screen.

You can clearly see that the lines are drawn with a thick pen which makes the ends of the lines square and distinct. The end points of the line however are buried within the rendered line as shown in figure 2.

Figure 2 above shows that line styles and line caps can make a lot of difference when detecting a specific line. In these cases it is not sufficient to assume that you know where you are, even if you have a great algorithm for line intersections.

To overcome such problems, the same mechanism that renders the complex polygons that comprise a styled line can be used to create a list of polygons in a GraphicsPath object that you can then hit-test. The method that does this particular bit of magic is GraphicsPath.Widen.

Widening a path by a provided pen produces a list of line segments that exactly duplicate the outline of complex pens. Finally the GraphicsPath.IsVisible method can be used to determine whether a specific point is inside one of the portions of the line, however complex that line may be. This method works for straight lines, polygons, Beziers and cardinal splines.

Listing 3 shows our simple Line class object with a hit-testing method built into it. Of course, this demonstration only uses the standard pen but it really does work on a dotted line with custom line caps.

public class Line
{
public Point StartPoint;
public Point EndPoint;
public int PenWidth;

public void DrawLine(Graphics g,Color c)
{
Pen p=new Pen(c,PenWidth);
g.DrawLine(p,StartPoint,EndPoint);
p.Dispose();
}

public bool IsInLine(Point pnt)
{
Pen p = new Pen(Color.Black,PenWidth);
GraphicsPath pth=new GraphicsPath();
pth.AddLine(StartPoint,EndPoint);
pth.Widen(p);
p.Dispose();
if(pth.IsVisible(pnt))
return true;
return false;
}
}

This Line class built into a simple Windows Forms application will enable you to detect one or more line from a list of objects.

In the final listing of this article I have provided a simple test application that places lines and detects which one the mouse is in as the mouse pointer moves about the window. When the mouse is detected in a line, the line will be repainted in red.

using System;

using System.Drawing;

using System.Drawing.Drawing2D;

using System.Collections;

using System.ComponentModel;

using System.Windows.Forms;

using System.Data;

namespace findlines

{

/// <summary>

/// Summary description for Form1.

/// </summary>

public class Form1 : System.Windows.Forms.Form

{

/// <summary>

/// Required designer variable.

/// </summary>

private System.ComponentModel.Container components = null;

private Line CurrentLine;

private bool AddingLine;

private LineArray Lines=new LineArray();

private Point LastPos;

private bool first = true;

public Form1()

{

// Required for Windows Form Designer support

InitializeComponent();

// TODO: Add any constructor code after InitializeComponent call

}

/// <summary>

/// Clean up any resources being used.

/// </summary>

protected override void Dispose( bool disposing )

{

if( disposing )

{

if (components != null)

{

components.Dispose();

}

base.Dispose( disposing );

}

#region Windows Form Designer generated code

/// <summary>

/// Required method for Designer support - do not modify

/// the contents of this method with the code editor.

/// </summary>

private void InitializeComponent()

{

// Form1

this.AutoScaleBaseSize = new System.Drawing.Size(5, 13);

this.BackColor = System.Drawing.Color.White;

this.ClientSize = new System.Drawing.Size(292, 273);

this.Name = "Form1";

this.Text = "Form1";

this.MouseDown += new System.Windows.Forms.MouseEventHandler(this.Form1_MouseDown);

this.MouseUp += new System.Windows.Forms.MouseEventHandler(this.Form1_MouseUp);

this.Paint += new System.Windows.Forms.PaintEventHandler(this.Form1_Paint);

this.MouseMove += new System.Windows.Forms.MouseEventHandler(this.Form1_MouseMove);

}

#endregion

/// <summary>

/// The main entry point for the application.

/// </summary>

[STAThread]

static void Main()

{

Application.Run(new Form1());

}

private void Form1_MouseDown(object sender, System.Windows.Forms.MouseEventArgs e)

{

CurrentLine = new Line();

CurrentLine.StartPoint=new Point(e.X,e.Y);

AddingLine = true;

}

private void Form1_MouseMove(object sender, System.Windows.Forms.MouseEventArgs e)

{

Graphics g=CreateGraphics();

if(!AddingLine)

{

foreach(Line l in Lines)

{

if(l.IsInLine(new Point(e.X,e.Y)))

l.DrawLine(g,Color.Red);

else

l.DrawLine(g,Color.Black);

}

LastPos = new Point(e.X,e.Y);

}

else

{

if(!first)

ControlPaint.DrawReversibleLine(PointToScreen(CurrentLine.StartPoint), PointToScreen(LastPos), Color.White);

LastPos = new Point(e.X,e.Y);

ControlPaint.DrawReversibleLine(PointToScreen(CurrentLine.StartPoint), PointToScreen(LastPos), Color.White);

first=false;

}

private void Form1_MouseUp(object sender, System.Windows.Forms.MouseEventArgs e)

{

CurrentLine.EndPoint=new Point(e.X,e.Y);

CurrentLine.PenWidth=5;

Lines.Add(CurrentLine);

AddingLine = false;

Invalidate();

}

private void Form1_Paint(object sender, System.Windows.Forms.PaintEventArgs e)

{

foreach(Line l in Lines)

l.DrawLine(e.Graphics,Color.Black);

}

public class Line

{

public Point StartPoint;

public Point EndPoint;

public int PenWidth;

public void DrawLine(Graphics g,Color c)

{

Pen p=new Pen(c,PenWidth);

g.DrawLine(p,StartPoint,EndPoint);

p.Dispose();

}

public bool IsInLine(Point pnt)

{

Pen p = new Pen(Color.Black,PenWidth);

GraphicsPath pth=new GraphicsPath();

pth.AddLine(StartPoint,EndPoint);

pth.Widen(p);

p.Dispose();

if(pth.IsVisible(pnt))

return true;

return false;

}

public class LineArray : CollectionBase

{

public void Add(Line l)

{

List.Add(l);

}

public Line this[int index]

{

get{return (Line)List[index];}

set{List[index]=value;}

}

Return to the GDI+ FAQ.

Hit testing lines and shapes.