Detecting when a mouse cursor is near a line

Warning, this post contains math!

First, I'm abandoning all of my "recreational" coding projects save one: a java applet for my wife to design clothes. Building a CAD system from the ground up is painful and slow, and I can't tinker any further with other fun things without sapping creative energy I need for my day job.

In the current early stages of this project, I've been thinking a lot about design, and what I do and don't like about similar programs. One of the things I don't like about simple CAD-like tools is their approach to manipulating existing lines. The line's endpoints are draggable, and so is a single point in the middle, but the line itself is not. Take this screenshot of Visio, for example:



I can't click on the line itself and move it, I have to grab the box in the middle of the line. The reason this design style is prevalent has a little to do with object oriented design, and a little to do with math. It is trivial to create an object, give it a bounding rectangle, and have a trigger that fires when the mouse cursor enters the rectangle. It is seemingly difficult, at least for those not willing to crunch equations, to detect when the mouse is near a line set at an arbitrary angle. So the design pattern that wins out is finding the middle point of a line, drawing a box there, and making that box an active component.

Wanting to be different, as that is my way, I decided the line itself should be hot, and the user could click anywhere within a few pixels of the line to drag it.

My middle school Algebra and high school Trig classes taught me equations that I found interesting, so I learned them, but like many of my peers, I was skeptical that there was any actual utility in them. They are, in no particular order:

y = mx + b, describing a straight line with slope m and y-intercept b
x² + y² = r², describing a circle whose center is on the origin
Lastly, the quadratic formula. If Ax² + Bx + C = 0, then:



This small snippet from the formula:

can be used to tell me whether or not a line and a circle intersect.

What does this have to do with cursors touching a line? Can't I just see if the cursor point is on the line by plugging it into y = mx + b? That would create a few problems. First, the user would have no wiggle room, the cursor would have to be exactly touching a one pixel thin line. Second, mouse position is defined in integers, and any non-integer points on the line would not be accessible. Third, if the shape is drawn with anything but a basic one pixel stroke, where in the line to place the cursor would be ambiguous.

Considering those problems, it is better to define the cursor's location as a circle with a small radius (say, 5 pixels), and use math to check for line/circle intersections. So instead of plugging the cursor point into the line equation, the line can be plugged into the circle's equation.

Circle on the origin point:
x² + y² = r²

Arbitrary non-vertical line: y = mx + b

Substitute line into circle: x² + (mx + b)² = r²

Multiply out: x² + m²x² + 2mbx + b² = r²

Solve for 0: x² + m²x² + 2mbx + b² - r² = 0

In quadratic form: (m² + 1)x² + (2mb)x + (b² - r²) = 0

Now we have the A, B, and C of the quadratic formula. From there, more math can be applied to find the exact positions of the intersection point(s), but I don't care about that, only whether or not an intersection takes place. That can be determined simply by what type of result the square root function returns. The result types mean the following:

Imaginary number: No intersection.
Zero: Circle and line are tangent.
Positive number: Circle and line intersect at two secant points.

Rather than actually perform the square root, we can just remember that the square root of a negative number is imaginary. So if B² - 4AC > 0, there is an intersection.

Some further formula manipulation gives us this:
(2mb)² - 4(m²+1)(b² - r²) > 0
Divide by 4: (mb)² - (m² + 1)(b² - r²) > 0
Multiply out: (mb)² - ((mb)² + b² - (mr)² - r²) > 0
Simplify: (mb)² - (mb)² - b² + (mr)² + r² > 0
Simplify: -b² + (mr)² + r² > 0
Add b²: (mr)² + r² > b²
Reduce: (m² + 1)r² > b²

Then, with a circle on the origin point whose radius I know, and a line whose slope and y-intercept I know, I can easily tell if an intersection happens. The obvious drawback here is that the circle, being the mouse cursor area, is in motion, and won't be on the origin. Adding in the h and k modifiers to the circle equation makes the above math more complicated, so instead the y-intercept can be adjusted based on the circle's actual center point, like so:

double x = line.getX1() - cursor.getX();
double y = line.getY1() - cursor.getY();
double b = y - slope * x; // Y-intercept

The slope will be calculated once when the line is created to avoid making java do unnecessary math:
slope = (line.getY2() - line.getY1()) / (line.getX2() - line.getX1());
// (m² + 1)r²
range = (slope * slope + 1) * rSquared;

And then the final comparison is trivial:
return range > b * b;

Below is a simple java applet as a proof of concept. Click two points, and a line will be drawn between them. When the line is active, hovering over it will change its color to red. While it is red, it can be clicked on to remove it, and you can then draw a new line.





After taking most of a day (I'm ashamed to admit) to work that out, the fun really starts when I try to apply a similar principle to arbitrary Bezier curves!

Source code for the above:

package cea.demos;

import java.applet.Applet;
import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import java.awt.event.MouseMotionListener;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;

@SuppressWarnings("serial")
public class Intersect extends Applet implements MouseMotionListener, MouseListener {
  private Point2D p;
  private Line2D line;
  private Color color;
  private double slope, range;

  private final int cursorRadius = 5;
  private final int rSquared = cursorRadius * cursorRadius;
  
  public void init() {
    color = Color.BLACK;
    addMouseListener(this);
    addMouseMotionListener(this);
  }
  
  public void paint(Graphics g1) {
    Graphics2D g = (Graphics2D) g1;
    g.setColor(color);
    g.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
    if (line == null) {
      if (p != null) {
        g.setStroke(new BasicStroke(cursorRadius));
        g.drawRect((int)p.getX(), (int)p.getY(), 1, 1);
      }
    } else {
      g.draw(line);
    }
  }
  
  @Override
  public void mouseClicked(MouseEvent e) {
    if (line == null) {
      if (p == null) {
        p = new Point2D.Double(e.getX(), e.getY());
      } else {
        line = new Line2D.Double(p.getX(), p.getY(), e.getX(), e.getY());
        if (line.getX1() != line.getX2()) {
          slope = (line.getY2() - line.getY1()) / (line.getX2() - line.getX1());
          range = (slope * slope + 1) * rSquared;
        }

      } 
    } else {
      if (intersects(e.getPoint())) {
        line = null;
        p = null;
        color = Color.BLACK;
      }
    }
    repaint();
  }

  @Override
  public void mouseMoved(MouseEvent e) {
    if(line == null) return;
    Color oldColor = color;
    color = (intersects(e.getPoint())) ? Color.RED : Color.BLACK;
    if (!color.equals(oldColor)) repaint();
  }
  
  private boolean intersects(Point2D cursor) {
    // Don't check if the cursor isn't in the line's bounding rectangle
    if(!line.getBounds().contains(cursor)) return false;
    
    // Special handling for vertical lines
    if (line.getX1() == line.getX2()) return cursorRadius > Math.abs(cursor.getX() - line.getX1());

    double x = line.getX1() - cursor.getX();
    double y = line.getY1() - cursor.getY();
    double b = y - slope * x; // Y-intercept
    return range > b * b;
  }

 // Unused mouse methods
  @Override public void mousePressed (MouseEvent e) { }
  @Override public void mouseReleased(MouseEvent e) { }
  @Override public void mouseEntered (MouseEvent e) { }
  @Override public void mouseExited  (MouseEvent e) { }
  @Override public void mouseDragged (MouseEvent e) { }
}