Сегменты линии для проверки попадания

1) У меня есть список сегментов линий (определяемых их двумя конечными точками и шириной.)
2) Эти сегменты линий рисуются на панели.
3) Когда моя мышь перемещается (событие Panel.MouseMove), Я перебираю список сегментов линии.
4) Foreach:

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

5) Если я получаю истину, то я знаю, что мой курсор находится над текущим сегментом линии.

Это отлично работает примерно... 300 строк или около того. Когда я достигаю 1000, моя программа останавливается (профилирование показывает, что это вызвано IsOutlineVisible). Итак, есть ли способ повысить производительность моего алгоритма проверки попаданий? Я не знаю, насколько эффективен IsOutlineVisible, поэтому я не хочу реализовывать какие-либо оптимизации, которые уже использует этот метод. Любые идеи?

EDIT:
Покопавшись в своих данных, я заметил, что некоторые строки были очень большими. Например:
конечная точка1 = (16000, -16000)
конечная точка2 = (5041448, -32868734)

(да, одна из координат находится в отрицательных десятках миллионов...)

Я убедился, что проверки попадания только на один такой сегмент строки достаточно, чтобы остановить мою программу (IsOutlineVisible выполняет тест за 2-3 секунды, и тест запускается всякий раз, когда перемещается курсор...).

Я должен был проверить это более тщательно, прежде чем публиковать. Спасибо всем, кто ответил (двухмерный пространственный индекс — отличное предложение, если мне придется обрабатывать тысячи строк).

p.s. Если кто-нибудь знает, почему большой сегмент строки является такой большой проблемой для IsOutlineVisible, это было бы здорово.


c# winforms hittest system.drawing
person Bob Coder    schedule 09.10.2013    source источник
comment
Возможно, вы захотите взглянуть на Мой пример очень похожей вещи с использованием современных соответствующих технологий пользовательского интерфейса .Net Windows. Он включает в себя некоторые интересные функции, такие как выбор строки и выделение.   -  person Federico Berasategui    schedule 09.10.2013
comment
спасибо, но сейчас я использую winforms.   -  person Bob Coder    schedule 10.10.2013
comment
просто комментарий. Я думаю, что это превращает их в прямоугольники для проверки попаданий. Выполнение этого математически улучшит производительность, например, ограничительная рамка и расстояние с векторами должны быть быстрыми. 1000 строк это слишком много   -  person GorillaApe    schedule 03.05.2015

Ответы (2)


arrow_upward
0
arrow_downward

Попробуй это:

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>();

Это зависит от того, как вы хотите использовать свои lines, если вы хотите их рисовать, мы должны отметить производительность drawing, а не detecting the hovered line, да, в этом случае, drawing - это ваша проблема. Я думаю, мы можем использовать здесь немного Thread. Во всяком случае, я тестировал с 1000 строками, и все работает нормально (с рисованием всех линий в Form Paint) без использования какого-либо потока.

person King King    schedule 09.10.2013

arrow_upward
0
arrow_downward

IsOutlineVisible вызывает Gdi+, возможно, это немного замедляет его работу.

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);
}

Кроме того, эти проверки на попадание не используют оптимизации, такие как построение 2D-индекса всех используемых графических элементов. Чтобы улучшить производительность, я бы попытался

  1. внедрить тестирование на попадание самостоятельно и перебирать все элементы
  2. возможно, использовать 2D-индекс, хотя для ‹ 1000 элементов я вряд ли считаю, что это необходимо.
person citykid    schedule 09.10.2013