Verbesserte Treffertests in Winforms; eine Alternative zu GraphicsPath.IsVisible?

Question

Auf einem benutzerdefinierten Steuerelement habe ich eine Reihe von LED-Objekten, die gemäß einer gegebenen GraphicsPath eingeschaltet werden sollten (z. B. siehe Bild unten). Derzeit verwende ich graphicsPath.IsVisible(ledPoint), aber da ich viele LEDs habe, kann die Iteration durch alle von ihnen sehr langsam sein, besonders wenn der Pfad komplex ist (z. B. die Umkehrung des Pfads in dem Beispiel).

Hat jemand von Ihnen eine Idee zu etwas schlauer, um Iteration zu beschleunigen? Wenn es zu komplex ist, um ein Beispiel zu geben, kann es sinnvoll sein, mich zu geeigneten Ressourcen umzuleiten. Bitte beachten Sie, dass das Steuerelement in GDI + ist und ein Reengineering in eine andere Engine keine Option ist.

EDIT

---

auf meinem PC (i7 3,6 GHz), wenn sie als GraphicsPath I 100x100 Pixel nur ein einfaches Rechteck haben und dann berechnen ich die inverse auf meiner Kontrolle, das ist Größe von etwa 500x500 Pixel (daher wird die resultierende GraphicsPath wird ein 500x500 Rechteck mit einem "Loch" von 100x100), um 6000 LEDs zu testen dauert etwa 1,5 Sekunden, die zu viel beeinflussen Benutzererfahrung.

Nach Matthew Watson Antwort, ich bin mehr auf meinem Beispiel Detaillierung:

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

Auf meinem PC habe ich ~ 725ms auf den ersten Test und ~ 5000 ms auf dem zweiten. Und das ist nur ein ziemlich einfacher Weg. Die GraphicsPath wird durch Mausbewegungen des Benutzers generiert, und der Benutzer kann mehrere Pfade kombinieren (Invertierung, Vereinigung, Schnittpunkt, .. Ich verwende dafür GPC). Daher kann das Testen auf Inversion durch Testen der Negation von GraphicsPath.IsVisible() schwierig sein.

Die inversePath kehrte von Utility.CombinePath ist ganz einfach und hat Punkten nach (links PathPoints, rechts PathTypes):

Answer 1

Eine Optimierung nur innerhalb des effektiven Grenzen Rechteck zu testen:

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)).. 

Ein weiterer Trick ist flatten der Pfad, so dass es aus Zeile nur Segmente besteht:

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

Die Auswahl eines größeren flatness hilft auch. Ich habe mit 1 oder 2 die Geschwindigkeit leicht verdoppelt.

Ich habe nicht Ihre Prüfstände verwenden, aber die Ergebnisse helfen sollen:

Testen Sie diesen Pfad:

Die Zeit ging:

25781 (ohne Grenzen)

7929 (nur innerhalb der Grenzen)

3067 (in Grenzen & werden abgeflacht von 2)

Notiere die die erste wird nur, wenn Sie von der ClientRectangle mit und die zweite helfen nur beginnen invertieren nicht helfen, wenn die Bahnkurven tatsächlich enthält.

Update:

auf Hans Vorschlag aufgreifend, ist dies bei weitem die effektivste 'Optimierung': (!)

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

Es ist meine Timings nimmt bis auf 10-20 ms

So ist es nicht wirklich nur eine "Optimierung"; es ist eine schreckliche Verschwendung der Zeit zu vermeiden, lesen: im Grunde ging keine Zeit überhaupt in die Prüfung und alle ging in Einrichtung die Testregion.

Von Hans Passant Kommentar:

GraphicsPath.IsVisible erfordert den Pfad zu einer Region unter der Haube umgewandelt werden. Machen Sie das vorne mit dem Region (GraphicsPath) Konstruktor, so dass Sie diese Kosten nicht für jeden einzelnen Punkt bezahlen müssen.

Hinweis, die zu den anderen Pfaden verglichen wird, ist mir sehr komplexe ; deshalb sind meine Einsparungen viel größer als diejenigen, die Sie von einem Rechteck mit einem rechteckigen Loch oder so erwarten können. User gezeichnet Pfade wie meins (oder die aus dem OP) leicht neigen dazu, aus Hunderten von Segmenten, nicht nur eine 4-8 ..

Answer 2

Ich denke, es ist etwas anderes sich die Zeit nehmen muss, weil meine Tests, dass ich zeigen 250.000 Punkte in weniger als einer Sekunde testen:

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

der obige Code Ergebnisse von weniger als 900ms gibt. (Ich laufe auf einem alten Prozessor mit einer Geschwindigkeit von weniger als 3 GHz.)

Sie sollten in der Lage sein, 6000 Punkte in weniger als 25 ms zu testen.

Dies scheint darauf hinzudeuten, dass die Zeit woanders genommen wird.

(Beachten Sie, dass die Inverse zu testen alles, was Sie !path.IsVisible(x, y) verwenden zu tun haben, statt path.IsVisible(x, y).)

---

Als Reaktion auf die editierte Frage:

Wie gesagt, die invers zu testen Alles, was Sie tun müssen, ist !Path.IsVisible(x,y). Sie scheinen es zu invertieren, indem Sie ein umschließendes Rechteck hinzufügen - das funktioniert, ist aber nicht notwendig und verlangsamt die Dinge.

Der folgende Code demonstriert, was ich meine - beachten Sie die 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));