/// добавление уравнения

/// </summary>

public void Add(Equation eq)

{

//добавление уравнения в общий массив уравнений

num_eq++;

data.Add(eq);

//добавление номера уравнения в соответствующий список

int i;

for(i = 0;i<eq.Dimension()+1;i++)

if (eq[i] != 0)

((ArrayList)arrayOfNumbers[i]).Add(data.Count-1);

}

/// <summary>

/// тестовый метод для консольного вывода множества уравнений

/// </summary>

public void Output()

{

Console.WriteLine("Вывод множества уравнений");

Console.WriteLine("Всего уравнений = {0}",num_eq.ToString());

Console.WriteLine("Размерность уравений = {0}",(arrayOfNumbers.Count-1).ToString());

int count;

for(int i = 0;i<arrayOfNumbers.Count;i++)

{

Console.WriteLine("Уравнения содержащие ненулевой коэффициент при {0}-ой переменной",i+1);

count = ((ArrayList)arrayOfNumbers[i]).Count;

if ( count == 0 )

Console.WriteLine("Пусто");

else for(int j = 0;j<count;j++)

((Equation)data[((int)((ArrayList)arrayOfNumbers[i])[j])]).Output();

}

}

/// <summary>

/// добавление множества уравнений, уравнения должны быть одной размерности

/// </summary>

public void AddSOF(SetOfEquations sof)

{

foreach(Equation eq in sof.data)

this.Add(eq);

}

/// <summary>

/// возвращает общее число уравнений,работает некорректно!!!!

/// </summary>

public int Size()

{

return num_eq;

}

/// <summary>

/// возвращает количество типов уравнений

/// </summary>

public int Dimension()

{

return arrayOfNumbers.Count-1;

}

/// <summary>

/// возвращает множество уравнений, где коэффициент при i-ой переменной ненулевой;

/// </summary>

public SetOfEquations GetSOF(int ind)

{

SetOfEquations result = new SetOfEquations(arrayOfNumbers.Count);

foreach(int number in ((ArrayList)arrayOfNumbers[ind-1]))

result.Add( (Equation)data[number] );

return result;

}

/// <summary>

/// возвращает первое уравнение, где коэффициент при i-ой переменной ненулевой

/// </summary>

public Equation GetI(int i)

{

if ( (i > 0) && (i <= this.Dimension()+1) )

return (Equation)data[ (int)((ArrayList)arrayOfNumbers[i-1])[0] ];

else return new Equation(this.Dimension());

}

/// <summary>

/// возвращает номер первого уравнения, где коэффициент при i-ой переменной ненулевой

/// </summary>

public int GetNumberI(int i)

{

if ( (i > 0) && (i <= this.Dimension()+1) && (((ArrayList)arrayOfNumbers[i-1]).Count != 0) )

return (int)((ArrayList)arrayOfNumbers[i-1])[0];

else return -1;

}

/// <summary>

/// удаляет первое уравнение, где коэффициент при i-ой переменной ненулевой

/// </summary>

public void DeleteI(int i)

{

if ( (i > 0) && (i <= this.Dimension()+1) && (((ArrayList)arrayOfNumbers[i-1]).Count != 0) )

{

//data.RemoveAt( (int)((ArrayList)arrayOfNumbers[i-1])[0] );

((ArrayList)arrayOfNumbers[i-1]).RemoveAt(0);

num_eq--;

}

}

/// <summary>

/// количество уравнений во множестве

/// </summary>

private int num_eq;

/// <summary>

/// возвращает ураврение по его номеру

/// </summary>

public Equation GetEquationByNumber(int i)

{

if ( (i > -1) /*&& (i < num_eq)*/ )

return (Equation)data[i];

else return null;

}

}

}

Polygon.cs

using System;

using System.Collections;

namespace Diplom

{

public class Polygon : Diplom.GeomObj, IDraw, IChange, IOperations

{

public enum round {CLOCKWISE,COUNTER_CLOCKWISE,UNDEFINE};

public Polygon()

{

points = new ArrayList();

pole = new Point();

pole.X = 0;

pole.Y = 0;

}

void IDraw.Draw()

{

Console.WriteLine("Drawings polygon");

foreach(Point p in points)

((IDraw)p).Draw();

}

//methods IChange interface

void IChange.Add(GeomObj data)

{

points.Add(data);

}

void IChange.SetI(GeomObj data, int ind)

{

if (ind < points.Count)

points[ind] = data;

}

void IChange.DeleteI(int ind)

{

if (ind < points.Count)

points.RemoveAt(ind);

}

void IChange.Insert(GeomObj data,int ind)

{

if (ind < points.Count)

points.Insert(ind,data);

}

//methods IOperations interface

void IOperations.Shift(Point to)

{

foreach(Point p in points)

((IOperations)p).Shift(to);

}

void IOperations.Rotate(Point center,double angel)

{

foreach(Point p in points)

((IOperations)p).Rotate(center,angel);

}

//collection of points

public ArrayList points;

/// <summary>

/// количество точек

/// </summary>

public int NumPoints

{

get

{

return points.Count;

}

}

/// <summary>

/// получение i-ой точки

/// </summary>

public Point GetI(int ind)

{

if (ind < points.Count)

return ((Point)points[ind]);

else return null;

}

/// <summary>

/// полюс

/// </summary>

private Point pole;

/// <summary>

/// свойство - полюс многоугольника

/// </summary>

public Point Pole

{

get

{

return pole;

}

set

{

pole = value;

}

}

/// <summary>

/// определяет направление обхода вершин

/// </summary>

public round Round()

{

if (this.NumPoints < 3) return round.UNDEFINE;

else

{

//центр масс

Point middle = new Point();

middle.X = (((Point)points[0]).X+((Point)points[1]).X+((Point)points[2]).X)/3.0;

middle.Y = (((Point)points[0]).Y+((Point)points[1]).Y+((Point)points[2]).Y)/3.0;

Point p1 = new Point();

Point p2 = new Point();

Point p3 = new Point();

p1.X = ((Point)points[0]).X - middle.X;

p1.Y = ((Point)points[0]).Y - middle.Y;

p2.X = ((Point)points[1]).X - middle.X;

p2.Y = ((Point)points[1]).Y - middle.Y;

p3.X = ((Point)points[2]).X - middle.X;

p3.Y = ((Point)points[2]).Y - middle.Y;

double ang1;

if (p1.X != 0)

ang1 = Math.Atan(p1.Y/p1.X);

else

{

if (p1.Y>0) ang1 = Math.PI/2;

else ang1 = 3*Math.PI/2;

}

//вторая четверть

if ( (p1.X < 0) && (p1.Y >= 0) ) ang1 += Math.PI;

//третья четверть

if ( (p1.X < 0) && (p1.Y < 0) ) ang1 += Math.PI;

double ang2;

if (p2.X != 0) ang2 = Math.Atan(p2.Y/p2.X);

else

{

if (p2.Y>0) ang2 = Math.PI/2;

else ang2 = 3*Math.PI/2;

}

//вторая четверть

if ( (p2.X < 0) && (p2.Y > 0) ) ang2 += Math.PI;

//третья четверть

if ( (p2.X < 0) && (p2.Y < 0) ) ang2 += Math.PI;

double ang3;

if (p3.X != 0) ang3 = Math.Atan(p3.Y/p3.X);

else

{

if (p3.Y>0) ang3 = Math.PI/2;

else ang3 = 3*Math.PI/2;

}

//вторая четверть

if ( (p3.X < 0) && (p3.Y > 0) ) ang3 += Math.PI;

//третья четверть

if ( (p3.X < 0) && (p3.Y < 0) ) ang3 += Math.PI;

bool b1 = (ang1<=ang2) && (ang2<=ang3);

bool b2 = (ang3<=ang1) && (ang1<=ang2);

bool b3 = (ang2<=ang3) && (ang3<=ang1);

if ( b1 || b2 || b3 ) return round.COUNTER_CLOCKWISE;

else return round.CLOCKWISE;

}

}

/// <summary>

/// формирует множество уравнений по непересечению с полосой s, возвращает множество уравнений;

/// n - размерность уравнений

/// i - номер многоугольника,нумерация с единицы

/// </summary>

public SetOfEquations FormingEquations(Strip s,int n,int i)

{

SetOfEquations sof = new SetOfEquations(n);

double xmax = 0,xmin = 100000000000,ymax = 0,ymin = 1000000000000;

double x;

double y;

foreach(Point p in points)

{

x = ((Point)p).X;

y = ((Point)p).Y;

if ( x<xmin ) xmin = x;

if ( y<ymin ) ymin = y;

if ( x>xmax ) xmax = x;

if ( y>ymax ) ymax = y;

}

Equation eq1 = new Equation(n);

eq1[2*(i-1)] = -1;

eq1[n] = -xmin; //xmin

sof.Add(eq1);

Equation eq2 = new Equation(n);

eq2[2*(i-1)] = 1;

eq2[n-1] = -1;

eq2[n] = xmax;

sof.Add(eq2);

Equation eq3 = new Equation(n);

eq3[2*i-1] = -1; //1

eq3[n] = -ymin; //ymin

sof.Add(eq3);

Equation eq4 = new Equation(n);

eq4[2*i-1] = 1;

eq4[n] = ymax-s.Width;

sof.Add(eq4);

return sof;

}

/// <summary>

/// формирует множество уравнений по непересечению с другим многоугольником pol,

/// возвращает множество уравнений;

/// n - размерность уравнений

/// i - номер текущего многоугольника

/// j - номер многоугольника pol,нумерация с единицы

/// </summary>

public SetOfEquations FormingEquations(Polygon pol,int n,int i,int j)

{

if (this.Round() == round.CLOCKWISE)

{

points.Reverse();

}

if (pol.Round() == round.CLOCKWISE)

{

pol.points.Reverse();

}

SetOfEquations sof = new SetOfEquations(n);

double x1 = 0;

double y1 = 0;

double x2 = 0;

double y2 = 0;

double x = 0;

double y = 0;

double a = 0;

double b = 0;

double c = 0;

double dmin = 0;

double d = 0;

for(int k = 0;k<points.Count;k++)

{

x1 = ((Point)points[k]).X;

y1 = ((Point)points[k]).Y;

if (k == points.Count-1)

{

x2 = ((Point)points[0]).X;

y2 = ((Point)points[0]).Y;

}

else

{

x2 = ((Point)points[k+1]).X;

y2 = ((Point)points[k+1]).Y;

}

a = y2 - y1;

b = x1 - x2;

c = -x1*y2 + x2*y1;

dmin = 1e+100;

foreach(Point p in pol.points)

{

x = p.X;

y = p.Y;

d = (a*x+b*y+c)/Math.Sqrt(a*a+b*b);

if (d<dmin) dmin = d;

}

Equation eq = new Equation(n);

eq[2*j-2] = a;

eq[2*j-1] = b;

eq[2*i-2] = -a;

eq[2*i-1] = -b;

eq[n] = -dmin;//+

sof.Add(eq);

}

return sof;

}

/// <summary>

/// копирование объекта

/// </summary>

public void Copy(Polygon pol)

{

this.points.Clear();

foreach(Point p in pol.points)

{

Point point = new Point();

point.Copy(p);

this.points.Add(point);

}

pole.Copy(pol.pole);

}

//ширина по Х

public double MaxLengthX()

{

double xmin = 1000000000000;

double xmax = 0;

foreach(Point p in points)

{

if (p.X<xmin) xmin = p.X;

if (p.X>xmax) xmax = p.X;

}

return (xmax-xmin);

}

/// <summary>

/// проверка на принадлежность точки многоугольнику

/// </summary>

public bool IsPointIn(Point p)

{

int num = 0; //количество пересечений гор. линии с многоугольником

int i;

double y1,y2,ymed;

double x1,x2,xmed,xx;

xmed = p.X;

ymed = p.Y;

for(i = 0;i < this.NumPoints-1;i++)

{

y1 = ((Point)points[i]).Y;

y2 = ((Point)points[i+1]).Y;

x1 = ((Point)points[i]).X;

x2 = ((Point)points[i+1]).X;

if ((y2-y1) == 0) xx = 1000; //особоый случай-сторона горизонтальная

else xx = ((x2-x1)/(y2-y1))*(ymed-y1)+x1;

if ( (ymed > y1) && (ymed < y2) && (xmed < xx) ) num++;

if ( (ymed > y2) && (ymed < y1) && (xmed < xx) ) num++;

}

y1 = ((Point)points[this.NumPoints-1]).Y;

y2 = ((Point)points[0]).Y;

x1 = ((Point)points[this.NumPoints-1]).X;

x2 = ((Point)points[0]).X;

if ((y2-y1) == 0) xx = 1000;

else xx = ((x2-x1)/(y2-y1))*(ymed-y1)+x1;

if ( (ymed > y1) && (ymed < y2) && (xmed < xx) ) num++;

if ( (ymed > y2) && (ymed < y1) && (xmed < xx) ) num++;

if ( (num % 2) == 0 ) return false;

else return true;

}

//пересекаются ли многоугольники

public bool IntersectPolygons(Polygon pol)

{

int i,j;

Point p1,p2,p3,p4;

p1 = new Point();

p2 = new Point();

p3 = new Point();

p4 = new Point();

bool flag_a,flag_b;

double ua,ub,chisl_a,chisl_b,znam_a,znam_b;

//этот алгоритм в некоторых случаях не работает, например случай звезда давида

bool result = false;

for(i = 0;i<pol.NumPoints;i++)

result = result || ( this.IsPointIn(pol.GetI(i)) );

for(i = 0;i<this.NumPoints;i++)

result = result || ( pol.IsPointIn(this.GetI(i)) );

if (result) return true;

//проверка на непересение сторон многоугольников

for(i = 0;i<this.NumPoints-1;i++)

{

p1.Copy(this.GetI(i));

p2.Copy(this.GetI(i+1));

for(j = 0;j<pol.NumPoints-1;j++)

{

p3.Copy(pol.GetI(j));

p4.Copy(pol.GetI(j+1));

chisl_a = (p4.X-p3.X)*(p1.Y-p3.Y)-(p4.Y-p3.Y)*(p1.X-p3.X);

chisl_b = (p2.X-p1.X)*(p1.Y-p3.Y)-(p2.Y-p1.Y)*(p1.X-p3.X);

znam_a = (p4.Y-p3.Y)*(p2.X-p1.X)-(p4.X-p3.X)*(p2.Y-p1.Y);

znam_b = znam_a;

if (znam_a != 0)

{

ua = chisl_a/znam_a;

ub = chisl_b/znam_b;

//ua = Math.Abs(ua);

//ub = Math.Abs(ub);

flag_a = (ua>=0) && (ua<=1);

flag_b = (ub>=0) && (ub<=1);

if (flag_a && flag_b) return true;

}

p3.Copy(pol.GetI(pol.NumPoints-1));

p4.Copy(pol.GetI(0));

chisl_a = (p4.X-p3.X)*(p1.Y-p3.Y)-(p4.Y-p3.Y)*(p1.X-p3.X);

chisl_b = (p2.X-p1.X)*(p1.Y-p3.Y)-(p2.Y-p1.Y)*(p1.X-p3.X);

znam_a = (p4.Y-p3.Y)*(p2.X-p1.X)-(p4.X-p3.X)*(p2.Y-p1.Y);

znam_b = znam_a;

if (znam_a != 0)

{

ua = chisl_a/znam_a;

ub = chisl_b/znam_b;

//ua = Math.Abs(ua);

//ub = Math.Abs(ub);

flag_a = (ua>=0) && (ua<=1);

flag_b = (ub>=0) && (ub<=1);

if (flag_a && flag_b) return true;

}

}

}

p1.Copy(this.GetI(this.NumPoints-1));

p2.Copy(this.GetI(0));

for(j = 0;j<pol.NumPoints-1;j++)

{

p3.Copy(pol.GetI(j));

p4.Copy(pol.GetI(j+1));

chisl_a = (p4.X-p3.X)*(p1.Y-p3.Y)-(p4.Y-p3.Y)*(p1.X-p3.X);

chisl_b = (p2.X-p1.X)*(p1.Y-p3.Y)-(p2.Y-p1.Y)*(p1.X-p3.X);

znam_a = (p4.Y-p3.Y)*(p2.X-p1.X)-(p4.X-p3.X)*(p2.Y-p1.Y);

znam_b = znam_a;

if (znam_a != 0)

{

ua = chisl_a/znam_a;

ub = chisl_b/znam_b;

//ua = Math.Abs(ua);

//ub = Math.Abs(ub);

flag_a = (ua>=0) && (ua<=1);

flag_b = (ub>=0) && (ub<=1);

if (flag_a && flag_b) return true;

}

p3.Copy(pol.GetI(pol.NumPoints-1));

p4.Copy(pol.GetI(0));

chisl_a = (p4.X-p3.X)*(p1.Y-p3.Y)-(p4.Y-p3.Y)*(p1.X-p3.X);

chisl_b = (p2.X-p1.X)*(p1.Y-p3.Y)-(p2.Y-p1.Y)*(p1.X-p3.X);

znam_a = (p4.Y-p3.Y)*(p2.X-p1.X)-(p4.X-p3.X)*(p2.Y-p1.Y);

znam_b = znam_a;

if (znam_a != 0)

{

ua = chisl_a/znam_a;

ub = chisl_b/znam_b;

//ua = Math.Abs(ua);

//ub = Math.Abs(ub);

flag_a = (ua>=0) && (ua<=1);

flag_b = (ub>=0) && (ub<=1);

if (flag_a && flag_b) return true;

}

}

return false;

}

}

}

Point.cs

using System;

namespace Diplom

{

/// <summary>

///

/// </summary>

public class Point : Diplom.GeomObj, IOperations, IDraw

{

//constructor

public Point()

{

x = 0;

y = 0;

}

//methods IDraw interface

void IDraw.Draw()

{

Console.WriteLine("Drawing point");

Console.WriteLine("X={0}",x.ToString());

Console.WriteLine("Y={0}",y.ToString());

Console.WriteLine("");

}

//methods IOperations interface

//shift point along vector determinate point "to"

void IOperations.Shift(Point to)

{

x += to.X;

y += to.Y;

}

//rotate point around "center" on positiv "angel"

void IOperations.Rotate(Point center,double angel)

{

double rx = Math.Abs(x-center.X);

double ry = Math.Abs(y-center.Y);

double curr_angel = Math.Atan(ry/rx);

double r = Math.Sqrt(rx*rx+ry*ry);

if (ry < 0) curr_angel += Math.PI;

x = center.X + r * Math.Cos(curr_angel+angel);

y = center.Y + r * Math.Sin(curr_angel+angel);

}

//operator =,copy p to this

public void Copy(Point p)

{

x = p.X;

y = p.Y;

focus = p.focus;

}

//operator ==

new public bool Equals(Object p)

{

return ( (x == ((Point)p).X) && (y == ((Point)p).Y) );

}

/// <summary>

/// property ordinate X

/// </summary>

public double X

{

get

{

return x;

}

set

{

x = value;

}

}

/// <summary>

/// ordinate x

/// </summary>

private double x;

/// <summary>

/// ordinate y

/// </summary>

private double y;

/// <summary>

/// property ordinate Y

/// </summary>

public double Y

{

get

{

return y;

}

set

{

y = value;

}

}

}

}

MyTask.cs

using System;

using System.Collections;

using solveSLAU_SVD;

namespace Diplom

{

public class MyTask

{

public MyTask(ref MainForm _mainForm)

{

cp = new CollectionsPolygons();

sof = null;

sof_strip = null;

matr = new ArrayList();

system = new ArrayList();

ar_sof_pol = new ArrayList();

mf = _mainForm;

begin = new DateTime();

begin = DateTime.Now;

current = new DateTime();

}

//окно

MainForm mf;

// набор многоугольников

private CollectionsPolygons cp;

// возвращает количество многоугольников

public int CountPolygons()

{

return cp.NumPolygons;

}

// доступ к набору многоугольников

public CollectionsPolygons Cp

{

get

{

CollectionsPolygons result = new CollectionsPolygons();

result.Copy(cp);

return result;

}

set

{

cp = value;

}

}

// полоса

private Strip strip;

// полоса

public Strip _Strip

{

get

{

Strip new_strip = new Strip();

new_strip.Copy(strip);

return new_strip;

}

set

{

strip = value;

}

}

// создание множества уравнений

public void CreateSOF()

{

int i,j;

if (cp.NumPolygons == 0) return;

else

{

max_length = 0;

for(i = 0;i<cp.NumPolygons;i++)

if (cp.GetI(i).MaxLengthX()>max_length)

max_length = cp.GetI(i).MaxLengthX();

//количество переменных в уравнениях

int n = cp.NumPolygons * 2 + 1;

sof = new SetOfEquations(n);

sof_strip = new SetOfEquations(n);

for(i = 0;i<cp.NumPolygons;i++)

{

sof.AddSOF( cp.GetI(i).FormingEquations(strip,n,i+1) );

sof_strip.AddSOF( cp.GetI(i).FormingEquations(strip,n,i+1) );

for(j = i+1;j<cp.NumPolygons;j++)

{

sof.AddSOF( cp.GetI(i).FormingEquations(cp.GetI(j),n,i+1,j+1) );

sof.AddSOF( cp.GetI(j).FormingEquations(cp.GetI(i),n,j+1,i+1) );

ar_sof_pol.Add( cp.GetI(i).FormingEquations(cp.GetI(j),n,i+1,j+1) );

ar_sof_pol.Add( cp.GetI(j).FormingEquations(cp.GetI(i),n,j+1,i+1) );

}

}

}

/*for(int i = 0;i<sof.Size();i++)

sof.GetEquationByNumber(i).Output();*/

}

//матрица коэффициентов ситемы уравнений

double[,] a;

//промежуточное решение

double[,] sol;

//максимальная ширина многоугольников

double max_length = 0;

// множество всех уравнений

public SetOfEquations sof;

//множество уравнений на принадлежность полосе

private SetOfEquations sof_strip;

//массив множеств уравнений

private ArrayList ar_sof_pol;

// получение матрицы номеров уравнений расположенных в множестве уравнений

private void ConvertSOFToMatrix()

{

//количество переменных в уравнениях

int n = cp.NumPolygons * 2 + 1;

a = new double[n+1,n+2];

//промежуточное решение

sol = new double[n+1,n+2];

//инициализация массива решений

result = new ArrayList();

int i;

for(i = 0;i<n+1;i++)

for(int j = 0;j<n+2;j++)

{

a[i,j] = 0;

sol[i,j] = 0;

}

for(i = 0;i<n-1;i++)

result.Add(0);

result.Add(strip.Length+1);

SetOfEquations sof_tmp = new SetOfEquations(n);

sof_tmp.AddSOF(sof);

for(i = 1;i<=sof_tmp.Dimension()/*+1*/;i++)

{

ArrayList ar = new ArrayList();

while (sof_tmp.GetNumberI(i) != -1)

{

ar.Add(sof_tmp.GetNumberI(i));

sof_tmp.DeleteI(i);

}

matr.Add(ar);

}

}

//-----------------------------

//-----------------------------

//-----------------------------

//далее методы генерирования дерева

//матрица номеров уравнений

private ArrayList matr;

//массив номеров уравнений входящих в систему уравнений

private ArrayList system;

//таблица коэффициентов уравнений

private double[,] koef;

//счетчик систем уравнений

public int num_system;

//счетчик полученных допустимых точек

public int num_points;

//счетчик отбраковок

public int num_brak;

private long chit;

//массив-решение

ArrayList result;

//время

public DateTime begin;

public DateTime current;

//-----------------

//копирование массивов

ArrayList CopyArray(ArrayList ar)

{

ArrayList res = new ArrayList();

foreach(int num in ar)

res.Add(num);

return res;

}

//-----------------

//генерация систем уравнений и их решение

private void Generations()

{

int n = cp.NumPolygons*2+1;

int layer = 0;

int i,l;

int[] ind = new int[n];

for(i = 0;i<n;i++)

ind[i] = -1;

ind[0] = 0;

system.Add(((ArrayList)matr[0])[0]);

int sec;

int flag_min = 0;

int __min = 1;

while( !((layer<=0) && (ind[0]==-1)) )

{

//дополнительная точка окончания расчета

if ((double)result[2*cp.NumPolygons]<=max_length+5e-10)

{

return;

}

chit++;

if (layer<(n-1))

{

layer++;

ind[layer]++;

system.Add( ((ArrayList)matr[layer])[ind[layer]] );

}

else

{

ind[layer]++;

if (ind[layer] <= ((ArrayList)matr[layer]).Count-1)

system[layer] = ((ArrayList)matr[layer])[ind[layer]];

}

l = layer;

for(i = l;i>=0;i--)

{

if (ind[i] > ((ArrayList)matr[i]).Count-1)

{

ind[i] = -1;

layer = i-1;

system.RemoveAt(system.Count-1);

if ((i-1)>=0)

{

ind[i-1]++;

if (ind[i-1] <= ((ArrayList)matr[i-1]).Count-1)

system[layer] = ((ArrayList)matr[layer])[ind[layer]];

}

}

}

//тест

while ( (layer != -1) && (Test(system,layer)) )

{

chit++;

num_brak++;

mf.textBox_num_brak.Text = num_brak.ToString();

mf.textBox_num_brak.Refresh();

ind[layer]++;

if (ind[layer] <= ((ArrayList)matr[layer]).Count-1)

system[layer] = ((ArrayList)matr[layer])[ind[layer]];

l = layer;

for(i = l;i>=0;i--)

{

if (ind[i] > ((ArrayList)matr[i]).Count-1)

{

ind[i] = -1;

layer = i-1;

system.RemoveAt(system.Count-1);

if ((i-1)>=0)

{

ind[i-1]++;

if (ind[i-1] <= ((ArrayList)matr[i-1]).Count-1)

system[layer] = ((ArrayList)matr[layer])[ind[layer]];

}

}

}

}

if (layer == (n-1))

{

//далее решение

//здесь происходит решение полученное системы

//Output(system);

//далее решение системы уравнений

//Console.WriteLine(num_system.ToString());

//if (num_system == 76548) while(true) {};

SolveSystem(system);

}

}

}

//------------

//отладочная функция для вывода системы уравнений в виде номеров

private void Output(ArrayList ar)

{

Console.WriteLine("Вывод системы № {0}:",num_system.ToString());

String str;

str = "";

foreach(int num in ar)

str = str + num.ToString() + " ";

Console.WriteLine(str);

}

/// <summary>

/// проверка на совместимость входящих уравнений

/// если набор уравнений некорректен то результат true

/// </summary>

private bool Test(ArrayList ar,int i)

{

bool result = false;

//проверка на повторяемость уравнений

if (FindIEquation(ar,(int)ar[i])) return true;

//правила отсечения

int j,k;

//счетчик повторений

int s = 0;

double val;

int n = cp.NumPolygons*2+1;

for(j = 0;j<=i;j++)

{

val = koef[(int)ar[j],n-1];

if (val == -1) s++;

}

if (s>1) return true;

//отсечение 9+5

//if ((chit % 10) == 0) return true;

return result;

}

/// <summary>

/// построение дерева решения и собственное поиск решения

/// </summary>

public ArrayList Solve()

{

ConvertSOFToMatrix();

ConvertSOFToTable();

/*//отладка - вывод таблицы коэффициентов

for(int i = 0;i<sof.Size();i++)

{

for(int j = 0;j<2*cp.NumPolygons+2;j++)

Console.Write("{0} ",koef[i,j]);

Console.WriteLine();

}*/

Generations();

/*for(int i = 0;i<sof.Size();i++)

sof.GetEquationByNumber(i).Output();*/

current = DateTime.Now;

return result;

}

/// <summary>

/// проверка на вхождение i-ого уравнения более одного раза

/// </summary>

private bool FindIEquation(ArrayList ar,int i)

{

int k = 0;

foreach(int num in ar)

if (num == i) k++;

return (k > 1);

}

/// <summary>

/// решение системы уравнений

/// </summary>

private void SolveSystem(ArrayList ar)

{

//номер системы

num_system++;

mf.textBox_NumSystems.Text = num_system.ToString();

mf.textBox_NumSystems.Refresh();

//количество уравнений

int m = 2*cp.NumPolygons+1;

//число неизвестных

int n = m;

/*

A - массив с нумерацией элементов [1..M, 1..N+1].

В столбцах от 1 до N содержится матрица системы,

В столбце N+1 содержится правая часть b.

*/

//double[,] a = new double[m+1,n+2];

//заполнение массива а

int i,j;

for(i = 1;i<=m;i++)

for(j = 1;j<=n+1;j++)

a[i,j] = koef[(int)(ar[i-1]),j-1];

//класс решающий систему уравнений

solveSLAU s = new solveSLAU();

//промежуточное решение

//double[,] sol;

//размерность решения

int dim;

s.svdsolvefundamental(ref a,m,n,ref sol,out dim);

/*

Solutions - массив с нумерацией элементов [1..N, 0..Dimension].

Фундаментальная система решений.

Столбец с номером 0 содержит частное решение системы уравнений (или решение с минимальной невязкой, если система несовместна).

Столбцы с номерами с 1 по Dimension содержат ортогональный набор векторов, являющихся базисом пространства решений однородной системы.

*/

bool flag;

if (dim == 0)

{

//if (num_system == 200) while (true) {};

flag = TestSolution(sol);

if (flag) num_points++;

if ( (sol[n,0] < (double)result[n-1]) && flag )

{

mf.progressBar.Value += mf.progressBar.Step;

if (mf.progressBar.Value == mf.progressBar.Maximum)

mf.progressBar.Value = 0;

mf.textBox_num_points.Text = num_points.ToString();

mf.textBox_num_points.Refresh();

for(i = 0;i<n;i++)

result[i] = sol[i+1,0];

}

/// <summary>

/// коэффициенты множества уравнений представляются в виде таблицы

/// </summary>

private void ConvertSOFToTable()

{

int num_koef = 2*cp.NumPolygons+2;

koef = new double[sof.Size(),num_koef];

Equation eq;

int i,j;

for(i = 0;i<sof.Size();i++)

{

eq = sof.GetEquationByNumber(i);

for(j = 0;j<num_koef-1;j++)

koef[i,j] = eq[j];

koef[i,j] = -eq[j];

}

}

//-----------------------------

//-----------------------------

//-----------------------------

//тестирование промежуточного решения на допустимость

//результат true, если решение допустимо

//в массиве sol нумерация [1..N, 0..0]

private bool TestSolution(double[,] sol)

{

//проверка неравенств на допустимость (принадлежность полосе)

int i,j,k,l;

double a = 0;

double eps = 5e-15;

Equation eq;

bool res = true;

for(i = 0;i<sof_strip.Size();i++)

{

eq = sof_strip.GetEquationByNumber(i);

for(j = 0;j<eq.Dimension();j++)

a += eq[j]*sol[j+1,0];

a += eq[eq.Dimension()];

if ( a > eps) return false;

a = 0;

}

//проверка неравенств на допустимость (взаимное непересечение многоугольников)

CollectionsPolygons cp_tmp = new CollectionsPolygons();

cp_tmp.Copy(cp);

Point p = new Point();

for(i = 0;i<cp_tmp.NumPolygons;i++)

{

p.X = sol[2*i+1,0];

p.Y = sol[2*i+2,0];

Polygon pol = new Polygon();

pol.Copy(cp_tmp.GetI(i));

((IOperations)pol).Shift(p);

((IChange)cp_tmp).SetI(pol,i);

}

for(i = 0;i<cp_tmp.NumPolygons-1;i++)

for(j = i+1;j<cp_tmp.NumPolygons;j++)

if ( cp_tmp.GetI(i).IntersectPolygons(cp_tmp.GetI(j)) )

return false;

return true;

}

}

}

Equation.cs

using System;

using System.Collections;

namespace Diplom

{

/// <summary>

/// класс-уравнение

/// </summary>

public class Equation

{

public Equation(int n)

{

data = new ArrayList(n+1);

for(int i = 0;i<n+1;i++)

data.Add(0.0);

}

/// <summary>

/// массив коэффициентов уравнения

/// </summary>

private ArrayList data;

/// <summary>

/// доступ к коэффициентам по индексу,начиная с 0

/// </summary>

public double this[int ind]

{

get

{

if ((ind > -1) && (ind < data.Count))

return ((double)data[ind]);

else return 0.0;

}

set

{

if ((ind > -1) && (ind < data.Count))

data[ind] = value;

}

}

/// <summary>

/// тестовый метод для вывода коэффициентов

/// </summary>

public void Output()

{

Console.WriteLine("Коэффициенты уравнения");

foreach(double koef in data)

Console.Write(koef.ToString()+" ");

Console.WriteLine("");

}

/// <summary>

/// возвращает количество переменных в уравнении

/// </summary>

public int Dimension()

{

return data.Count-1;

}

/// <summary>

/// проверка на равенство уравнений

/// </summary>

new public bool Equals(Object eq)

{

bool flag = true;

for(int i = 0;i<data.Count;i++)

if ((double)data[i] != ((Equation)eq)[i]) flag = false;

return flag;

}

/// <summary>

/// копирование объекта

/// </summary>

public void Copy(Equation eq)

{

for(int i = 0;i<data.Count;i++)

data[i] = eq[i];

}

}

}

Размещено на Allbest.ru