Find last drawn pixel of C# Metafile

Question

I have a Metafile object. For reasons outside of my control, it has been provided much larger (thousands of times larger) than what would be required to fit the image drawn inside it.

For example, it could be 40 000 x 40 000, yet only contains "real" (non-transparent) pixels in an area 2000 x 1600.

Originally, this metafile was simply drawn to a control, and the control bounds limited the area to a reasonable size.

Now I am trying to split it into different chunks of dynamic size, depending on user input. What I want to do it count how many of those chunks will be there (in x and in y, even the splitting is into a two-dimensional grid of chunks).

I am aware that, technically, I could go the O(N²) way, and just check the pixels one by one to find the "real" bounds of the drawn image.

But this will be painfully slow.

I am looking for a way of getting the position (x,y) of the very last drawn pixel in the entire metafile, without iterating through every single one of them.

Since The DrawImage method is not painfully slow, at least not N² slow, I assume that the metafile object has some optimisations on the inside that would allow something like this. Just like the List object has a .Count Property that is much faster than actually counting the objects, is there some way of getting the practical bounds of a metafile?

The drawn content, in this scenario, will always be rectangular. I can safely assume that the last pixel will be the same, whether I loop in x then y, or in y then x.

How can I find the coordinates of this "last" pixel?

Answer 1

Finding the bounding rectangle of the non-transparent pixels for such a large image is indeed an interesting challenge.

The most direct approach would be tackling the WMF content but that is also by far the hardest to get right.

Let's instead render the image to a bitmap and look at the bitmap.

First the basic approach, then a few optimizations.

To get the bounds one need to find the left, top, right and bottom borders.

Here is a simple function to do that:

Rectangle getBounds(Bitmap bmp)
{
    int l, r, t, b; l = t = r = b = 0;
    for (int x = 0; x < bmp.Width - 1; x++) 
    for (int y = 0; y < bmp.Height - 1; y++) 
            if (bmp.GetPixel(x,y).A > 0) { l = x; goto l1; }
    l1:
    for (int x = bmp.Width - 1; x > l ; x--) 
    for (int y = 0; y < bmp.Height - 1; y++) 
            if (bmp.GetPixel(x,y).A > 0) { r = x; goto l2; }
    l2:
    for (int y = 0; y < bmp.Height - 1; y++) 
    for (int x = l; x < r; x++) 
            if (bmp.GetPixel(x,y).A > 0) { t = y; goto l3; }
    l3:
    for (int y = bmp.Height - 1; y > t; y--) 
    for (int x = l; x < r; x++) 
            if (bmp.GetPixel(x,y).A > 0) { b = y; goto l4; }
    l4:

    return Rectangle.FromLTRB(l,t,r,b);
}

Note that is optimizes the last, vertical loops a little to look only at the portion not already tested by the horizontal loops.

It uses GetPixel, which is painfully slow; but even Lockbits only gains 'only' about 10x or so. So we need to reduce the sheer numbers; we need to do that anyway, because 40k x 40k pixels is too large for a Bitmap.

Since WMF is usually filled with vector data we probably can scale it down a lot. Here is an example:

string fn = "D:\\_test18b.emf";
Image img = Image.FromFile(fn);

int w = img.Width;
int h = img.Height;
float scale = 100;
Rectangle rScaled = Rectangle.Empty;

using (Bitmap bmp = new Bitmap((int)(w / scale), (int)(h / scale)))
using (Graphics g = Graphics.FromImage(bmp))
{
    g.ScaleTransform(1f/scale, 1f/scale);
    g.Clear(Color.Transparent);
    g.DrawImage(img, 0, 0);
    rScaled = getBounds(bmp);
    Rectangle rUnscaled = Rectangle.Round(
         new RectangleF(rScaled.Left * scale, rScaled.Top * scale, 
                        rScaled.Width * scale, rScaled.Height * scale ));

 }

Note that to properly draw the wmf file one may need to adapt the resolutions. Here is an example i used for testing:

    using (Graphics g2 = pictureBox.CreateGraphics())
    {
        float scaleX = g2.DpiX / img.HorizontalResolution / scale;
        float scaleY = g2.DpiY / img.VerticalResolution / scale;

        g2.ScaleTransform(scaleX, scaleY);
        g2.DrawImage(img, 0, 0);    // draw the original emf image.. (*)
        g2.ResetTransform();
        // g2.DrawImage(bmp, 0, 0); // .. it will look the same as (*)
        g2.DrawRectangle(Pens.Black, rScaled);
    }

I left this out but for fully controlling the rendering, it ought have been included in the snippet above as well..

---

This may or may not be good enough, depending on the accuracy needed.

To measure the bounds perfectly one can do this trick: Use the bounds from the scaled down test and measure unscaled but only a tiny stripe around the four bound numbers. When creating the render bitmap we move the origin accordingly.

Example for the right bound:

Rectangle rScaled2 = Rectangle.Empty;
int delta = 80;
int right = (int)(rScaled.Right * scale);

using (Bitmap bmp = new Bitmap((int)(delta * 2 ), (int)(h )))
using (Graphics g = Graphics.FromImage(bmp))
{
    g.Clear(Color.Transparent);
    g.DrawImage(img, - right - delta, 0);
    rScaled2 = getBounds(bmp);
}

I could have optimized by not going over the full height but only the portion (plus delte) we already found..

Further optimization can be achieved if one can use knowledge about the data. If we know that the image data are connected we could use larger steps in the loops until a pixel is found and then trace back one step..