Hit-testing line segments

Question

1) I have a list of line segments (defined by their two endpoints and a width.)
2) These line segments are drawn in a panel.
3) When my mouse moves (Panel.MouseMove event), I loop over the list of line segments.
4) Foreach:

  gPath.Reset();
  Pen Pen = new Pen(Color.White, 20);
  gPath.AddLine(P1, P2);
  return gPath.IsOutlineVisible(cursorPos, Pen);

5) If I get true, then I know my cursor is hovering over the current line segment.

This works fine for about... 300 lines or so. When I reach 1,000 my program slows to a halt (profiling shows that it's caused by IsOutlineVisible). So, is there any way I could increase performance of my hit-testing algorithm? I don't know how efficient IsOutlineVisible is, so I don't want to implement any optimizations that the method already uses. Any ideas?

EDIT:
After digging into my data I noticed some of the lines were extremely large. For example:
endpoint1 = (16000, -16000)
endpoint2 = (5041448, -32868734)

(yes, one of the coordinates is in the negative tens of millions...)

I verified that hit-testing against just one such line segment is enough to bring my program to a halt, (IsOutlineVisible takes 2-3 seconds to do the test, and the test is run whenever the cursor moves...).

I should have tested this more thoroughly before posting. Thanks to all that responded (a 2d spatial index is a great suggestion if I end-up handling thousands of lines).

p.s. If anyone knows why a large line-segment is that big a problem for IsOutlineVisible, that would be great.

You may want to have a look at [My Example](http://stackoverflow.com/a/15469477/643085) of a very similar thing using current, relevant .Net Windows UI technologies. It includes some interesting functionalities such as line selection and highlight. — Federico Berasategui, Oct 09 '13 at 16:03
just a comment. I think it makes then into rectangles foe hit testing. Doing it mathematically would improve performance ,for example bounding box and distance with vectors should be fast. 1000 lines is too much though — GorillaApe, May 03 '15 at 11:19

score 0 · Answer 1 · answered Oct 09 '13 at 07:47

Try this:

public Line GetHotSpottedLine(Point mousePos){
        var line = lines.Where(line =>
        {
            Point p1 = new Point(Math.Min(line.P1.X, line.P2.X), Math.Min(line.P1.Y, line.P2.Y));
            Point p2 = new Point(Math.Max(line.P1.X, line.P2.X), Math.Max(line.P1.Y, line.P2.Y));
            return mousePos.X >= p1.X && mousePos.X <= p2.X && mousePos.Y >= p1.Y && mousePos.Y <= p2.Y;
        }).FirstOrDefault(line => {
            using (GraphicsPath gp = new GraphicsPath())
            {
                gp.AddLine(line.P1, line.P2);
                //You can declare your pen outside and this pen should be used to draw your lines.
                using (Pen p = new Pen(Color.Red, 20))
                {
                    return gp.IsOutlineVisible(mousePos, p);
                }
            }
        });
        return line;
 }
 public class Line{
        public Point P1 { get; set; }
        public Point P2 { get; set; }
 }
 List<Line> lines = new List<Line>();

It depends on how you want to use your lines, if you want to draw them, we have to notice the performance of drawing not detecting the hovered line, yes in that case, drawing is your problem. I think we can use some Thread here. Anyway, I tested with 1000 lines and it works OK (with drawing all the lines in Form Paint) without using any thread.

score 0 · Answer 2 · answered Oct 09 '13 at 07:48

IsOutlineVisible calls the Gdi+, maybe this slows it down a bit.

public bool GraphicsPath.IsOutlineVisible(PointF pt, Pen pen, Graphics graphics)
{
  int num;
  if (pen == null)
  {
      throw new ArgumentNullException("pen");
  }
  int status = SafeNativeMethods.Gdip.GdipIsOutlineVisiblePathPoint(new HandleRef(this, this.nativePath), pt.X, pt.Y, new HandleRef(pen, pen.NativePen), new HandleRef(graphics, (graphics != null) ? graphics.NativeGraphics : IntPtr.Zero), out num);
  if (status != 0)
  {
      throw SafeNativeMethods.Gdip.StatusException(status);
  }
  return (num != 0);
}

Beside that, these hit testing do not use optimizations like building an 2d index of all graphical elements used. To improve the performance I would try to

implement hit testing yourself and iterating over all elements
maybe use a 2D index, although for < 1000 elements I hardly believe this is necessary.

Hit-testing line segments

2 Answers2