Selecting a Geometrical Object


For the last year, I have been working on a project that involves a lot of 2D and 3D geometry. I needed some technique for the user to select these geometries easily, i.e. using the mouse and clicking. The biggest problem was determining how the program knew if the cursor was overlapping the geometry. For a while, I used basic boundary-based selection but found that this was not adequate and I was unable to use any API-based regions.

So, I thought about x and y coordinates and how I can test them to see whether they were in an object. I was able to rule out x-coordinate testing, which saves on processing by using a simple rule. I developed the algorithm using Microsoft Visual Basic 6 and then implemented it within my program using Microsoft Visual C++ .NET 2003 Professional.

Supported Geometry

This algorithm can be used with any shape of geometry, provided that the vertex (or node) positions are known. Here is an example of the kind of geometry that we could be up against.

Is the Cursor Overlapping the Geometry?

So, how do we know whether the mouse pointer is overlapping our geometry? First, we will need to get the mouse pointer's coordinates; in this article, I will show the mouse pointer on the illustrations.

If the mouse is positioned here, obviously the object should be selected upon clicking. Before we can find out whether it is overlapping the object, we need to map the mouse position onto all of the lines of geometry. So, basically we want to find the positions of the red points shown on the next illustration.

An important thing to note with the above illustration is that all of the red points are in pairs of two. So, if the mouse pointer is (vertically) in between a pair of points, the mouse must lie on top of the geometry. When these red points are calculated, there is one per edge within the geometry. If the cursor is not horizontally on the edge, its y-coordinate really does not matter.

In other words:

In the above illustration, I have extended the edge shown in green and added its associated red dot; but, as you can see, the mouse pointer has no relevance to this edge. The mouse would need to be somewhere in the shaded area for it to make any relevance. So, this is the basic theory behind determining whether the mouse pointer overlaps the object and we are only considering the y-coordinate of the mouse. It is possible to map the x-coordinates as well, but that isn't necessary.

Known Problem

Whilst this technique works for most geometry, it will not detect a single line beneath the cursor.

This obviously doesn't work because there is only one point as opposed to a pair of two. You can solve this problem with additional code that tests for the mouse overlapping the line (only when there are non-joint edges), you could allow for the mouse to be out by a couple of pixels to make it easy to select the line. The following illustration is an example of a non-joint polygon; thus, because the mouse pointer is not on (or near) one of the two lines, it should not be selected.

Basic Formula to Obtain Red Points

In general, to obtain the y-coordinate of one of the red points, use this formula:

(x1, y1) - 1st vertex position on line
(x2, y2) - 2nd vertex position on line
a - x-coordinate of mouse position

Gradient: m = (y2 - y1) / (x2 - x1)

X-Coordinate of red point: x = a
Y-Coordinate of red point: y = m * (a - x1) + y1

For those interested in the math, I derived the y-coordinates' formula from:

With this formula, the (x, y) coordinate is that of the red dot; thankfully, we already know the x-coordinate because it is identical to that of the mouse pointer's position.

The Algorithm Behind This (Pseudo Code)

FUNCTION DoSinglePoint(X: Integer, Y: Integer)
  ... Obtain the array of red points ...
   SET nRedPos = 0
   FOR EACH Edge IN Edges
      IF Edge.X2 - Edge.X1 <> 0 THEN
         IF Edge.X1 > Edge.X1 THEN
            SET nPointX1 = Edge.X2
            SET nPointY1 = Edge.Y2
            SET nPointX2 = Edge.X1
            SET nPointY2 = Edge.Y1
            SET nPointX1 = Edge.X1
            SET nPointY1 = Edge.Y1
            SET nPointX2 = Edge.X2
            SET nPointY2 = Edge.Y2
         END IF
         IF X >= nPointX1 AND X < nPointX2 THEN
            SET nTempX = X - nPointX1
            SET nTempY = ((nPointY2 - nPointY1) /
                          (nPointX2 - nPointX1)) * nTempX
            ADD nTempY + nPointY1 TO RedPoints ARRAY
            SET nRedPos = nRedPos + 1
         END IF
      END IF
   NEXT Edge

   ... Sort the array of red points into ascending order ...
   ... Only bother if the array does contain some points ...
   IF nRedPos > 0 THEN
      FOR i = 0 TO nRedPos + 1
         FOR j = i TO nRedPos + 1
            IF RedPoints[i] > RedPoints[j] THEN
               SET PrevPoint = RedPoints[i]
               SET RedPoints[i] = RedPoints[j]
               SET RedPoints[j] = PrevPoint
            END IF
         NEXT j
      NEXT i

   ... Find out whether the mouse pointer is overlapping the geometry ...
   SET i = 0
   SET bOver = FALSE
   WHILE i <= nRedPos DO
      IF Y > RedPoints[i] AND Y < RedPoins[i + 1] THEN
         SET bOver = TRUE
      END IF
      SET i = i + 2

   ... If the mouse pointer is overlapping the geometry, then ...
   IF bOver = TRUE THEN
      ... Do your selection stuff ...


Obviously, this code will need to be adapted to work in your software, but code examples have been included for you to use. I have attached the same examples in both C++ and Visual Basic. I hope that this article has been of some interest to you and that it will help you in some way.

About the Author

Lea Hayes

I have always enjoyed learning new concepts which is one of the things which suits me to programming, because in programming you are always learning new and interesting concepts. I have been programming since about 1995 and have become reasonably experienced with Microsoft Visual Basic 4,5,6 and Microsoft Visual C++ 5,6,7,7.1. Having achieved a double A grade in AVCE ICT I have begun to study BEng Games and Entertainment Systems Engineering at the University of Greenwich at Medway. I have now completed my first year with the kind of results expected from a first-class degree.



  • Handling Corner Case(s)

    Posted by bubulbaruah on 09/29/2005 06:42am

    Need to take care of the corner case like if the internal RED point(s)(not extreme RED points on the vertical line) is exactly on a vertex (edge point), then the same vertex should be considered as ending of the current pair and beginning of next pair. In case of open geometries, like a line segment or angle or polyline, perpendicular distance should be calculated from mouse point to the nearest line segment and compare with some TOLERANCE value.

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Enterprises are increasingly looking to platform as a service (PaaS) to lower their costs and speed their time to market for new applications. Developing, deploying, and managing applications in the cloud eliminates the time and expense of managing a physical infrastructure to support them. PaaS offerings must deliver additional long-term benefits, such as a lower total cost of ownership (TCO), rapid scalability, and ease of integration, all while providing robust security and availability. This report …

  • Moving from an on-premises environment to Office 365 does not remove the need to plan for disruptions or reduce the business risk requirements for protecting email services. If anything, some risks increase with a move to the cloud. Read how to ease the transition every business faces if considering or already migrating to cloud email. This white paper discusses: Setting expectations when migrating to Office 365 Understanding the implications of relying solely on Exchange Online security Necessary archiving …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date