指定した座標の色を取得し、その座標の左右上下の座標の色と比較し同じであれば、塗りつぶし座標の配列にスタックします。
その後、配列にスタックした座標を指定色でセットします。
その後、配列にスタックした座標を指定色でセットします。
プロジェクトの作成
PowerShellで実行。要dotnet.exe
mkdir SamplePaint
cd SamplePaint
dotnet new wpf
code .ソースコード
<Window x:Class="SamplePaint.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:SamplePaint"
mc:Ignorable="d"
Title="MainWindow" Height="450" Width="800">
<Grid>
<Image x:Name="image1" Stretch="None" />
</Grid>
</Window>using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;
using System.Diagnostics;
namespace SamplePaint
{
/// <summary>
/// Interaction logic for MainWindow.xaml
/// </summary>
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<Point> array = new List<Point>();
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<Point> array = new List<Point>();
Dictionary<Point, int> dic = new Dictionary<Point, int>();
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();
}
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();
Paint(ref wb, 100, 32, Color.FromArgb(255, 0, 127, 255));
sw.Stop();
Debug.WriteLine($"Paint:{sw.ElapsedMilliseconds}ミリ秒");
sw.Restart();
Paint2(ref wb, 32, 100, Color.FromArgb(255, 127, 255, 0));
sw.Stop();
Debug.WriteLine($"Paint2:{sw.ElapsedMilliseconds}ミリ秒");
image1.Source = wb;
}
}
}
ビルド
dotnet build実行
dotnet run黒い線で三角形を２つ用意し、その内部を塗りつぶしています。
塗りつぶしメソッドをPaint()とPaint2()の２パターンを試したところPaint2()が速く動作するようです。
とりあえずこのサンプルでは、作成者の意図したとおり塗りつぶしが行われいますが、あまりテストしていないので致命的な間違いがあるかもしれません。
塗潰しのアルゴリズムを探してみたところ、関数内で自分自身を呼び出す再帰関数を使った物が見つかりました。
C#でサンプルプログラムを作ったところ、画像のサイズが小さい場合は問題なく動作しましたが、画像サイズが大きくなるとスタックがどうのというエラーが発生しました。
仕方が無いので、再帰関数の代わりにList<Point>に見つかった座標をスタックするする方法にしたのがPaint()メソッドになります。
ただ、Paint()では既に確認済みの座標を排除するため.indexOf()を使っているのですが、こちらに時間が掛かるらしく、少し大きな面積を塗りつぶすと体感できるほど塗りつぶしに時間を要することに成りました。
実用的な速度まで改善するため考えてみましたが、余り良い方法は思いつかず、大分強引ですが、Dictionary<Point,int>のキーにたいする.ContainsKey()で重複座標の排除を行うようしたバージョンがPaint2になります。速度は結構改善しましたが、ListとDictionaryで同じデータを持たせることになっており、特にDictionaryのValueは使われることが無いのでメモリの無駄遣い感が大きいです。
C#でサンプルプログラムを作ったところ、画像のサイズが小さい場合は問題なく動作しましたが、画像サイズが大きくなるとスタックがどうのというエラーが発生しました。
仕方が無いので、再帰関数の代わりにList<Point>に見つかった座標をスタックするする方法にしたのがPaint()メソッドになります。
ただ、Paint()では既に確認済みの座標を排除するため.indexOf()を使っているのですが、こちらに時間が掛かるらしく、少し大きな面積を塗りつぶすと体感できるほど塗りつぶしに時間を要することに成りました。
実用的な速度まで改善するため考えてみましたが、余り良い方法は思いつかず、大分強引ですが、Dictionary<Point,int>のキーにたいする.ContainsKey()で重複座標の排除を行うようしたバージョンがPaint2になります。速度は結構改善しましたが、ListとDictionaryで同じデータを持たせることになっており、特にDictionaryのValueは使われることが無いのでメモリの無駄遣い感が大きいです。
コメント