Линейни сегменти за тестване на хитове

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, така че не искам да прилагам никакви оптимизации, които методът вече използва. Някакви идеи?

РЕДАКТИРАНЕ:
След като се порових в данните си, забелязах, че някои от редовете са изключително големи. Например:
крайна точка1 = (16000, -16000)
крайна точка2 = (5041448, -32868734)

(да, една от координатите е в отрицателните десетки милиони...)

Проверих, че тестването за попадение срещу само един такъв сегмент от линия е достатъчно, за да спре програмата ми (IsOutlineVisible отнема 2-3 секунди, за да направи теста, и тестът се изпълнява всеки път, когато курсорът се движи...).

Трябваше да тествам това по-задълбочено, преди да публикувам. Благодаря на всички, които отговориха (2d пространствен индекс е чудесно предложение, ако в крайна сметка работя с хиляди редове).

p.s. Ако някой знае защо голям сегмент от линия е толкова голям проблем за IsOutlineVisible, това би било чудесно.


c# winforms hittest system.drawing
person Bob Coder    schedule 09.10.2013    source източник
comment
Може да искате да разгледате Моят пример за много подобно нещо, използващо текущи, подходящи .Net Windows UI технологии. Той включва някои интересни функции като избор на линия и подчертаване.   -  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