塗りつぶしのサンプルプログラムを作ってみましたが、検査済み座標を記憶するためDictionary<T>を使っていましたが、シンプルに座標に対応した２次元配列にした方が高速化するのではと思い、作りなおしてみました。
プロジェクトの作成
PowerShellで実行。要dotnet.exe
mkdir SamplePaint2
cd SamplePaint2
dotnet new wpf
code .ソースコード
<Window x:Class="SamplePaint2.MainWindow"
xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
xmlns:d="http://schemas.microsoft.com/expression/blend/2008"
xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006"
xmlns:local="clr-namespace:SamplePaint2"
mc:Ignorable="d"
Title="MainWindow" Height="450" Width="800">
<Grid>
<Image x:Name="image1" Stretch="None" />
</Grid>
</Window>using System.Collections.Generic;
using System.Windows;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Diagnostics;
using System.Threading.Tasks;
namespace SamplePaint2
{
///
/// Interaction logic for MainWindow.xaml
///
public partial class MainWindow : Window
{
static void DrawLine(ref WriteableBitmap bitmap, int x0, int y0, int x1, int y1, Color c)
{
int width = (int)bitmap.PixelWidth;
int height = (int)bitmap.PixelHeight;
int pixelsSize = (width * 4) * height;
byte[] pixels = new byte[pixelsSize];
int stride = (width * bitmap.Format.BitsPerPixel + 7) / 8;
bitmap.CopyPixels(pixels, stride, 0);
bitmap.Lock();
int dx = System.Math.Abs(x1-x0);
int dy = System.Math.Abs(y1-y0);
int sx = (x0 < x1) ? 1 : -1;
int sy = (y0 < y1) ? 1 : -1;
int err = dx - dy;
while(true)
{
// System.Console.WriteLine("x:{0}y:{1}", x0, y0);
int i = (x0 * 4) + (y0 * (width * 4));
pixels[i+0] = (byte)c.B;
pixels[i+1] = (byte)c.G;
pixels[i+2] = (byte)c.R;
pixels[i+3] = (byte)c.A;
if ((x0 == x1) && (y0 == y1)) break;
int e2 = 2 * err;
if (e2 > dy)
{
err = err - dy;
x0 = x0 + sx;
}
if (e2 < dx)
{
err = err + dx;
y0 = y0 + sy;
}
}
bitmap.WritePixels(new Int32Rect(0, 0, width, height), pixels, stride, 0, 0);
bitmap.Unlock();
}
static Color GetPixel(ref byte[] pixels, int width, int height, int x, int y)
{
Color c = new Color();
int i = (x * 4) + (y * (width * 4));
c.B = pixels[i+0];
c.G = pixels[i+1];
c.R = pixels[i+2];
c.A = pixels[i+3];
return c;
}
static void SetPixel(ref byte[] pixels, int width, int height, int x, int y, Color c)
{
int i = (x * 4) + (y * (width * 4));
pixels[i+0] = c.B;
pixels[i+1] = c.G;
pixels[i+2] = c.R;
pixels[i+3] = c.A;
}
static void Paint(ref WriteableBitmap bitmap, int startX, int startY, Color c)
{
int width = (int)bitmap.PixelWidth;
int height = (int)bitmap.PixelHeight;
int pixelsSize = (width * 4) * height;
byte[] pixels = new byte[pixelsSize];
int stride = (width * bitmap.Format.BitsPerPixel + 7) / 8;
bitmap.CopyPixels(pixels, stride, 0);
List array = new List();
array.Add(new Point((double)startX, (double)startY));
int arrayIndex = 0;
int x = startX;
int y = startY;
Color baseColor = GetPixel(ref pixels, width, height, x, y);
//Debug.WriteLine("{0} {1} {2}", baseColor, x, y);
while(true)
{
// 上
if (y > 0 && baseColor == GetPixel(ref pixels, width, height, x, y-1))
{
var p = new Point(x, y-1);
if (-1 == array.IndexOf(p)) array.Add(p);
}
// 右
if (x < width-1 && baseColor == GetPixel(ref pixels, width, height, x+1, y))
{
var p = new Point(x+1, y);
if (-1 == array.IndexOf(p)) array.Add(p);
}
// 下
if (y < height-1 && baseColor == GetPixel(ref pixels, width, height, x, y+1))
{
var p = new Point(x, y+1);
if (-1 == array.IndexOf(p)) array.Add(p);
}
// 左
if (x > 0 && baseColor == GetPixel(ref pixels, width, height, x-1, y))
{
var p = new Point(x-1, y);
if (-1 == array.IndexOf(p)) array.Add(p);
}
arrayIndex = arrayIndex + 1;
if (arrayIndex >= array.Count) break;
x = (int)array[arrayIndex].X;
y = (int)array[arrayIndex].Y;
}
foreach(var p in array)
{
x = (int)p.X;
y = (int)p.Y;
SetPixel(ref pixels, width, height, x, y, c);
}
bitmap.Lock();
bitmap.WritePixels(new Int32Rect(0, 0, width, height), pixels, stride, 0, 0);
bitmap.Unlock();
}
static void Paint2(ref WriteableBitmap bitmap, int startX, int startY, Color c)
{
int width = (int)bitmap.PixelWidth;
int height = (int)bitmap.PixelHeight;
int pixelsSize = (width * 4) * height;
byte[] pixels = new byte[pixelsSize];
int stride = (width * bitmap.Format.BitsPerPixel + 7) / 8;
bitmap.CopyPixels(pixels, stride, 0);
List array = new List();
Dictionary dic = new Dictionary();
var sp = new Point((double)startX, (double)startY);
array.Add(sp);
int arrayIndex = 0;
dic.Add(sp, arrayIndex);
int x = startX;
int y = startY;
Color baseColor = GetPixel(ref pixels, width, height, x, y);
//Debug.WriteLine("{0} {1} {2}", baseColor, x, y);
while(true)
{
// 上
if (y > 0 && baseColor == GetPixel(ref pixels, width, height, x, y-1))
{
var p = new Point(x, y-1);
if (!dic.ContainsKey(p))
{
array.Add(p);
dic.Add(p, arrayIndex);
}
}
// 右
if (x < width-1 && baseColor == GetPixel(ref pixels, width, height, x+1, y))
{
var p = new Point(x+1, y);
if (!dic.ContainsKey(p))
{
array.Add(p);
dic.Add(p, arrayIndex);
}
}
// 下
if (y < height-1 && baseColor == GetPixel(ref pixels, width, height, x, y+1))
{
var p = new Point(x, y+1);
if (!dic.ContainsKey(p))
{
array.Add(p);
dic.Add(p, arrayIndex);
}
}
// 左
if (x > 0 && baseColor == GetPixel(ref pixels, width, height, x-1, y))
{
var p = new Point(x-1, y);
if (!dic.ContainsKey(p))
{
array.Add(p);
dic.Add(p, arrayIndex);
}
}
arrayIndex = arrayIndex + 1;
if (arrayIndex >= array.Count) break;
x = (int)array[arrayIndex].X;
y = (int)array[arrayIndex].Y;
}
foreach(var p in array)
{
x = (int)p.X;
y = (int)p.Y;
SetPixel(ref pixels, width, height, x, y, c);
}
bitmap.Lock();
bitmap.WritePixels(new Int32Rect(0, 0, width, height), pixels, stride, 0, 0);
bitmap.Unlock();
}
static void Paint3(ref WriteableBitmap bitmap, int startX, int startY, Color c)
{
int width = (int)bitmap.PixelWidth;
int height = (int)bitmap.PixelHeight;
int pixelsSize = (width * 4) * height;
byte[] pixels = new byte[pixelsSize];
int stride = (width * bitmap.Format.BitsPerPixel + 7) / 8;
bitmap.CopyPixels(pixels, stride, 0);
Stack array = new Stack();
//Dictionary dic = new Dictionary();
var sp = new Point((double)startX, (double)startY);
array.Push(sp);
//dic.Add(sp, 0);
int x = startX;
int y = startY;
Color baseColor = GetPixel(ref pixels, width, height, x, y);
//Debug.WriteLine("{0} {1} {2}", baseColor, x, y);
int[,] xxx = new int [width, height];
while(true)
{
var ss = array.Pop();
x = (int)ss.X;
y = (int)ss.Y;
// 上
if (y > 0 && baseColor == GetPixel(ref pixels, width, height, x, y-1))
{
var p = new Point(x, y-1);
if (xxx[x, y-1] == 0)
{
array.Push(p);
xxx[x, y-1] = 1;
}
}
// 右
if (x < width-1 && baseColor == GetPixel(ref pixels, width, height, x+1, y))
{
var p = new Point(x+1, y);
if (xxx[x+1, y] == 0)
{
array.Push(p);
xxx[x+1, y] = 1;
}
}
// 下
if (y < height-1 && baseColor == GetPixel(ref pixels, width, height, x, y+1))
{
var p = new Point(x, y+1);
if (xxx[x, y+1] == 0)
{
array.Push(p);
xxx[x, y+1] = 1;
}
}
// 左
if (x > 0 && baseColor == GetPixel(ref pixels, width, height, x-1, y))
{
var p = new Point(x-1, y);
if (xxx[x-1, y] == 0)
{
array.Push(p);
xxx[x-1, y] = 1;
}
}
if (array.Count == 0) break;
}
foreach(var p in array)
{
x = (int)p.X;
y = (int)p.Y;
SetPixel(ref pixels, width, height, x, y, c);
}
bitmap.Lock();
bitmap.WritePixels(new Int32Rect(0, 0, width, height), pixels, stride, 0, 0);
bitmap.Unlock();
}
public MainWindow()
{
InitializeComponent();
const int width = 256;
const int height = 256;
var wb = new WriteableBitmap(width, height, 75, 75, PixelFormats.Bgra32, null);
DrawLine(ref wb, 10, 10, 10, 246, Color.FromArgb(255, 0, 0, 0));
DrawLine(ref wb, 10, 246, 246, 246, Color.FromArgb(255, 0, 0, 0));
DrawLine(ref wb, 246, 246, 10, 10, Color.FromArgb(255, 0, 0, 0));
DrawLine(ref wb, 246, 246, 246, 10, Color.FromArgb(255, 0, 0, 0));
DrawLine(ref wb, 10, 10, 246, 10, Color.FromArgb(255, 0, 0, 0));
var sw = new System.Diagnostics.Stopwatch();
sw.Start();
Paint3(ref wb, 100, 32, Color.FromArgb(255, 0, 127, 255));
sw.Stop();
Debug.WriteLine($"Paint3:{sw.ElapsedMilliseconds}ミリ秒");
sw.Restart();
Paint2(ref wb, 100, 32, Color.FromArgb(255, 127, 255, 0));
sw.Stop();
Debug.WriteLine($"Paint2:{sw.ElapsedMilliseconds}ミリ秒");
image1.Source = wb;
}
}
} ビルド
dotnet build実行
dotnet run結果
2次元配列(Paint3())…16ミリ秒
Dictionary<T>(Paint2())…90ミリ秒
※Intel Celeron 3965U @ 2.2GHzで実行
実行時間を計測したところ大分時間が短縮されました。
コメント