Подсчет уникальных пикселей в нарисованном изображении фигур

Question

Я работаю над графическим приложением, в котором пользователь может нарисовать любое количество линий (с некоторой толщиной от точки A до точки B), прямоугольников или эллипсов на холсте.

После того, как ониГотово, у меня есть набор данных формы, указывающий местоположение каждой фигуры и нарисованной линии, и мне нужно определить, сколько уникальных пикселей они раскрасили в рамках исследовательского проекта.

Мой наивный алгоритм заключается в реализации формы bool. Содержит (x, y) для каждой фигуры и вызывает ее для каждой нарисованной фигуры для каждого пикселя в изображении, чтобы определить, был ли этот пиксель нарисован линией, прямоугольником илиэллипс.

Работая другим способом, я мог бы создать void shape.SetPixels (bool [,] canvas) и установить для каждой фигуры значение true, каждый пиксель, который он содержит.Это то, что я на самом деле реализовал, и с большими наборами данных это мучительно медленно.

У меня такое ощущение, что есть более прямой путь от необработанных данных формы к нужному выводу без изучения каждого пикселя.Так что мой вопрос, учитывая набор данных формы, есть ли функция O (n) bool [,] IsColored (int x, int y) {}, которая может генерировать матрицу true / false для цветных пикселей более непосредственно, чем либоИдея, которую я дал?

Answer 1

Избегайте метода Bitmap.GetPixel. Это очень очень медленно. Если возможно, ваш низкоуровневый доступ к растровым данным с помощью LockBits или аналогичных методов.

В одном из моих проектов я использовал:

public void LoadFromBitmap(Bitmap bmp)
    {
        if (bmp.Width != Width || bmp.Height != Height)
            throw new ArgumentException("Size missmatch");
        unsafe
        {
            BitmapData bmpData = null;
            try
            {
                bmpData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

                for (int y = 0; y < bmpData.Height; y++)
                {
                    uint* p = (uint*)((byte*)bmpData.Scan0 + y * bmpData.Stride);
                    for (int x = 0; x < bmpData.Width; x++)
                    {
                        this[x, y] = RawColor.FromARGB(*p);
                        p++;
                    }
                }
            }
            finally
            {
                if (bmpData != null)
                    bmp.UnlockBits(bmpData);
            }
        }
    }

https://github.com/CodesInChaos/ChaosUtil/blob/master/Chaos.Image/Pixels.cs

Другая оптимизация - реализация пула для вашего пикселя, содержащего массивы. Частое размещение объектов в куче больших объектов в моем опыте сильно подчеркивает gc.

Answer 2

Два метода, о которых вы говорите, - это, как правило, два основных варианта.Либо проверяйте каждый пиксель по мере необходимости, либо заранее создайте некую структуру данных для быстрого поиска.

Если у вас большой холст, но только несколько фигур (таким образом, относительно немного «на» пикселях), тогда онЛучше всего просто записать каждый пиксель, попавший под любую форму, например, в хеш.

HashSet<KeyValuePair<int,int>> listOfPixelsHitByAnyShape = new HashSet()

foreach(Shape s in allShapes)
{
    s.Draw(listOfPixelsHitByAnyShape); // will update listOfPixelsHitByAnyShape
}

// Now we can easily query if a pixel is set
bool isSet = listOfPixelsHitByAnyShape.Contains(new KeyValuePair(10,99))

Это должно быть быстрым для поиска, за счет памяти и времени для создания HashSet.

Но это будет не так быстро, как ваша SetPixels(bool[,] canvas) версия, и не будет использовать столько памяти (в редком случае, о котором мы говорим).

Answer 3

Если вы не используете графическую библиотеку, пожалуйста, сделайте!

---

Если это графическое приложение, вероятно, вы уже рисуете то, что вводит пользователь.Вы не можете просто запросить это?Вы всегда можете нарисовать две разные цели, одну для красивой пользовательской версии, а другую для запроса (каждый объект имеет уникальный цвет).

Как вы хотите бороться с перекрытиями?

---

Какого размера набор данных мы говорим?Рендеринг должен быть «свободным», поскольку растровое изображение может быть построено, когда пользователь рисует в приложении.

Если то, что вы сделали, действительно медленное, вы можете рассмотреть использование графического процессора для рисования и запроса (возможно, используямодные шейдеры).