Dennis Crain
Microsoft Developer Network Technology Group
Created: February 8, 1994
Click to open or copy the files in the W32HIT sample application for this technical article.
Useful graphics applications, such as CAD or drawing programs, permit the user to select and manipulate graphics objects. This article describes three methods for detecting if the user has selected a line or a curve.
The first method is used to hit test lines. It uses two-dimensional vector techniques that resolve the vector components of the line and the point at which the user clicked the mouse. These vector methods are described in detail in the "Use of Two-Dimensional Vectors with Windows NT" technical article in the Microsoft® Development Library.
The second method illustrates how to hit test Bézier curves using one of two techniques. The first technique involves calculating the points of the Bézier curve. The distance from the mouse click to the nearest point of the Bézier curve determines if the line was successfully hit. The second technique illustrates the use of paths in Win32®. Bézier curves or arcs are drawn into a path, which is flattened to produce an array of points that describes line segments. These line segments are then tested using the vector method to detect line hit testing. An accompanying sample program, W32HIT, demonstrates these methods. W32HIT is a modification of the W32PEN sample that accompanies the "Pens in Win32" article in the Development Library.
To the user, the act of hit testing in a graphical user interface seems natural. The pointing device's cursor is placed over an object, and the user initiates an action to "hit" the object. Most often this pointing device is a mouse, and the action is a mouse click.
Within the context of this article, let's agree that hit testing is the process of determining if the user has selected a line or a curve by means of a mouse click. I will describe three methods for selecting these objects. Two methods are general in that they do not rely on any of the functionality of Win32®. The third method combines the line hit-testing method with a new feature of Win32, paths.
Many programmers know hit testing as "picking," the term used in many textbooks on graphics and in many graphics languages. For example, you pick a line segment on the screen and move it to another location.
The methods described in this article hinge on a single user-initiated event. The user has placed the mouse cursor over a line or a curve and has clicked a mouse button, indicating that the object is to be selected. The challenge then is to ensure that the application will detect and act on this intent. What goes on after this detection takes place is up to the application. The application often considers the line or curve as a "selected object." This object may then be acted on in some fashion, such as moving it to a different location or changing its attributes (such as line style or width). The sample code provided with this article does two things: First, it indicates that the object has been selected by redrawing the object using the inverse of the current pen color. Second, it displays a dialog box that permits the user to change the attributes of the object, such as the pen attributes and object type (straight line, curve, or arc).
In this scenario, the user is attempting to select a previously drawn line. There are many methods for detecting the presence of a point (the mouse click) on or near a line. The simplest but least accurate test is to detect if the point is within the rectangular area bounding the line. This works great if the line is horizontal or vertical, but it is obviously less useful for lines that are not parallel to the x or y axes. However, by using the bounding rectangle you can quickly determine if you should continue using this method or switch to a different, more accurate method to determine the distance of the point to the line. It is possible to use various algebraic methods involving the angle between the lines formed by one endpoint of the line, the point at the mouse click, and the second endpoint of the original line. However, having to deal with angles can be somewhat time consuming (unless you have a lookup table). A more reasonable approach might involve comparing the slopes of the two lines. As we will see, this approach also has some problems.
Figures 1 and 2 illustrate this concept. In Figure 1, the slope of the line from (x0, y0) to (x1, y1) is not the same as the line from (x0, y0) to (x2, y2). In Figure 2, the slope of these lines is the same. But is it reasonable to assume that, by simply comparing the slopes, in all cases it's safe to say that a point is on the line if the slopes are equal? To say yes to this, some boundary checking needs to take place before comparing the slopes. Again, this is where the bounding rectangle is useful. In the case of Figure 1, the point (x1, y1) lies outside the bounding rectangle. This can easily be checked by using the PtInRect function, which is found in all versions of Microsoft® Windows™. Because the point is not within the bounding rectangle, there is no need to compare the two slopes.
Figure 1. Slopes of lines are not equal
In Figure 2, the point (x1, y1) is obviously within the bounding rectangle. Comparing the slopes of the two lines makes sense in this case.
Figure 2. Slopes of lines are equal
The calculation of the slope of a line is likely stamped in our brains from our grade school days. Recall that the slope of the line between two points (x0, y0) and (x1, y1) is as follows:
This approach will work—sometimes. But there are some problems. If the comparison is based on equality, you might as well forget it. Your user may click on the line until he or she is blue in the face. Remember, this is a raster output device. The resolution of your slope calculations may not coincide with the pixels that are turned on. Okay, so try comparing it to a range of slopes. Create two lines on either side of the point of the mouse click (not inclusive of the point). Figure 3 illustrates this concept. This will minimize error, but you are left to find the points perpendicular to the line at any given slope of the original line, and you double your calculations. In addition, it is really dependent on points. The use of points tends to constrain one to a specific coordinate system. Although there are ways to work around all of this, it is probably easier to address the issue with vectors.
Figure 3. Using a range of slopes
One of the challenges of the previous solution involves finding points at an equal distance from the mouse click and perpendicular to the line. Call it coincidence, but the perpendicular line just happens to be a normal vector. So why not take the normal vector and the magnitude of that vector to achieve a solution? As it turns out, it works—and it is accurate and reliable. The technique for finding the distance from a point to a line involves resolving the vector between one of the endpoints of the line and the point at which the mouse click occurred into its components. Figure 4 illustrates the two vectors involved. Vector a is the vector from the left endpoint of the line to the mouse click. Vector b is the vector between the two endpoints of the line.
Figure 4. Vectors between points of line and mouse click
Figure 5 shows how vector a is projected onto vector b. The components of the newly projected vector are shown as well. Notice that the length of the normal (perpendicular to the line) vector is the distance from the mouse click to the line.
Figure 5. Components of a vector
To find the length of vector e in Figure 5, you need to find the components of vector c, which is vector a projected onto vector b. The following code illustrates the process of finding the length of the vector normal to the line.
typedef struct tagVECTOR2D {
double x;
double y;
} VECTOR2D, *PVECTOR2D;
double vGetLengthOfNormal(PVECTOR2D a, PVECTOR2D b)
{
VECTOR2D c, vNormal;
//
//Obtain projection vector.
//
//c = ((a * b)/(|b|^2))*b
//
c.x = b->x * (vDotProduct(a, b)/vDotProduct(b, b));
c.y = b->y * (vDotProduct(a, b)/vDotProduct(b, b));
//
//Obtain perpendicular projection : e = a - c
//
vSubtractVectors(a, &c, &vNormal);
//
//Fill PROJECTION structure with appropriate values.
//
return (vVectorMagnitude(&vNormal));
}
This code calls three functions: vDotProduct, vSubtractVectors, and vVectorMagnitude. The dot product of two vectors is the sum of the products of the components of the vectors. The dot product for the vectors a and b is a1 * a2 + b1 * b2. Given the sample vectors (4, 5) and (2, 3), the dot product is 4 * 2 + 5 * 3, or 23. This may be implemented as follows:
double vDotProduct(PVECTOR2D v0, PVECTOR2D v1)
{
double dotprod;
dotprod = (v0 == NULL || v1 == NULL)
? 0.0
: (v0->x * v1->x) + (v0->y * v1->y);
return(dotprod);
}
Subtraction of vectors is straightforward. The corresponding elements of the vectors are simply subtracted, as the following code illustrates.
PVECTOR2D vSubtractVectors(PVECTOR2D v0, PVECTOR2D v1, PVECTOR2D v)
{
if (v0 == NULL || v1 == NULL)
v = (PVECTOR2D)NULL;
else
{
v->x = v0->x - v1->x;
v->y = v0->y - v1->y;
}
return(v);
}
The length or magnitude of a vector is the distance from the head of the vector to the tail of the vector. Distance is the operative word here. Remember the Pythagorean theorem? It asserts that the distance between two points can be obtained by the formula:
If you have doubts, take a look at a math textbook. Because the components of a two-dimensional vector are the differences between two points, this formula can be restated as follows, given the vector a:
This relationship is easily implemented in the following code.
double vVectorMagnitude(PVECTOR2D v0)
{
double dMagnitude;
if (v0 == NULL)
dMagnitude = 0.0;
else
dMagnitude = sqrt(vVectorSquared(v0));
return (dMagnitude);
}
The following code demonstrates the use of VECTOR2D.DLL and an exported function called vDistFromPointToLine. This function basically does all of what I described earlier in the vGetLengthOfNormal function. The "Use of Two-Dimensional Vectors with Windows NT" technical article in the Microsoft Development Library describes this dynamic-link library (DLL) in detail. The HitTestLine function creates two vectors from the line to be hit tested, and a combination of the left endpoint of the line and the point at which the mouse was clicked. vDistFromPointToLine is then called. This function projects the mouse vector onto the line and resolves it into its components as outlined above. I've removed error and line boundary checking from this code fragment for readability.
//Macro to convert mouse points (short) to points (long).
#define MPOINT2POINT(mpt, pt) ((pt).x = (mpt).x, (pt).y = (mpt).y)
//Macro to convert two points to a 2-D vector.
#define POINTS2VECTOR2D(pt0, pt1, vect) \
((vect).x = (double)((pt1).x - (pt0).x), \
(vect).y = (double)((pt1).y - (pt0).y))
BOOL HitTestLine(POINT pt0, POINT pt1, POINTS ptMouse, int nWidth)
{
POINT PtM;
VECTOR2D tt0, tt1;
double dist;
int nHalfWidth;
//
//Get the half width of the line to adjust for hit testing of wide lines.
//
nHalfWidth = (nWidth/2 < 1) ? 1 : nWidth/2;
//
//Convert the line into a vector using the two endpoints.
//
POINTS2VECTOR2D(pt0, pt1, tt0);
//
//Convert the mouse points (short) into a POINT structure (long).
//
MPOINT2POINT(ptMouse ,PtM);
//
//Convert the line from the left endpoint to the mouse point into a vector.
//
POINTS2VECTOR2D(pt0, PtM, tt1);
//
//Obtain the distance of the point from the line.
//
dist = vDistFromPointToLine(&pt0, &pt1, &PtM);
//
//Return TRUE if the distance of the point from the line is within the width
//of the line
//
return (dist >= -nHalfWidth && dist <= nHalfWidth);
}
That's all there is to it! Once you determine that you hit the line, you can do anything you want. Applications most often set the status of the line as "selected"; then the user decides what happens to the line. As I mentioned previously, the sample provided with this article, W32HIT, does two things: First, it indicates that the object has been selected by redrawing the object using the inverse of the current pen color. Second, it displays a dialog box that permits the user to change the attributes of the object, such as the pen attributes and object type (straight line, curve, or arc).
Hit testing a Bézier curve presents a challenge. If you use the Bézier functions of Win32, the points used to draw the line are not immediately available to you. Consider the Win32 PolyBezier function. This function takes as a parameter a pointer to an array of POINT structures that contain the endpoints and control points of the spline(s). Do not mistake these control points for the actual points used to draw the curve. Figure 6 illustrates a Bézier curve and the control points used to determine the shape of the curve. The control polygon (not to be confused with the convex hull) is simply the polygon formed by the control points. It should be clear that the points on the curve itself are not specified. The PolyBezier function is responsible for generating the points that lie on the curve. You may recall that the Bézier curves may be generated as a special case of B-spline curves (if you don't recall this, I recommend that you take a look at one of the many textbooks available on the subject). Win32 implements Bézier curves as cubic B-splines. There is much more to the subject of Bézier curves than this simple explanation—the point I am making is that these four points, in and of themselves, are not sufficient to determine if a mouse click is on the line generated by a Bézier curve.
Figure 6. Bézier curve and associated control points and control polygon
So just how do you go about determining the points used to draw the curve? In Win32, you have two choices: You can either calculate the points yourself or use the path functions new to Win32. Once you come up with the points, you then need to determine whether the point at which the mouse click occurred is on the curve.
Calculating the points of a Bézier curve is not complex, but it does lend itself to a long-winded exegesis. So, if you don't already understand how to do this, I offer this intuitive explanation: Bézier curves can be subdivided into smaller curves to the point at which the control polygon of those smaller curves is flat. When this condition exists, the curve segment can be drawn as a straight line. Arriving at this, you have two control points that are very close to one another. You can find points on the line by means of linear interpolation, or just test the distance of a point from the line, as was done above.
This subdivision works best if done recursively. To do this, you need to write your own recursive subdivision function and a function to determine if the control polygon is flat. Or you can use the code provided in the W32HIT sample. I ported code from the public domain à la the book Graphics Gems. This code determines the nearest point on a curve to a test point.
Win32 provides a convenient method for obtaining the line segments used to produce curves. Using paths and the associated application programming interfaces (APIs), you can draw curves and subsequently flatten them to produce the line segments. The problem of hit testing is then reduced to testing if a mouse click was on one of the line segments. The following code fragment demonstrates this.
//
//This structure is referred to in the following code fragment as pTempPR.
//
typedef struct tagPENRECORD {
DWORD dwPenType;
POINT PtsToDraw[NUMPOINTS];
DWORD dwPenStyle;
DWORD dwJoinStyle;
DWORD dwEndCapStyle;
DWORD dwWidth;
LOGBRUSH lb;
XFORM xf;
int nPickPriority;
DWORD dwLineType;
DWORD dwFlags;
struct tagPENRECORD *next;
struct tagPENRECORD *prev;
} PENRECORD, *PPENRECORD, FAR *LPPENRECORD;
//
//Begin the path.
//
if (BeginPath(hdc))
{
//
//Draw a Bézier curve into the path.
//
PolyBezier(hdc, (LPPOINT)pTempPR->PtsToDraw, NUMPOINTS);
//
//Select the path into the DC.
//
if (EndPath(hdc))
{
//
//Flatten the path to produce a list of the line segments used to produce
//the curve.
//
if (FlattenPath(hdc))
//
//Get the number of vertices contained in the list of line segments.
//
nNumPoints = GetPath(hdc, (LPPOINT)NULL, (LPBYTE)NULL, 0);
//
//If the call was successful then the number of points is known and > 0.
//
if (nNumPoints > 0)
{
//
//Allocate memory for the list of path vertices and vertex types.
//
lpPt = (LPPOINT)malloc((DWORD)(sizeof(POINT) * nNumPoints));
lpB = (LPBYTE)malloc((DWORD)(sizeof(BYTE) * nNumPoints));
//
//Go and really get them this time.
//
nNumPoints = GetPath(hdc, lpPt, lpB, nNumPoints);
//
//Move through the list and test if the mouse click happened on any of the
//line segments.
//
for (nPt = 0; nPt < nNumPoints - 1; nPt++)
{
//
//Is the point on the line?
//
if (HitTestLine(lpPt[nPt], lpPt[nPt + 1], ptMouse, pTempPR->dwWidth))
MessageBeep(0);
}
free(lpPt);
free(lpB);
}
}
}
The call to BeginPath is the first part of what is called a path bracket. Once you call BeginPath, you can specify the points in the path by calling one or more of the functions that can be used with paths, as shown in Table 1.
Table 1 Functions That Can Be Used with Paths
| AngleArc | LineTo | Polyline |
| Arc | MoveToEx | PolylineTo |
| ArcTo | Pie | PolyPolygon |
| Chord | PolyBezier | PolyPolyline |
| CloseFigure | PolyBezierTo | Rectangle |
| Ellipse | PolyDraw | RoundRect |
| ExtTextOut | Polygon | TextOut |
In the above code, a call to PolyBezier is made into the path. The call to EndPath selects the path into the device context. The FlattenPath function transforms any curves in the selected path into a sequence of lines. Finally, the code retrieves the coordinates of the line segments by calling the GetPath function.
The most convenient technique for hit testing curves other than Bézier curves is the path method described above. However, remember that this technique is restricted to those functions that can be used with paths as listed in Table 1, and it only works in Win32.
The sample application, W32HIT, demonstrates the methods described in this article. The application should look familiar to those who have seen the W32PEN application, also included in the Development Library. However, there are differences. W32HIT adds new functionality to W32PEN. Support for Bézier curves and arcs is included (W32PEN provided only polyline support). Hit testing is included; the hit-testing methods are the same as those described above. The user interface changed slightly; an extra menu item was added that permits the user to select one of two methods for hit testing Bézier curves (calculating the points or using paths). Hit testing of lines uses the vector method; hit testing of arcs uses the path method.
To draw a line or curve in the workspace of W32HIT, press the left mouse button while the mouse cursor is over the workspace (denoted by the presence of the left-slanted pen cursor). This brings up the pen and line selection dialog box as shown in Figure 7.
Figure 7. Pen and line selection dialog box
To hit test a line, place the mouse cursor over the line and press the left mouse button as shown in Figure 8. If you have hit the line, it will be redrawn using the inverse of the pen color. Then the dialog box in Figure 7 will appear. You can change any of the attributes of the pen and line/curve at that time.
Figure 8. Place cursor over line and press left mouse button
Hit testing lines and curves is basic to a good drawing program. Even so, it is not immediately clear how you should go about implementing this in applications. I have described three methods you can use. The first method illustrated the use of vectors for hit testing lines. The second method used a recursive subdivision of a Bézier curve to generate the points of the curve. The third method discussed the use of paths. These paths were flattened and the subsequent lines were hit tested using the vector method. A note of caution, though—paths are restricted to Win32. If you are hit testing outside this environment, you will need to generate the points for hit testing curves.