C#任意图形加权Voronoi图生成(AE环境下，栅格光栅扫描算法)
距离变换是计算并标识空间点（对目标点）距离的过程，它最终把二值图像变换为灰度图像[1]（其中每个栅格的灰度值等于它到最近目标点的距离）。目前距离变换被广泛应用于计算机图形学、GIS空间分析和模式识别等领域。
按距离类型划分，距离变换可分为：非欧氏距离变换和欧氏距离变换（EDT）。其中EDT精度高，与实际距离相符，应用更广泛。目前随着应用的需要，已经有多种EDT算法[2-6]。按变换方式分，这些算法可以分为：基于目标点变换算法[2,3]和基于背景点变换算法[4-6]，其中基于目标点变换算法又可分为：传播算法[4]、光栅扫描算法[5]和独立扫描算法[6]。上述算法大多致力于算法效率和完全性上的研究，其算法扩展性十分有限。
为此，作者提出了一种新的EDT算法，该算法在原有光栅扫描算法基础上，进行了改进，算法在信息传递的时候，用最近目标点的行列号代替与最近目标点行列号的差异，这样通过这些行列号可以轻松实现欧氏距离变换。和原有算法相比，该算法扩展后可以用于加权欧氏距离变换、任意图形加权Voronoi图的生成。以下为实现代码：
一、IVoronoiClass.cs文件，DLL文件一
using System;
using System.Collections.Generic;using System.Text;
using System.Collections;
[assembly: CLSCompliant(true)]
namespace Voronoi
{
public class VoronoiClass : IVoronoiClass
{
private struct RC
{
public int i;
public int j;
}
private class Mark
{
private int o_x;
public int O_x
{
get { return o_x; }
set { o_x = value; }
}
private int o_y;
public int O_y
{
get { return o_y; }
set { o_y = value; }
}
private double weight;
public double Weight
{
get { return weight; }
set { weight = value; }
}
private double o_num;
public double O_num
{
get { return o_num; }
set { o_num = value; }
}
}
private class Recode
{
private int o_x;
public int O_x
{
get { return o_x; }
set { o_x = value; }
}
private int o_y;
public int O_y
{
get { return o_y; }
set { o_y = value; }
}
private double o_num;
public double O_num
{
get { return o_num; }
set { o_num = value; }
}
private double weight;
public double Weight
{
get { return weight; }
set { weight = value; }
}
private double distance;
public double Distance
{
get { return distance; }
set { distance = value; }
}
}
//公共变量
Mark[,] T;
int max = 10000000;
Array IVoronoiClass.doVoronoi(Array pixelData, int W, int H)
{
T = new Mark[W + 2, H + 2];//加个框框
Array ResultData;
///////////////////////////////预处理
for (int i = 0; i < W + 2; i++)
for (int j = 0; j < H + 2; j++)
{
T[i, j] = new Mark();
double weight;
try
{
weight = Convert.ToDouble(pixelData.GetValue(i - 1, j - 1));
}
catch (Exception ex)
{
weight = 0;
string a = ex.Message;//日魂归
}
if (weight > 0)//目标
{
T[i, j].O_x = i;
T[i, j].O_y = j;
T[i, j].Weight = weight;
T[i, j].O_num = 0;
}
else//背景
{
T[i, j].O_x = max;
T[i, j].O_y = max;
T[i, j].Weight = 1.1;
T[i, j].O_num = 0;
}
}
double num = 1;
for (int i = 0; i < W + 2; i++)
for (int j = 0; j < H + 2; j++)
{
if (T[i, j].Weight != 1.1 && T[i, j].O_num == 0)
{
T[i, j].O_num = num;
Stack process = new Stack();
FindPolygon(process, i, j,W,H);
while (process.Count > 0)
{
RC rc = (RC)process.Pop();
FindPolygon(process, rc.i, rc.j,W,H);
}
GC.Collect();
num++;
}
}
//////////////////////////////上行扫描
Recode[] recode = new Recode[9];
for (int i = 1; i < W + 1; i++)
for (int j = 1; j < H + 1; j++)
{
recode[1] = new Recode();
recode[1].Distance = Math.Sqrt(Math.Pow(i - T[i, j - 1].O_x, 2) + Math.Pow(j - T[i, j - 1].O_y, 2)) / T[i, j - 1].Weight;
recode[1].O_x = T[i, j - 1].O_x;
recode[1].O_y = T[i, j - 1].O_y;
recode[1].O_num = T[i, j - 1].O_num;
recode[1].Weight = T[i, j - 1].Weight;
recode[2] = new Recode();
recode[2].Distance = Math.Sqrt(Math.Pow(i - T[i - 1, j - 1].O_x, 2) + Math.Pow(j - T[i - 1, j - 1].O_y, 2)) / T[i - 1, j - 1].Weight;
recode[2].O_x = T[i - 1, j - 1].O_x;
recode[2].O_y = T[i - 1, j - 1].O_y;
recode[2].O_num = T[i - 1, j - 1].O_num;
recode[2].Weight = T[i - 1, j - 1].Weight;
recode[3] = new Recode();
recode[3].Distance = Math.Sqrt(Math.Pow(i - T[i - 1, j].O_x, 2) + Math.Pow(j - T[i - 1, j].O_y, 2)) / T[i - 1, j].Weight;
recode[3].O_x = T[i - 1, j].O_x;
recode[3].O_y = T[i - 1, j].O_y;
recode[3].O_num = T[i - 1, j].O_num;
recode[3].Weight = T[i - 1, j].Weight;
recode[4] = new Recode();
{
recode[4].Distance = Math.Sqrt(Math.Pow(i - T[i - 1, j + 1].O_x, 2) + Math.Pow(j - T[i - 1, j + 1].O_y, 2)) / T[i - 1, j + 1].Weight;
recode[4].O_x = T[i - 1, j + 1].O_x;
recode[4].O_y = T[i - 1, j + 1].O_y;
recode[4].O_num = T[i - 1, j + 1].O_num;
recode[4].Weight = T[i - 1, j + 1].Weight;
}
for (int k = 1; k < 5; k++)
{
double distance = Math.Sqrt(Math.Pow(i - T[i, j].O_x, 2) + Math.Pow(j - T[i, j].O_y, 2)) / T[i, j].Weight;
if (recode[k].Distance < distance)
{
T[i, j].O_x = recode[k].O_x;
T[i, j].O_y = recode[k].O_y;
T[i, j].O_num = recode[k].O_num;
T[i, j].Weight = recode[k].Weight;
}
}
}
//////////////////////上行扫描结束
///////////////////////下行扫描
for (int i = W; i > 0; i--)
for (int j = H; j > 0; j--)
{
recode[5] = new Recode();
recode[5].Distance = Math.Sqrt(Math.Pow(i - T[i, j + 1].O_x, 2) + Math.Pow(j - T[i, j + 1].O_y, 2)) / T[i, j + 1].Weight;
recode[5].O_x = T[i, j + 1].O_x;
recode[5].O_y = T[i, j + 1].O_y;
recode[5].O_num = T[i, j + 1].O_num;
recode[5].Weight = T[i, j + 1].Weight;
recode[6] = new Recode();
recode[6].Distance = Math.Sqrt(Math.Pow(i - T[i + 1, j + 1].O_x, 2) + Math.Pow(j - T[i + 1, j + 1].O_y, 2)) / T[i + 1, j + 1].Weight;
recode[6].O_x = T[i + 1, j + 1].O_x;
recode[6].O_y = T[i + 1, j + 1].O_y;
recode[6].O_num = T[i + 1, j + 1].O_num;
recode[6].Weight = T[i + 1, j + 1].Weight;
recode[7] = new Recode();
recode[7].Distance = Math.Sqrt(Math.Pow(i - T[i + 1, j].O_x, 2) + Math.Pow(j - T[i + 1, j].O_y, 2)) / T[i + 1, j].Weight;
recode[7].O_x = T[i + 1, j].O_x;
recode[7].O_y = T[i + 1, j].O_y;
recode[7].O_num = T[i + 1, j].O_num;
recode[7].Weight = T[i + 1, j].Weight;
recode[8] = new Recode();
{
recode[8].Distance = Math.Sqrt(Math.Pow(i - T[i + 1, j - 1].O_x, 2) + Math.Pow(j - T[i + 1, j - 1].O_y, 2)) / T[i + 1, j - 1].Weight;
recode[8].O_x = T[i + 1, j - 1].O_x;
recode[8].O_y = T[i + 1, j - 1].O_y;
recode[8].O_num = T[i + 1, j - 1].O_num;
recode[8].Weight = T[i + 1, j - 1].Weight;
}
for (int k = 5; k < 9; k++)
{
double distance = Math.Sqrt(Math.Pow(i - T[i, j].O_x, 2) + Math.Pow(j - T[i, j].O_y, 2)) / T[i, j].Weight;
if (recode[k].Distance < distance)
{
T[i, j].O_x = recode[k].O_x;
T[i, j].O_y = recode[k].O_y;
T[i, j].O_num = recode[k].O_num;
T[i, j].Weight = recode[k].Weight;
}
}
}
///////////////////下行扫描结束
ResultData = Array.CreateInstance(typeof(Byte), W, H);
for (int i = 1; i < W + 1; i++)
for (int j = 1; j < H + 1; j++)
{
ResultData.SetValue(Convert.ToByte(T[i, j].O_num), i - 1, j - 1);
}
return ResultData;
}
private void digui(int i, int j,int W,int H){
#region
#endregion
if (i > 1)
{
if (T[i - 1, j].Weight != 1.1 && T[i - 1, j].O_num == 0)
{
T[i - 1, j].O_num = T[i, j].O_num;
digui(i - 1, j,W,H);
}
}
if (i > 1 && j > 1)
{
if (T[i - 1, j - 1].Weight != 1.1 && T[i - 1, j - 1].O_num == 0)
{
T[i - 1, j - 1].O_num = T[i, j].O_num;
digui(i - 1, j - 1,W,H);
}
}
if (j > 1)
{
if (T[i, j - 1].Weight != 1.1 && T[i, j - 1].O_num == 0)
{
T[i, j - 1].O_num = T[i, j].O_num;
digui(i, j - 1,W,H);
}
}
if (i < W && j > 0)
{
if (T[i + 1, j - 1].Weight != 1.1 && T[i + 1, j - 1].O_num == 0)
{
T[i + 1, j - 1].O_num = T[i, j].O_num;
digui(i + 1, j - 1,W,H);
}
}
if (i < W)
{
if (T[i + 1, j].Weight != 1.1 && T[i + 1, j].O_num == 0)
{
T[i + 1, j].O_num = T[i, j].O_num;
digui(i + 1, j,W,H);
}
}
if (i < W && j < H)
{
if (T[i + 1, j + 1].Weight != 1.1 && T[i + 1, j + 1].O_num == 0)
{
T[i + 1, j + 1].O_num = T[i, j].O_num;
digui(i + 1, j + 1,W,H);
}
}
if (j < H)
{
if (T[i, j + 1].Weight != 1.1 && T[i, j + 1].O_num == 0)
{
T[i, j + 1].O_num = T[i, j].O_num;
digui(i, j + 1,W,H);
}
}
if (i > 1 && j < H)
{
if (T[i - 1, j + 1].Weight != 1.1 && T[i - 1, j + 1].O_num == 0)
{
T[i - 1, j + 1].O_num = T[i, j].O_num;
digui(i - 1, j + 1,W,H);
}
}
GC.Collect();
}
private void FindPolygon(Stack process, int i, int j,int W,int H)
{
if (i > 1)
{
if (T[i - 1, j].Weight != 1.1 && T[i - 1, j].O_num == 0)
{
T[i - 1, j].O_num = T[i, j].O_num;
AddValue(process, i - 1, j);
}
}
if (i > 1 && j > 1)
{
if (T[i - 1, j - 1].Weight != 1.1 && T[i - 1, j - 1].O_num == 0)
{
T[i - 1, j - 1].O_num = T[i, j].O_num;
AddValue(process, i - 1, j - 1);
}
}
if (j > 1)
{
if (T[i, j - 1].Weight != 1.1 && T[i, j - 1].O_num == 0)
{
T[i, j - 1].O_num = T[i, j].O_num;
AddValue(process, i, j - 1);
}
}
if (i < W && j > 0)
{
if (T[i + 1, j - 1].Weight != 1.1 && T[i + 1, j - 1].O_num == 0)
{
T[i + 1, j - 1].O_num = T[i, j].O_num;
AddValue(process, i + 1, j - 1);
}
}
if (i < W)
{
if (T[i + 1, j].Weight != 1.1 && T[i + 1, j].O_num == 0)
{
T[i + 1, j].O_num = T[i, j].O_num;
AddValue(process, i + 1, j);
}
}
if (i < W && j < H)
{
if (T[i + 1, j + 1].Weight != 1.1 && T[i + 1, j + 1].O_num == 0)
{
T[i + 1, j + 1].O_num = T[i, j].O_num;
AddValue(process, i + 1, j + 1);
}
}
if (j < H)
{
if (T[i, j + 1].Weight != 1.1 && T[i, j + 1].O_num == 0)
{
T[i, j + 1].O_num = T[i, j].O_num;
AddValue(process, i, j + 1);
}
}
if (i > 1 && j < H)
{
if (T[i - 1, j + 1].Weight != 1.1 && T[i - 1, j + 1].O_num == 0)
{
T[i - 1, j + 1].O_num = T[i, j].O_num;
AddValue(process, i - 1, j + 1);
}
}
}
private void AddValue(Stack process, int i, int j)
{
{
RC rc = new RC();
rc.i = i;
rc.j = j;
process.Push(rc);
}
}
}
}
二、IVoronoiClass.cs文件,DLL文件二，实现接口
using System;
namespace Voronoi
{
public interface IVoronoiClass
{
Array doVoronoi(Array pixelData, int W, int H);
}
}
三、执行文件（AE下实现）
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Threading;
using System.IO;
using System.Collections;
namespace GLCStatisticalAnalysis
{
public partial class BuiltVoronoiFrom : Form
{
public BuiltVoronoiFrom()
{
InitializeComponent();
worker.WorkerReportsProgress = true;
worker.WorkerSupportsCancellation = true;
//正式做事情的地方
worker.DoWork += new DoWorkEventHandler(DoWork);
//任务完称时要做的，比如提示等等
worker.ProgressChanged += new ProgressChangedEventHandler(ProgessChanged);
//任务进行时，报告进度
worker.RunWorkerCompleted += new RunWorkerCompletedEventHandler(CompleteWork);
}
Thread mainThread;
public BackgroundWorker worker = new BackgroundWorker();
bool progress = true; //进度条控制参
VoronoiProcess pProcess = new VoronoiProcess();
string classField;
string cellSize;
private void OK_Click(object sender, EventArgs e)
{
bool start = checkFilePath();
if (start)
{
classField = comboBox1.Text;
cellSize = textBox2.Text;
mainThread = new Thread(mainThreadProcess);
mainThread.SetApartmentState(ApartmentState.STA);
mainThread.Start();
worker.RunWorkerAsync();//进度条控制
this.panel_hidden.Enabled = false;
OK.Enabled = false;
}
}
private bool checkFilePath()
{
bool start = true;
if (textBox1.Text == "")
{ MessageBox.Show("请输入要素文件!"); start = false; return start; }
else if (textBox2.Text == "")
{ MessageBox.Show("请输入影像文件!"); start = false; return start; }
else if (comboBox1.Text == "")
{ MessageBox.Show("请输入权重字段!"); start = false; return start; }
else if (textBox2.Text == "")
{ MessageBox.Show("请输入精度!"); start = false; return start; }
else if (!File.Exists(textBox1.Text))
{ MessageBox.Show("要素文件不存在!"); start = false; return start; }
else if (File.Exists(textBox3.Text))
{
try { System.IO.File.Delete(textBox3.Text); }
catch (Exception ex)
{
start = false;
MessageBox.Show(ex.Message);
return start;
}
}
else
{
//检验输出路径是否存在
string outPath = textBox3.Text;
int index = outPath.LastIndexOf("\\");
if ((index == -1) || (index >= outPath.Length - 1))
{
MessageBox.Show("输出文件路径有误！");
start = false;
return start;
}
else
{
string outFilePath = outPath.Remove(index);
if (!(Directory.Exists(outFilePath)))
{
MessageBox.Show("输出文件路径有误！");
start = false;
return start;
}
}
}
return start;
}
private void Cancel_Click(object sender, EventArgs e)
{
progress = false;
this.Close();
}
private void pictureBox1_Click(object sender, EventArgs e)
{
openFileDialog1.FileName = null;//清楚文件路径，防止再次导入时，取消后依然导入
openFileDialog1.Filter = "Shapefile(*.shp)|*.shp";
openFileDialog1.ShowDialog();
this.textBox1.Text=openFileDialog1.FileName;
if (textBox1.Text != "")
{
AddComboBox1();
this.textBox3.Text = this.textBox1.Text.Replace(".shp", "_voronoi.shp");
}
}
[STAThread]
private void mainThreadProcess()
{
//try
{
pProcess.run(textBox1.Text, textBox3.Text, classField, cellSize);
}
//catch (Exception ex)
//{
// MessageBox.Show(ex.Message);
//}
}
#region 进度条
public void DoWork(object sender, DoWorkEventArgs e)
{
e.Result = ComputeFibonacci(worker, e);//当ComputeFibonacci(worker, e)返回时，异步过程结束
}
//调用 ReportProgress 时发生
public void ProgessChanged(object sender, ProgressChangedEventArgs e)
{
this.toolStripProgressBar1.Value = e.ProgressPercentage;
this.toolStripStatusLabel2.Text = Convert.ToString(e.ProgressPercentage);
}
//当后台操作已完成、被取消或引发异常时发生
public void CompleteWork(object sender, RunWorkerCompletedEventArgs e)
{
MessageBox.Show("Complete！");
this.Close();
}
private int ComputeFibonacci(object sender, DoWorkEventArgs e)
{
int i = 0;
while (mainThread.IsAlive)
{
if (progress == false)
{
MessageBox.Show("Cancelled！");
mainThread.Abort();//叫停处理图像进程
System.Threading.Thread.CurrentThread.Abort();
}
if (worker.CancellationPending)
{
e.Cancel = true;
}
else
{
worker.ReportProgress(i);
}
System.Threading.Thread.Sleep(300);
i++; if (i == 100) i = 0;
}
worker.ReportProgress(100);
return -1;
}
#endregion
private void CalculateStatisticsFrom_FormClosed(object sender, FormClosedEventArgs e)
{
progress = false;
}
private void AddComboBox1()
{
comboBox1.Items.Clear();
ArrayList pValue = new ArrayList();
pValue = pProcess.getZoneField(textBox1.Text);
for (int i = 0; i < pValue.Count; i++)
{
comboBox1.Items.Add(pValue[i]);
}
comboBox1.Text = Convert.ToString(comboBox1.Items[3]);
}
private void pictureBox3_Click(object sender, EventArgs e)
{
saveFileDialog1.FileName = null;//清楚文件路径，防止再次导入时，取消后依然导入
saveFileDialog1.Filter = "Shapefile(*.shp)|*.shp";
saveFileDialog1.ShowDialog();
this.textBox3.Text = saveFileDialog1.FileName;
}
}
}