using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading.Tasks;
using System.Windows.Forms;
using System.Collections;
namespace CourceWork
{
public partial class Form1 : Form
{
int[] gdx = new int[] {1, 0, -1, 0, 1, 1, -1, -1 };
int[] gdy = new int[] {0, 1, 0, -1, 1,-1, 1, -1 };
Image mainImage;
Bitmap currBitmap;
bool[,] matrix;
Graphics drawContext;
StreamWriter outstr = new StreamWriter("matrix.txt");
StreamReader instr = new StreamReader("input.txt");
Bitmap secondViewport;
public Form1()
{
InitializeComponent();
mainImage = Image.FromFile("test5.jpg");
mainView.Image = mainImage;
currBitmap = new Bitmap(mainImage);
secondViewport = new Bitmap(2000, 2000);
drawContext = Graphics.FromImage(secondViewport);
simplyBinarize();
matrix = new bool[currBitmap.Size.Height, currBitmap.Size.Width];
buildBorders();
dfsStarter();
buildBSpline();
for (int i = 0; i < matrix.GetLength(0); ++i)
{
for (int j = 0; j < matrix.GetLength(1); ++j)
{
if (matrix[i, j] == true)
{
outstr.Write("1");
}
else
outstr.Write("0");
}
outstr.WriteLine();
}
mainView.Image = currBitmap;
pictureBox1.Image = secondViewport;
}
int startX = 0;
int startY = 0;
int collectedPixels = 0;
int shortesPathDist = 0;
List<pix> shortestBorder = new List<pix>();
void filterMatrix()
{
for(int i = 1; i < matrix.GetLength(0) - 1; ++i)
for (int j = 1; j < matrix.GetLength(1) - 1; ++j)
{
if (matrix[i, j])
{
if (matrix[i + 1, j + 1] && matrix[i + 1, j]) matrix[i + 1, j] = false;
if (matrix[i + 1, j + 1] && matrix[i, j + 1]) matrix[i, j + 1] = false;
}
}
}
bool findShortestPath(int x, int y, int cnt)
{
if (Math.Abs(startX - x) <= 1 && Math.Abs(startY - y) <= 1 && cnt > 10)
{
return true;
}
shortestBorder.Add(new pix(x, y));
matrix[y, x] = false;
for(int i = 0; i < gdx.Length; ++i)
for (int j = 0; j < gdy.Length; ++j)
{
if (y + gdy[j] < 0 || x + gdx[i] < 0 || y + gdy[j] >= matrix.GetLength(0) || x + gdx[i] >= matrix.GetLength(1))
continue;
if (matrix[y + gdy[j], x + gdx[i]])
if (findShortestPath(x + gdx[i], y + gdy[j], cnt + 1))
return true;
}
shortestBorder.RemoveAt(shortestBorder.Count - 1);
matrix[y, x] = true; ;
return false;
}
double getAngle(pix a, pix b, pix c)
{
pix ac = new pix();
pix bc = new pix();
ac.x = a.x - c.x;
ac.y = a.y - c.y;
bc.x = b.x - c.x;
bc.y = b.y - c.y;
double angle = (ac.x * bc.x + ac.y * bc.y) / (Math.Sqrt(ac.x * ac.x + ac.y * ac.y) * Math.Sqrt(bc.x * bc.x + bc.y * bc.y));
return Math.Acos(angle);
}
double getDist(pix ai, pix bi, pix ci)
{
v2 a = new v2(ai.x, ai.y);
v2 b = new v2(bi.x, bi.y);
v2 c = new v2(ci.x, ci.y);
v2 ab = b - a;
v2 ac = c - a;
return Math.Abs(ab.cross(ac) / ac.norm());
}
double getAngle(v2 a, v2 b)
{
return Math.Acos( (a.x * b.x + a.y * b.y) / (a.norm() * b.norm()));
}
double getSquaredError(bpoint a, bpoint b)
{
int N = shortestBorder.Count;
double T_STEP = 0.01;
int ai = (a.indexInPathArr - 1 + N ) % N;
int bi = (b.indexInPathArr + 1) % N;
if (bi < ai) bi = N;
double retVal = 0;
for (double t = T_STEP; t < 1; t += T_STEP)
{
int ind = (int)(((double)bi - (double)ai) * t) + ai;
v2 pa = new v2(shortestBorder[ind].x, shortestBorder[ind].y);
v2 pb = getSplinePoint(t, a, b);
retVal += (pa - pb).squaredNorm();
}
return retVal;
}
void buildBSpline()
{
int L = 13;
int SL = L;
double ANGLE_THRETHOLD = 1.8;
int N = shortestBorder.Count;
List<bpoint> bezierControlPointArray = new List<bpoint>();
/// Build corner points
for (int i = 0; i < shortestBorder.Count; i += 1)
{
double angle = getDist(shortestBorder[(i + N - L) % N], shortestBorder[i], shortestBorder[(i + L) % N]);
if (angle > ANGLE_THRETHOLD)
{
shortestBorder[i].corner = true;
shortestBorder[i].cpower = angle;
}
}
//////////////////////
/// Filter corner points ///////////
/// ////////////////////////////////
int FILTER_COUNT = 6;
for (int i = 0; i < shortestBorder.Count; ++i)
{
if (shortestBorder[i].corner == false)
continue;
for (int fp = -FILTER_COUNT; fp <= FILTER_COUNT; ++fp)
{
if (fp == 0) continue;
int cmpInd = (i + N + fp) % N;
if (shortestBorder[cmpInd].corner && (shortestBorder[cmpInd].cpower < shortestBorder[i].cpower))
shortestBorder[cmpInd].corner = false;
}
}
for (int i = 0; i < shortestBorder.Count; ++i)
{
if (shortestBorder[i].corner == true)
{
//drawContext.DrawEllipse(new Pen(Color.Green), shortestBorder[i].x, shortestBorder[i].y, 3, 3);
bezierControlPointArray.Add(new bpoint(shortestBorder[i].x, shortestBorder[i].y, i));
}
}
/* Procceed control points */
int ITERATION_COUNT = 5;
int cpN = bezierControlPointArray.Count;
for (int i = 0; i < bezierControlPointArray.Count; ++i)
{
bpoint a = bezierControlPointArray[i];
bpoint b = bezierControlPointArray[ (i + 1) % cpN];
int ai = a.indexInPathArr;
int bi = b.indexInPathArr;
int ain = (ai + L ) % N;
int bin = (bi - L + N) % N;
double koeff1 = 0;
double koeff2 = 0;
double koeffApprStep = 0.001;
a.sx = (shortestBorder[ain].x - a.x) * koeff1 + a.x;
a.sy = (shortestBorder[ain].y - a.y) * koeff1 + a.y;
b.fx = (shortestBorder[bin].x - b.x) * koeff2 + b.x;
b.fy = (shortestBorder[bin].y - b.y) * koeff2 + b.y;
for (int iteration = 0; iteration < ITERATION_COUNT; ++iteration)
{
double error = getSquaredError(a, b);
while (true)
{
koeff1 += koeffApprStep;
a.sx = (shortestBorder[ain].x - a.x) * koeff1 + a.x;
a.sy = (shortestBorder[ain].y - a.y) * koeff1 + a.y;
double nerror = getSquaredError(a, b);
if (error < nerror)
{
koeff1 -= koeffApprStep;
a.sx = (shortestBorder[ain].x - a.x) * koeff1 + a.x;
a.sy = (shortestBorder[ain].y - a.y) * koeff1 + a.y;
break;
}
error = nerror;
}
error = getSquaredError(a, b);
while (true)
{
koeff2 += koeffApprStep;
b.fx = (shortestBorder[bin].x - b.x) * koeff2 + b.x;
b.fy = (shortestBorder[bin].y - b.y) * koeff2 + b.y;
double nerror = getSquaredError(a, b);
if (error < nerror)
{
koeff2 -= koeffApprStep;
b.fx = (shortestBorder[bin].x - b.x) * koeff2 + b.x;
b.fy = (shortestBorder[bin].y - b.y) * koeff2 + b.y;
break;
}
error = nerror;
}
}
a.drawBpoint(drawContext);
b.drawBpoint(drawContext);
drawSplineMain(a, b, drawContext);
}
}
float getRadialValue(int x, int y)
{
int[] dx = new int[] { 1, 0 };
int[] dy = new int[] { 0, 1 };
/*
*
* A
* B P C P -- our tested pixel
* D
*
* */
float centralPixel = currBitmap.GetPixel(x, y).GetBrightness();
float maxDiff = 0;
for (int i = 0; i < 2; ++i)
{
if (currBitmap.Size.Width > x + dx[i] && currBitmap.Size.Height > y + dy[i] && 0 <= x + dx[i] && 0 <= y + dy[i])
maxDiff = Math.Max(maxDiff, Math.Abs(currBitmap.GetPixel(x + dx[i], y + dy[i]).GetBrightness() - centralPixel));
}
return maxDiff;
}
void simplyBinarize()
{
for(int x = 0; x < currBitmap.Size.Width; ++x)
for (int y = 0; y < currBitmap.Height; ++y)
{
if (currBitmap.GetPixel(x, y).GetBrightness() > 0.5)
currBitmap.SetPixel(x, y, Color.FromArgb(255,255,255));
else
currBitmap.SetPixel(x, y, Color.FromArgb(0, 0, 0));
}
}
void buildBorders()
{
for(int x = 0; x < currBitmap.Size.Width; ++x)
for (int y = 0; y < currBitmap.Size.Height; ++y)
{
if (getRadialValue(x, y) > 0.5)
{
matrix[y, x] = true;
}
}
}
void dfsStarter()
{
bool started = false;
for(int x = 0; x < currBitmap.Size.Width && !started; ++x)
for (int y = 0; y < currBitmap.Size.Height && !started; ++y)
{
if (matrix[y,x] == true)
{
startX = x;
startY = y;
findShortestPath(x, y, 0);
started = true;
}
}
}
private void Form1_Load(object sender, EventArgs e)
{
}
public v2 getSplinePoint(double t, bpoint a, bpoint b)
{
double px = a.x * (1 - t) * (1 - t) * (1 - t) + (1 - t) * (1 - t) * t * a.sx * 3
+ (1 - t) * t * t * b.fx * 3 + t * t * t * b.x;
double py = a.y * (1 - t) * (1 - t) * (1 - t) + (1 - t) * (1 - t) * t * a.sy * 3
+ (1 - t) * t * t * b.fy * 3 + t * t * t * b.y;
return new v2(px, py);
}
public void drawSplineMain(bpoint a, bpoint b, Graphics e)
{
double step = 0.2;
for (double t = step; t <= 1; t += step)
drawRecursive(t - step, t, a, b, e);
}
public void drawRecursive(double t1, double t2, bpoint a, bpoint b, Graphics e)
{
v2 ap = getSplinePoint(t1, a, b);
v2 bp = getSplinePoint(t2, a, b);
v2 mp = getSplinePoint( (t1 + t2) / 2 , a, b);
double angle = getAngle(ap - mp, bp - mp);
if (angle > 3.11)
{
e.DrawLine(new Pen(Color.Red), (int)ap.x, (int)ap.y, (int)bp.x, (int)bp.y);
}
else
{
drawRecursive(t1, (t1 + t2) / 2, a, b, e);
drawRecursive( (t1 + t2) / 2, t2, a, b, e);
}
}
}
public class v2
{
public double x,y;
public v2(double _x, double _y)
{
x = _x;
y = _y;
}
static public v2 operator-(v2 a, v2 b)
{
return new v2(a.x - b.x, a.y - b.y);
}
public double norm()
{
return Math.Sqrt(x * x + y * y);
}
public double squaredNorm()
{
return x * x + y * y;
}
public double dot(v2 v)
{
return x * v.x + y * v.y;
}
public double cross(v2 v)
{
return x * v.y - y * v.x;
}
};
public class pix
{
public int x, y;
public int path;
public bool visited;
public bool corner;
public double cpower;
public pix()
{
x = 0;
y = 0;
path = 0;
visited = false;
corner = false;
cpower = 0;
}
public pix(int _x, int _y)
{
x = _x;
y = _y;
path = 0;
corner = false;
cpower = 0;
}
};
public class bpoint
{
public double x, y;
public double fx, fy, sx, sy;
public int indexInPathArr;
public bpoint()
{
x = 0;
y = 0;
fx = 0;
fy = 0;
sx = 0;
sy = 0;
indexInPathArr = 0;
}
public bpoint(float _x, float _y, int indx)
{
x = _x;
y = _y;
fx = x - 1;
fy = _y;
sx = x + 1;
sy = _y;
indexInPathArr = indx;
}
public void drawBpoint(Graphics context)
{
context.DrawEllipse(new Pen(new SolidBrush(Color.Red), 1), (int)x, (int)y, 3, 3);
context.DrawEllipse(new Pen(new SolidBrush(Color.Blue), 1), (int)fx, (int)fy, 3, 3);
context.DrawEllipse(new Pen(new SolidBrush(Color.Yellow), 1), (int)sx, (int)sy, 3, 3);
}
};
}