Улучшение хитов в Winforms; любая альтернатива GraphicsPath.IsVisible?

Question

На пользовательском контроле У меня есть серия светодиодных объектов, которые должны быть включены в соответствии с данным GraphicsPath (например, см. Рисунок ниже). В настоящее время я использую graphicsPath.IsVisible(ledPoint), однако, поскольку у меня много светодиодов, итерация через все они могут быть очень медленными, особенно если путь сложный (например, обратный путь в примере).

Есть ли у вас какие-либо идеи относительно чего-то более умного для ускорения итерации? Если это слишком сложно, чтобы привести пример, это может привести к перенаправлению меня к соответствующим ресурсам. Пожалуйста, учтите, что элемент управления находится в GDI +, реинжиниринг в другой движок не является вариантом.

EDIT

---

на моем компьютере (i7 3,6 ГГц), когда в качестве GraphicsPath Я только простой прямоугольник 100х100 пикселей, а затем я вычислить обратную на моем контроле, который размером от 500x500 пикселей (следовательно, итоговый GraphicsPath будет прямоугольником 500x500 с «отверстием» 100x100), для тестирования 6000 светодиодов занимает около 1,5 секунд, что слишком сильно повлияет на работу пользователя.

После Мэтью Уотсон ответ, я детализацией больше на моем примере:

//------ Base path test 
GraphicsPath path = new GraphicsPath(); 
path.AddRectangle(new Rectangle(100, 100, 100, 100)); 

var sw = System.Diagnostics.Stopwatch.StartNew(); 
for (int x = 0; x < 500; ++x) 
    for (int y = 0; y < 500; ++y) 
     path.IsVisible(x, y); 
Console.WriteLine(sw.ElapsedMilliseconds); 

//------ Inverse path test 
GraphicsPath clipRect = new GraphicsPath(); 
clipRect.AddRectangle(new Rectangle(0, 0, 500, 500)); 
GraphicsPath inversePath = Utility.CombinePath(path, clipRect, CombineMode.Complement); 

sw.Restart(); 
for (int x = 0; x < 500; ++x) 
    for (int y = 0; y < 500; ++y) 
     inversePath.IsVisible(x, y); 
Console.WriteLine(sw.ElapsedMilliseconds); 

На моем компьютере у меня есть ~ 725ms на первом тесте и ~ 5000 мс на секунду. И это довольно простой путь. GraphicsPath генерируется движением мыши пользователя, и пользователь может выполнять несколько комбинаций путей (инвертирование, объединение, пересечение, я использую для этого GPC). Следовательно, тестирование на инверсию путем тестирования отрицания GraphicsPath.IsVisible() может быть сложным.

inversePath вернулся из Utility.CombinePath довольно проста и имеет следующие пункты (слева PathPoints, справа PathTypes):

Answer 1

Одна оптимизации заключается в проверке только в пределах эффективных границ прямоугольника:

Rectangle r = Rectangle.Round(path.GetBounds()); 
for (int x = r.X; x < r.Width; ++x) 
    for (int y = r.Y; y < r.Height; ++y) 
     if (path.IsVisible(x, y)).. 

Другого трюк должен flatten путь, так что он состоит из строка только сегменты:

Matrix m = new Matrix(); 
path.Flatten(m, 2); 

Также помогает сбор крупного flatness. Я нашел с 1 или 2 скорость легко удваивалась.

Я не использовал свои тестовые стенды, но результаты должны помочь:

Тестирования этого пути:

Время спускался:

25781 (без границ)

7929 (только в границах)

3067 (в границах & flattend на 2)

Обратите внимание на первый только поможет, если вы не инвертировать в ClientRectangle, чтобы начать с, а второй только поможет, если путь на самом деле содержит кривые.

Update:

Занимая по предложению Ганса, это далеко наиболее эффективным 'оптимизации' (!)

Region reg = new Region(path); 
for (int x = r.X; x < r.Width; ++x) 
    for (int y = r.Y; y < r.Height; ++y) 
     reg.IsVisible(x, y); 

Он берет мои тайминги до 10-20ms

Таким образом, это не просто «опиумность»; он избегает большинства ужасных отходов времени, читайте: в основном нет времени вообще пошло на тестирование и все пошло в , установив область тестирования.

От комментария Ганса Passant в:

GraphicsPath.IsVisible требует путь для преобразования в области под капотом. Сделайте это с помощью конструктора Region (GraphicsPath) , чтобы вы не платили эту стоимость за каждую точку.

Примечание, что по сравнению с другими путями, шахта очень комплекс; поэтому мои сбережения намного больше, чем те, которые можно ожидать от прямоугольника с прямоугольным отверстием или подобным. Пользовательские рисунки, как и мой (или один из ОП), легко имеют тенденцию состоять из сотен сегментов, а не только от 4 до 8 ...

Answer 2

Я думаю, что должно быть что-то еще, что нашли время, потому что мои тесты показывают, что I может тестировать 250 000 точек менее чем за секунду:

GraphicsPath path = new GraphicsPath(); 

path.AddLine( 0, 0, 100, 0); 
path.AddLine(100, 0, 100, 100); 
path.AddLine(100, 100, 0, 100); 
path.AddLine( 0, 100, 0, 0); 

var sw = Stopwatch.StartNew(); 

for (int x = 0; x < 500; ++x) 
    for (int y = 0; y < 500; ++y) 
     path.IsVisible(x, y); 

Console.WriteLine(sw.ElapsedMilliseconds); 

Приведенный выше код дает результаты менее 900 мс. (Я работаю на старом процессоре со скоростью менее 3 гц.)

Вы должны быть способны протестировать 6000 точек менее чем за 25 мс.

Это, по-видимому, указывает на то, что время берется в другом месте.

(Обратите внимание, что для проверки инверсии все, что вам нужно сделать, это использовать !path.IsVisible(x, y) вместо path.IsVisible(x, y).)

---

В ответ на отредактированной вопрос:

Как я уже сказал, чтобы проверить обратный все, что вам нужно сделать, это использовать !Path.IsVisible(x,y). Кажется, вы инвертируете его, добавив содержащий прямоугольник - который работает, но не нужен и замедляет работу.

Следующий код демонстрирует, что я имею в виду - отмечает Trace.Assert():

GraphicsPath path = new GraphicsPath(); 
path.AddRectangle(new Rectangle(100, 100, 100, 100)); 

GraphicsPath inversePath = new GraphicsPath(); 
inversePath.AddRectangle(new Rectangle(100, 100, 100, 100)); 
inversePath.AddRectangle(new Rectangle(0, 0, 500, 500)); 

for (int x = 0; x < 500; ++x) 
    for (int y = 0; y < 500; ++y) 
     Trace.Assert(inversePath.IsVisible(x, y) == !path.IsVisible(x, y));