改进 Winforms 中的命中测试； GraphicsPath.IsVisible 有什么替代品吗？

Question

在自定义控件上，我有一系列 LED 对象应根据给定 GraphicsPath 打开（例如，见下图）。目前我正在使用 graphicsPath.IsVisible(ledPoint)，但是由于我有很多 LED，因此所有 LED 的迭代可能会非常慢，尤其是在路径很复杂的情况下（例如示例中的路径的逆向）。

你们有没有想出更聪明的方法来加速迭代？如果举个例子太复杂，它可能会把我重定向到适当的资源。请考虑该控件位于 GDI+ 中，无法将其重新设计到另一个引擎中。

编辑

在我的 PC (i7 3.6GHz) 上 GraphicsPath 我只有一个简单的矩形 100x100 像素，然后我在我的控件上计算大小约为 500x500 像素的逆（因此，结果 GraphicsPath将是一个500x500的矩形，'hole'为100x100)，测试6000个LED大约需要1.5秒，这会影响用户体验。

在 Matthew Watson 回复之后，我将详细说明我的示例：

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

在我的 PC 上，第一次测试大约有 725 毫秒，第二次测试大约有 5000 毫秒。这只是一条相当简单的路径。 GraphicsPath 由用户的鼠标移动生成，用户可以执行多种路径组合（反转、并集、交集……我为此使用 GPC）。因此，通过测试 GraphicsPath.IsVisible() 的否定来测试反转可能很棘手。

从Utility.CombinePath返回的inversePath非常简单，有以下几点（左PathPoints，右PathTypes）：

Answer 1

我想一定是有别的东西占用了时间，因为我的测试表明我可以在不到一秒的时间内测试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 毫秒的结果。（我运行使用速度低于 3GHz 的旧处理器。）

您应该能够在不到 25 毫秒的时间内测试 6000 个点。

这似乎表明时间正在别处。

（请注意，要测试逆，您所要做的就是使用 !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));

Answer 2

一个优化是只在有效边界矩形内测试：

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 by 2）

请注意，第一个只有在您没有通过客户端矩形开始反转时才有用，第二个只有在路径实际包含曲线时才有用。

更新：

采纳汉斯的建议，这是迄今为止最有效的'optimization':

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-20 毫秒 (!)

所以它不仅仅是一个 'opimization'；它避免了最可怕的浪费时间，阅读：基本上没有时间进入测试，所有时间都进入了设置测试区域。

来自 Hans Passant 的评论：

GraphicsPath.IsVisible requires the path to be converted to a region under the hood. Do that up front with the Region(GraphicsPath) constructor so you don't pay that cost for every single point.

注意与其他路径相比，我的路径非常复杂；因此，我的积蓄 比您从带有长方形孔的长方形或类似物中期望的积蓄多多。 用户绘制的路径 像我的（或来自 OP 的）很容易由数百段组成，而不仅仅是 4-8..

改进 Winforms 中的命中测试； GraphicsPath.IsVisible 有什么替代品吗？

Improving hit-testing in Winforms; any alternative to GraphicsPath.IsVisible?

c#

gdi+

hittest

winforms

graphicspath