Projects-3-computer Graphics & Virtual Reality (algorithms, Modeling, Programs)

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada

Grafica pe calculator / Geometrie computationala Computer Graphics / Computation Geometry Titular curs : Conf. Dr. Marin Vlada, Universitatea din Bucuresti WEB: http://marinvlada.googlepages.com/, www.ad-astra.ro/marinvlada E-mail: marinvlada[at]yahoo.com, marinvlada[at]gmail.com Course: COMPUTER GRAPHICS | Bachelor of Science (Computer Science) Software: C++, OpenGL, Java 3D, Java Script, VRML, SVG http://marinvlada.googlepages.com/prog_grafic.htm www.cniv.ro

www.icvl.eu ©

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada

PROIECT – generare curbe plane remarcabile Nota: Codul in C++

REFERINTA: M. Vlada, A,.Posea,…, Grafica pe calculator in limbajele Pascal si C, vol. I,II, , Implementare si aplicatii, Ed. Tehnica,1992 /* cout cout cout cout cout cout cout cout cout cout cout cout */

<<"*******************************************************"<<"\n"; <<" CURBE PLANE REMARCABILE "<<"\n"; <<" autor : M . Vlada "<<"\n"; <<"*******************************************************"<<"\n"; <<" 1 =concoida NICOMEDE 2 =melcul lui PASCAL "<<"\n"; <<" 3 =cisoida DIOCLES 4 =cisoida elipsei "<<"\n"; <<" 5 =trisectoarea MAC-LAURIN 6 =trisectoarea LONGCHAMPS"<<"\n"; <<" 7 =cicloida 8 =epicicloida "<<"\n"; <<" 9 =hipocicloida 10=astroida "<<"\n"; <<" 11=strofoida 12=bucla MARIA AGNESI "<<"\n"; <<" ( centrul ecranului = originea sistemului cartezian ) "<<"\n"; <<"*******************************************************"<<"\n";

//{=========================================================} //program CURBE ; curbe plane remarcabile - ecuatii parametrice #include #include <math.h> #include #include #include <stdlib.h> #define pi M_PI double round(double number) { double x = ceil(number)-number; if( number >= 0 ) {if(x <= 0.5) return ceil(number); else return floor(number);} else {if(x < 0.5) return ceil(number); else return floor(number);} } char solid[8]={255,255,255,255,255,255,255,255}; int graphdriver , graphmode; char ch; int graphX[740], graphY[740]; //array[-319..319] of integer; double a , b , arg , val1 , val2; int i , t1 , t2 , flag; //========================================================== void INIT() { graphdriver = DETECT;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada initgraph (&graphdriver ,&graphmode , "C:\\Borlandc\\bgi"); //init mod grafic setfillpattern ( solid , 15); bar ( 0,0 ,700,500 ); setcolor( 0 ) ; setviewport ( 320 , 175 , 500 , 200 , 0 );//fixare origine rectangle ( -150 , -150 , 150 , 150 ); //deseneaza un chenar setviewport ( 170 , 25 , 470 , 325 , 1 ); //fixare fereastra } void STOP() //iesire din modul grafic { getch(); // inghetare imagine closegraph(); // iesire mod grafic } void AXE() //-----------// deseneaza axele (format mic) in origine { moveto ( 120 , 150 ); lineto ( 180 , 150 ); moveto ( 150 , 120 ); lineto ( 150 , 180 ); } void GRAPH1 (int t1 ,int t2) //-----------------------------------------------//deseneaza curba data de ecuatiile parametrice // x = f (t) , y = g(t) pe intervalul [t1 ,t2] { int i; moveto ( graphX[t1+319] , graphY[t1+319] ) ; // fara trasare for(i = t1+1; i <= t2; i++) lineto ( graphX [ i+319 ] , graphY [ i+319 ] );// trasare } //{----------------------------------------------------} // main void main() { cout <<"*******************************************************"<<"\n"; cout <<" CURBE PLANE REMARCABILE "<<"\n"; cout <<" autor : M . Vlada "<<"\n"; cout <<"*******************************************************"<<"\n"; cout <<" 1 =concoida NICOMEDE 2 =melcul lui PASCAL "<<"\n"; cout <<" 3 =cisoida DIOCLES 4 =cisoida elipsei "<<"\n"; cout <<" 5 =trisectoarea MAC-LAURIN 6 =trisectoarea LONGCHAMPS"<<"\n"; cout <<" 7 =cicloida 8 =epicicloida "<<"\n"; cout <<" 9 =hipocicloida 10=astroida "<<"\n"; cout <<" 11=strofoida 12=bucla MARIA AGNESI "<<"\n"; cout <<" ( centrul ecranului = originea sistemului cartezian ) "<<"\n"; cout <<"*******************************************************"<<"\n"; cout <<" precizitati numarul de ordine pentru curba dorita : "<<"\n"; cin >> flag; switch (flag){

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada case 1: { // ================= curba lui cout <<" curba lui NICOMEDE "; cout <<" dati parametri a , b = "; t1 = round( (- pi / 2.0)*100) ; t2 //factorul 100 reprezinta scalarea for(i = t1; i <= t2; i++) { arg = i / 100.00 ; //vectorii graphX, graphY retin

NICOMEDE =============== cin >> a; cin>>b; =round( (pi / 2.0)*100); imaginii

coordonatele pentru

desenare graphX [i+319] = round( ( a + b * cos (arg) ) * 100 )+150 ; graphY [i+319] = round( ( a*sin(arg)/cos(arg) + b*sin(arg))*100)+150; } INIT(); AXE(); GRAPH1 ( t1 , t2 ); for(i = t1; i <= t2; i++) { arg = i / 100.00 ; graphX[i+319] = round( ( a - b * cos(arg) ) *100 )+150 ; graphY[i+319] = round( ( a*sin(arg)/cos(arg) b*sin(arg))*100)+150; } GRAPH1 ( t1 , t2 ) ; break; } // =================== melcul lui PASCAL =================== case 2 : { cout <<" melcul lui PASCAL "<<"\n"; cout <<" dati parametri a ,b = "; cin >> a; cin >> b; t1 = round( -pi * 90 ) ; t2 = - t1 ; for(i = t1; i <= t2; i++) { arg = i / 90.00 ; graphX[i+319] = round( ( 2 *(a * cos(arg) + b)*cos(arg) ) * 90 ); graphY[i+319] = round( ( 2 *(a * cos(arg) + b)*sin(arg) ) * 90 ); graphX[i+319] = graphX[i+319] + 150 ; graphY[i+319] = graphY[i+319] + 150; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ; break; } // =========== cisoida lui DIOCLES ( cisoida cercului ========= case 3 : { cout <<" cisoida lui DIOCLES ( cisoida cercului "<<'\n'; cout<<" dati parametrul a = "; cin >> a; t1 = round ( (-pi /2.0 ) * 90 ) ; t2 = - t1 ;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada for(i = t1; i <=t2; i++) { arg = i / 90.0 ; graphX[i+319] = round( ( 2*a*sin(arg) *sin(arg) ) * 90 ) + 150 ; graphY[i+319] = round( ( 2*a*sin(arg)*sin(arg)*sin(arg) /cos(arg) ) * 90 ) + 150 ; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ; break; } // ========================= cisoida elipsei ==================== case 4 : { cout <<" cisoida elipsei "; cout<<" dati parametri a , b = "; cin >> a>> b; t1 = round( ( - pi / 2.0 ) * 90 ) ; t2 = - t1 ; for( i = t1; i<= t2; i++) { arg = i / 90.0 + 0.01 ; graphX[i+319] = round( ( 2*a*a*a / ( a*a + b*b* pow(( cos(arg) / sin(arg) ),2) ) ) * 90 ) + 150 ; graphY[i+319] = round( ( 2*a*a*a / ( a*a * cos(arg) / sin(arg) + b*b * pow( ( cos(arg) / sin(arg) ),2) * ( cos(arg) / sin(arg) ) ) ) * 90 ) + 150 ; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ; break; } // ================== trisectoarea lui MAC - LAURIN ================== case 5 : { cout <<" trisectoarea lui MAC - LAURIN "<<"\n"; cout <<" dati parametrul a = "; cin>> a; t1 = round ( ( - pi / 2.0 ) * 90 ) ; t2 = - t1 ; for( i= t1; i<=t2; i++) { arg = i / 90.0 + 0.01 ; graphX[i+319] = round ( ( 4 * a * cos(arg) * cos(arg) - a) * 90)+150; graphY[i+319] = round ( ((4 * a * cos(arg) * cos(arg) - a) * sin(arg) / cos(arg) ) * 90 ) + 150 ; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ; break; } // ==================== trisectoarea lui LONGCHAMPS =================== case 6 : { cout <<" trisectoarea lui LONGCHAMPS ";

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada cout <<" dati parametrul a = "; cin >> a; t1 = round ( ( - pi / 2.0 ) * 50 ) ; t2 = - t1 ; for( i = t1; i <= t2; i++) { arg = i / 50.0 + 0.01 ; graphX[i+319] = round ( ( a / ( 4 * cos(arg)*cos(arg) -3) ) *50) +150; graphY[i+319] = round ( ( ( a* sin(arg) /cos(arg) ) / ( 4 * cos(arg) * cos(arg) - 3 ) ) * 50 ) + 150 ; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ; break; } // ======================= cicloida ================================ case 7 : { cout <<" cicloida "; cout<<" dati parametri a , b = "; cin >> a>>b; t1 = round ( ( - 2 * pi* 1.4 )* 35 ) ; t2 = - t1 ; for(i= t1; i <= t2; i++) { arg = i / 35.0 ; graphX[i+319] = round ( ( a * arg - b*sin(arg) ) * 35 ) + 150 ; graphY[i+319] = round ( ( a - b * cos(arg) ) * 35 ) + 150 ; } INIT(); AXE(); GRAPH1 ( t1 , t2 ) ;break; } // ===================== epicicloida =============================== case 8 :{ cout <<" epicicloida "; cout <<" dati parametri a , b = "; cin>> a>> b ; t1 = 0 ; t2 = round ( 10 * pi * 10) ; for(i = t1; i <= t2; i++) { arg = i / 10.00 ; val1 = b *arg / a ; val2 = arg + b * arg / a; graphX[i+319] = round( ( ( a + b) * cos( val1 ) - b * cos( val2 ) ) * 60 ) + 150; graphY[i+319] = round( ( (a + b) * sin( val1 ) - b * sin( val2 ) ) * 60 ) + 150 ; } INIT() ; AXE() ; GRAPH1 ( t1 , t2 ); break; } // ======================== hipocicloida ============================= case 9 : { cout <<" hipocicloida "; cout <<" dati parametri a , b = "; cin>> a >> b; t1 = 0 ; t2 = round ( 10 * pi * 10 ) ;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada for(i = t1; i <= t2; i++) { arg = i / 10.00 ; val1 = b * arg / a ; val2 = arg - b * arg / a ; graphX[i+319] = round( (( a-b ) * cos( val1 ) + b * cos( val2 )) * 150 ) + 150 ; graphY[i+319] = round( (( a-b ) * sin( val1 ) - b * sin( val2 )) * 150 ) + 150 ; } INIT() ; AXE() ; GRAPH1 ( t1 , t2 ) ; break; } // ======================== astroida =============================== case 10 : { cout <<" astroida "; cout <<" dati parametrul a = "; cin >> a; t1 = 0 ; t2 = round ( 2 * pi * 10 ) ; for(i = t1; i <= t2; i++) { arg = i / 10.00 ; graphX[i+319] = round ( ( a * cos(arg) * cos(arg) * cos(arg) ) * 60 ) + 150 ; graphY[i+319] = round ( ( a * sin(arg) * sin(arg) * sin(arg) ) * 60 ) + 150 ; } INIT() ; AXE() ; GRAPH1 ( t1 , t2 ) ; break; } // ========================= strofoida ============================== case 11 : { cout <<" strofoida "; cout <<" dati parametrul a = "; cin >> a; t1 = round ( ( - pi / 2 ) * 60 ) ; t2 = -t1 ; for(i = t1; i <= t2; i++) { arg = i / 60.0 + 0.01 ; graphX[i+319] = round( ( a + a * sin(arg) ) * 60 ) + 150 ; graphY[i+319] = round( ( a*sin(arg)/cos(arg) + a * sin(arg) * sin(arg) / cos(arg) ) * 60 ) + 150 ; } INIT() ; AXE() ; GRAPH1 ( t1 , t2 ) ; for(i = t1; i <= t2; i++) { arg = i / 60.0 + 0.01 ;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada graphX[i+319] = round( ( a - a * sin(arg) ) * 60 ) + 150 ; graphY[i+319] = round( ( a*sin(arg)/cos(arg) - a * sin(arg) * sin(arg) / cos(arg) ) * 60 ) + 150 ; } GRAPH1 ( t1 , t2 ) ; break; } // ==================== bucla MARIA AGNESI ====================== case 12 : { cout <<" bucla MARIA AGNESI "; cout <<" dati parametrul a = "; cin >> a; t1 = 1 ; t2 = round( pi * 60 ) - 1; for(i = t1; i <= t2; i++) { arg = i / 60.0 ; graphX[i+319] = round ( a * cos(arg) / sin(arg) * 60 ) + 150 ; graphY[i+319] = round ( a * sin(arg) * sin(arg) * 60 ) + 150 ; } INIT() ; AXE() ; GRAPH1 ( t1 , t2 ) ;break; } case 13: exit(0); } STOP(); } //sfirsit program

PROIECT – mini editor grafic Nota: Codul Visual Studio (Visual

C++); Visual Studio .NET 2003

Autor: Lucian Codita, sudent Facultatea de Matematica si Informatica, Universitatea din Bucuresti -Utilizeaza algoritmul Bresenham pentru trasarea liniei si cercului Program.cs using System; using System.Collections.Generic; using System.Windows.Forms; namespace Grafica { static class Program { /// <summary> /// The main entry point for the application. /// [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1());

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada } } }

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada Form1.cs using using using using using using using using

System; System.Collections.Generic; System.ComponentModel; System.Data; System.Drawing; System.Drawing.Imaging; System.Text; System.Windows.Forms;

namespace Grafica { public partial class Form1 : Form { private Bitmap buffer; // va contine figura ce se deseneaza la un moment dat; dupa ce am terminat, se va salva figura pe canvas private Bitmap canvas; // va contine imaginea finala private Graphics canvasGraphics; private Graphics bufferGraphics; private private private private

int int int int

Ax; // punctul de unde incep sa desenez Ay; Bx; // punctul unde termin de desenat By;

private Color color; //culoarea cu care se picteaza private Boolean drawMode = false; // desenez in momentul asta sau nu ? private String operation; // operatia ce se desfasoara public Form1() { InitializeComponent(); } private void Form1_Load(object sender, EventArgs e) { buffer = new Bitmap(400, 300, System.Drawing.Imaging.PixelFormat.Format24bppRgb); canvas = new Bitmap(400, 300, System.Drawing.Imaging.PixelFormat.Format24bppRgb); canvasGraphics = Graphics.FromImage(canvas); bufferGraphics = Graphics.FromImage(buffer); color = Color.DarkCyan; operation = "circle"; canvasGraphics.Clear(Color.White); bufferGraphics.Clear(Color.White); panel1.Cursor = Cursors.Cross; } private void panel1_MouseDown(object sender, MouseEventArgs e) { Ax = e.X; Ay = e.Y;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada drawMode = true; } private void panel1_MouseMove(object sender, MouseEventArgs e) { if (!drawMode) return; Bx = e.X; By = e.Y; bufferGraphics.Clear(Color.White); if (operation == "circle") drawCircle(); if (operation == "line") drawLine(); if (operation == "erase") erase(); if (operation == "brush") brush(); this.panel1.Invalidate(); // fortez redesenarea panel-ului } private void panel1_MouseUp(object sender, MouseEventArgs e) { drawMode = false; // salvez figura curenta pe poza principala (canvas) : ImageAttributes attr = new ImageAttributes(); attr.SetColorKey(Color.White, Color.White); Rectangle dstRect = new Rectangle(0, 0, buffer.Width, buffer.Height); canvasGraphics.DrawImage(buffer, dstRect, 0, 0, buffer.Width, buffer.Height, GraphicsUnit.Pixel, attr); bufferGraphics.Clear(Color.White); this.panel1.Invalidate(); } private void panel1_Paint(object sender, PaintEventArgs e) { Graphics objGraphics = e.Graphics; // afisez mai intai poza principala : objGraphics.DrawImage(canvas, 0, 0); // fac bufferul (ce contine figura curenta) transparent si il afisez : ImageAttributes attr = new ImageAttributes(); attr.SetColorKey(Color.White, Color.White); Rectangle dstRect = new Rectangle(0, 0, buffer.Width, buffer.Height); objGraphics.DrawImage(buffer, dstRect, 0, 0, buffer.Width, buffer.Height, GraphicsUnit.Pixel, attr); } private void newToolStripMenuItem_Click(object sender, EventArgs e) { // sterg totul: canvasGraphics.Clear(Color.White); bufferGraphics.Clear(Color.White); this.panel1.Invalidate(); }

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada /* * - functii grafice -----------------------------------*/ void drawCircle() { int radius = (int)Math.Round(Math.Sqrt((Bx - Ax) * (Bx Ax) + (By - Ay) * (By - Ay))); Bitmap bm = new Bitmap(1, 1); bm.SetPixel(0, 0, color); int D = 1 - radius; int x = 0; int y = radius; int i = 0; while (x <= y) { ++i; x++; if (D < 0) { D += 2 * x + 3; } else { y--; D += 2 * (x - y) + 5; } bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm, bufferGraphics.DrawImage(bm,

Ax Ax Ax Ax Ax Ax Ax Ax

+ + + + -

x, y, y, x, x, x, y, y,

Ay Ay Ay Ay Ay Ay Ay Ay

+ + + +

y); x); x); y); y); y); x); x);

} } void drawLine() // algoritmul bresenham { Bitmap bm = new Bitmap(1, 1); bm.SetPixel(0, 0, color); int x0 = Ax; int y0 = Ay; int x1 = Bx; int y1 = By; bool steep = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) // daca panta dreptei e mai mare ca 1 inversez coordonatele x si y { swap(ref x0, ref y0); swap(ref x1, ref y1); } if (x0 > x1) // daca linia se indreapta spre stanga inversez capetele { swap(ref x0, ref x1);

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada swap(ref y0, ref y1); } int deltax = x1 - x0; int deltay = Math.Abs(y1 - y0); int error = -deltax / 2; int ystep; int y = y0; if (y0 < y1) // daca linia se indreapta in sus adaug -1 variabilei y la fiecare pas ystep = 1; else ystep = -1; for (int x = x0; x<= x1; x++) { if (steep) bufferGraphics.DrawImage(bm, y, x); else bufferGraphics.DrawImage(bm, x, y); error = error + deltay; if (error >= 0) { y = y + ystep; error = error - deltax; } } } void erase() { Bitmap bm = new Bitmap(20, 20); Graphics objGraphics = Graphics.FromImage(bm); objGraphics.Clear(Color.White); canvasGraphics.DrawImage(bm, Bx, By); } void brush() { Bitmap bm = new Bitmap(5, 5); Graphics objGraphics = Graphics.FromImage(bm); objGraphics.Clear(color); canvasGraphics.DrawImage(bm, Bx, By); } private void button15_Click(object sender, EventArgs e) { info.BackColor = this.color = button15.BackColor; } private void button2_Click(object sender, EventArgs e) { info.BackColor = this.color = button2.BackColor; } private void button3_Click(object sender, EventArgs e) { info.BackColor = this.color = button3.BackColor; } private void button4_Click(object sender, EventArgs e) { info.BackColor = this.color = button4.BackColor;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada } private void button7_Click(object sender, EventArgs e) { info.BackColor = this.color = this.color = button7.BackColor; } private void button6_Click(object sender, EventArgs e) { info.BackColor = this.color = button6.BackColor; } private void button5_Click(object sender, EventArgs e) { info.BackColor = this.color = button5.BackColor; } private void button9_Click(object sender, EventArgs e) { info.BackColor = this.color = button9.BackColor; } private void button10_Click(object sender, EventArgs e) { info.BackColor = this.color = button10.BackColor; } private void button11_Click(object sender, EventArgs e) { info.BackColor = this.color = button11.BackColor; } private void button12_Click(object sender, EventArgs e) { info.BackColor = this.color = button12.BackColor; } private void button13_Click(object sender, EventArgs e) { info.BackColor = this.color = button13.BackColor; } private void button14_Click(object sender, EventArgs e) { info.BackColor = this.color = button14.BackColor; } private void button1_Click(object sender, EventArgs e) { info.BackColor = this.color = button1.BackColor; } private void button8_Click(object sender, EventArgs e) { info.BackColor = this.color = button8.BackColor; }

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada private { int y = x = }

void swap(ref int x, ref int y) a = y; x; a;

private void button16_Click(object sender, EventArgs e) { operation = "circle"; } private void button18_Click(object sender, EventArgs e) { operation = "line"; } private void button19_Click(object sender, EventArgs e) { operation = "erase"; } private void button20_Click(object sender, EventArgs e) { operation = "brush"; } private void newToolStripMenuItem1_Click(object sender, EventArgs e) { canvasGraphics.Clear(Color.White); bufferGraphics.Clear(Color.White); panel1.Invalidate(); } private void exitToolStripMenuItem1_Click(object sender, EventArgs e) { this.Close(); } } // un panel special, ce nu clipeste atunci cand se deseneaza pe el public class NewPanel : System.Windows.Forms.Panel { public NewPanel() { this.SetStyle(ControlStyles.DoubleBuffer, true); this.SetStyle(ControlStyles.UserPaint, true); this.SetStyle(ControlStyles.AllPaintingInWmPaint, true); this.UpdateStyles(); } } }

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada

PROIECT – aplicatie privind aria uni poligon oarecare Nota: Codul Visual Studio (Visual

C++); Visual Studio .NET 2003

Într-un sistem cartezian de axe XOY, considerăm un domeniu ce este determinat de o linie poligonală oarecare şi închisă P = P1P2 ... Pn , unde punctele Pi (xi , yi ), i= 1…n sunt determinate de coordonatele carteziene (xi , yi ), i= 1…n . Aria domeniului este data de urmatoarea formula:

Ca exemplu, prezentăm în figura de mai jos un domeniu oarecare determinat de 11 puncte date prin coordonate carteziene. Valoarea absolută din formula de mai sus este necesară, deoarece introducerea coordonatelor punctelor ce determină domeniu poate fi în sens trigonometric sau în sens invers celui trigonometric, aşa cum este în figura de mai jos.

Programul va afisa fereastra prezentata mai jos (Height = 300, Width = 450) si care ofera un meniu in partea inferioara, format din butoane pentru actiuni utile pentru aplicatie: - stergerea tuturor elementelor din zona de editare • Erase all (New) • Load from file - incarcarea unui fisier deja creat - salvarea coordonetelor punctelor intr-un fisier • Save to a file • Edit – modificarea / editarea punctelor deja introduse • Compute Area – activ (se va calcula aria domeniului poligonal) dupa introducerea in zona de editare a punctelor poligonului

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada

Erase Load from file Save to a file Introducerea punctelor se face folosind mouse-ul prin actiunea de click-stanga in zona de editare, fiecare punct fiid numerotat si colorat cu verde (punctul initial fiind colorat cu albastru). Ultimul punt trebuie sa fie obtinut prin click-stanga pe primul introdus in scopul inchiderii domeniului poligonal. Dupa obtinerea poligonului dorit se pot face modificari ale coordonatelor punctelor prin click-stanga pe punct si „tragere” in zona dorita.

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada EXEMPLU:

Calculul ariei Program.cs using System; using System.Collections.Generic; using System.Windows.Forms; namespace PolygonalArea { static class Program { /// <summary> /// The main entry point for the application. /// [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault( false ); Application.Run( new Form1() ); } } } Form1.cs using using using using

System; System.Collections.Generic; System.ComponentModel; System.Data;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada using System.Drawing; using System.Text; using System.Windows.Forms; namespace PolygonalArea { public partial class Form1 : Form { public Form1() { InitializeComponent(); } private graphicArea mainZone; private void Form1_Load( object sender, EventArgs e ) { mainZone = new graphicArea( graphicAreaMode.Polygon ); mainZone.Location = placeHolder.Location; this.Controls.Add( mainZone ); } private void Form1_Resize( object sender, EventArgs e ) { if( this.Height < 300 ) this.Height = 300; if( this.Width < 450 ) this.Width = 450; mainZone.Height = this.Height - 60; mainZone.Width = this.Width - 35; } private void Form1_FormClosing( object sender, FormClosingEventArgs e ) { mainZone.closingASAP = true; } } }

graphicArea.cs using using using using using using using using using using

System; System.Collections; System.Collections.Generic; System.ComponentModel; System.Drawing; System.Drawing.Drawing2D; System.Drawing.Imaging; System.Data; System.Text; System.Windows.Forms;

namespace PolygonalArea {

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada internal struct Edge { public int v1, v2; public Edge( int v1, int v2 ) { this.v1 = v1; this.v2 = v2; } } public enum graphicAreaMode { Graph, Polygon, Count } public enum graphicAreaStatus { Place, Edit, Compute, Count } public partial class graphicArea : UserControl { private List v = new List(); private List<Edge> e = new List<Edge>(); graphicAreaMode mode; internal bool closingASAP = false; public graphicArea( graphicAreaMode mode ) { this.mode = mode; InitializeComponent(); cmdAction.Text = actionName; cmdAction.Enabled = chkEdit.Checked = false; picBox.Image = new Bitmap( picBox.Width, picBox.Height, PixelFormat.Format32bppPArgb ); tooltips.SetToolTip( cmdNew, "Erase all (New)" ); tooltips.SetToolTip( cmdLoad, "Load from file" ); tooltips.SetToolTip( cmdSave, "Save to a file" ); } public graphicAreaStatus status() { if( !chkEdit.Checked ) return graphicAreaStatus.Place; return graphicAreaStatus.Edit; //to-do: other statuses? } private Point startedAt; private Label editing = null;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada private void picBox_MouseDown( object sender, MouseEventArgs e ) { if( ( chkEdit.Checked ) && ( editing != null ) ) { editing.BackColor = Color.LightGreen; editing = null; } startedAt = e.Location; } private void vertex_MouseDown( object sender, MouseEventArgs e ) { if( chkEdit.Checked ) { editing = ( Label )sender; editing.BackColor = Color.Yellow; } startedAt = ( ( Label )sender ).Location; startedAt.Offset( e.Location ); //updates the global variable } private /*const*/ int RADIUS = 10; private List getTouchyPoints( int x, int y ) { return getTouchyPoints( x, y, -1 ); } private List getTouchyPoints( int x, int y, int excluding ) { List result = new List(); int minDist = 7 * RADIUS / 2; for( int i = 0; i < v.Count; i++ ) if( i != excluding ) if( distance( x, y, v[ i ].X, v[ i ].Y ) < minDist ) result.Add( i ); return result; } private double distance( int x1, int y1, int x2, int y2 ) { return Math.Sqrt( ( ( x1 - x2 ) * ( x1 - x2 ) ) + ( ( y1 - y2 ) * ( y1 - y2 ) ) ); } private double getDistance( Point p1, Point p2 ) { return distance( p1.X, p1.Y, p2.X, p2.Y ); } private Label makeVertex( int x, int y, string tag ) { return makeVertex( x, y, tag, Color.LightGreen );

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada } private Label makeVertex( int x, int y, string tag, Color c ) { Label vertex = new Label(); vertex.BackColor = c; vertex.Height = vertex.Width = 2 * RADIUS; vertex.Location = new Point( x - RADIUS, y - RADIUS ); vertex.Tag = tag; //todo: use a flag to set if the number is shown or not vertex.TextAlign = ContentAlignment.MiddleCenter; vertex.Text = tag; //shape GraphicsPath path = new GraphicsPath(); //System.Drawing.Drawing2D path.AddEllipse( 0, 0, 2 * RADIUS, 2 * RADIUS ); vertex.Region = new Region( path ); //event handlers vertex.MouseDown += new MouseEventHandler( vertex_MouseDown ); vertex.MouseUp += new MouseEventHandler( vertex_MouseUp ); vertex.MouseMove += new MouseEventHandler( vertex_MouseMove ); //the end return vertex; } private void makeLine( int p ) { makeLine( p, p + 1, Pens.Black ); } private void makeLines( int point, Pen pen ) { if( point < 0 ) return; int max = v.Count - 1; if( point > 0 ) makeLine( point - 1, point, pen ); else makeLine( max, 0, pen ); if( point < max ) makeLine( point, point + 1, pen ); else makeLine( max, 0, pen ); } private void makeLine( int p1, int p2, Pen pen ) { //Pen p = new Pen( Color.Black, 1 ); //Graphics g = picBox.CreateGraphics(); //g.DrawLine( p, v[ p1 ], v[ p2 ] ); //g.Dispose(); //p.Dispose();

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada Graphics.FromImage( picBox.Image ).DrawLine( pen, v[ p1 ], v[ p2 ] ); picBox.Invalidate(); } private void vertex_MouseUp( object sender, MouseEventArgs e ) { Point displacement = ( ( Label )sender ).Location; MouseEventArgs actualEvent = new MouseEventArgs( e.Button, e.Clicks, e.X + displacement.X, e.Y + displacement.Y, e.Delta ); picBox_MouseUp( sender, actualEvent ); } private void cmdNew_Click( object sender, EventArgs e ) { v.Clear(); this.e.Clear(); picBox.Controls.Clear(); Graphics.FromImage( picBox.Image ).Clear( Color.White ); picBox.Invalidate(); cmdAction.Enabled = chkEdit.Checked = false; } private void cmdLoad_Click( object sender, EventArgs e ) { OpenFileDialog dialog = new OpenFileDialog(); dialog.CheckFileExists = true; dialog.Multiselect = false; dialog.Title = "Select the input file..."; if( dialog.ShowDialog() == DialogResult.Cancel ) return; List<Edge> incomingLines = null; List newData = loadDataFromFile( dialog.FileName, ref incomingLines ); if( newData.Count < 3 ) { MessageBox.Show( "Not enough points were specified!" ); return; } if( v.Count > 0 ) { DialogResult res = MessageBox.Show( "You have already drawn some points! Replace them?", "Caution: overwriting existing data", MessageBoxButtons.YesNo ); if( res == DialogResult.No ) return; cmdNew_Click( null, null ); } v = newData; this.e = incomingLines; //create labels and lines: recreatePicture();

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada } int minXpt, maxXpt, minYpt, maxYpt; private List loadDataFromFile( string fileName, ref List<Edge> edges ) { System.IO.TextReader reader = new System.IO.StreamReader( fileName ); string count = reader.ReadLine(); if( notAnInt( count ) ) return new List(); List result = new List( System.Convert.ToInt32( count ) ); progressBarContainer.Text = "Loading Vertices..."; progressBarContainer.Visible = true; progressBar.Maximum = result.Capacity; readPoints( result, reader ); progressBarContainer.Text = "Analyzing Vertices..."; double minDist = findExtremes( result ); { lblResult.Text = "d: " + minDist.ToString(); } if( minDist < ( 3 * RADIUS ) ) RADIUS = ( int )Math.Round( minDist / 3 ); { lblResult.Text = "new r: " + RADIUS.ToString(); } //debug: //Graphics.FromImage( picBox.Image ).DrawRectangle( Pens.LightGray, result[ minXpt ].X - 1, result[ minYpt ].Y - 1, 2 + result[ maxXpt ].X - result[ minXpt ].X, 2 + result[ maxYpt ].Y result[ minYpt ].Y ); //resize to fit: int dx = 0, dy = 0; if( ( result[ maxXpt ].X + 2 * RADIUS ) > picBox.Width ) dx = result[ maxXpt ].X + 2 * RADIUS picBox.Width; if( ( result[ maxYpt ].Y + 2 * RADIUS ) > picBox.Height ) dy = result[ maxYpt ].Y + 2 * RADIUS picBox.Height; if( ( dx > 0 ) || ( dy > 0 ) ) { this.Parent.Width += dx; this.Parent.Height += dy; } count = reader.ReadLine(); if( notAnInt( count ) ) return new List(); edges = new List<Edge>( System.Convert.ToInt32( count ) ); progressBarContainer.Text = "Loading Edges..."; progressBar.Maximum = edges.Capacity; for( int j = 0; j < edges.Capacity; j++ )

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada { progressBar.Value = j; string endPoints = reader.ReadLine(); string[] index = endPoints.Split( ' ' ); int v1 = 0, v2 = 0; if( notAnInt( index[ 0 ] ) || notAnInt( index[ 1 ] ) ) { //todo: warn: not an int } else { v1 = Convert.ToInt32( index[ 0 ] ); v2 = Convert.ToInt32( index[ 1 ] ); edges.Add( new Edge( v1, v2 ) ); } } progressBarContainer.Visible = false; reader.Close(); checkIntersections(); chkEdit.Enabled = true; return result; } private void readPoints( List points, System.IO.TextReader reader ) { for( int i = 0; i < points.Capacity; i++ ) { progressBar.Value = i; string location = reader.ReadLine(); string[] coords = location.Split( ' ' ); int x = 0, y = 0; if( notAnInt( coords[ 0 ] ) || notAnInt( coords[ 1 ] ) ) { //todo: warn: not an int } else { x = Convert.ToInt32( coords[ 0 ] ); y = Convert.ToInt32( coords[ 1 ] ); points.Add( new Point( x, y ) ); } } } private double findExtremes( List points ) { double minDist = -1.0; minXpt = maxXpt = minYpt = maxYpt = 0; for( int i = 0; i < points.Count; i++ ) { progressBar.Value = i; if( points[ i ].X < points[ minXpt ].X ) minXpt = i; if( points[ i ].X > points[ maxXpt ].X )

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada maxXpt = i; if( points[ i ].Y < points[ minYpt ].Y ) minYpt = i; if( points[ i ].Y > points[ maxYpt ].Y ) maxYpt = i; if( minDist < 0 ) { if( i == 1 ) minDist = getDistance( points[ 0 ], points[ 1 ] ); } else { int j = i - 1; double currentDist = 0; for( int k = 0; k < j; k++ ) { currentDist = getDistance( points[ k ], points[ j ] ); if( currentDist < minDist ) minDist = currentDist; } } } return minDist; } private bool notAnInt( string count ) { try { int i = System.Convert.ToInt32( count ); return false; } catch( FormatException ) { return true; } catch( OverflowException ) { return true; } } private void cmdSave_Click( object sender, EventArgs e ) { SaveFileDialog dialog = new SaveFileDialog(); dialog.OverwritePrompt = true; dialog.Title = "Select the input file..."; if( dialog.ShowDialog() == DialogResult.Cancel ) return; System.IO.TextWriter writer = new System.IO.StreamWriter( dialog.FileName, false ); writer.WriteLine( v.Count ); for( int i = 0; i < v.Count; i++ ) writer.WriteLine( "{0} {1}", v[ i ].X, v[ i ].Y );

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada writer.WriteLine( this.e.Count ); for( int j = 0; j < this.e.Count; j++ ) writer.WriteLine( "{0} {1}", this.e[ j ].v1, this.e[ j ].v2 ); writer.Close(); } private void tmrRefresher_Tick( object sender, EventArgs e ) { picBox.Refresh(); picBox.Invalidate(); } private void graphicArea_Resize( object sender, EventArgs e ) { picBox.Height = this.Height - 60; picBox.Width = this.Width - 20; panelTools.Top = picBox.Top + picBox.Height; //instead of moving all of: //cmdNew //cmdLoad + cmdSave //chkEdit //cmdAction + chkShowAll //lblResult //also, do something about the bitmap too: //picBox.Image = new Bitmap( picBox.Width, picBox.Height, PixelFormat.Format32bppPArgb ); Bitmap old = ( Bitmap )picBox.Image; int newWidth = ( picBox.Width > old.Width ? picBox.Width : old.Width ); int newHeight = ( picBox.Height > old.Height ? picBox.Height : old.Height ); picBox.Image = new Bitmap( newWidth, newHeight, PixelFormat.Format32bppPArgb ); Graphics.FromImage( picBox.Image ).DrawImage( old, new Point( 0, 0 ) ); } } } polygonalArea.cs using using using using using

System; System.Collections.Generic; System.Drawing; System.Text; System.Windows.Forms;

namespace PolygonalArea { //class polygonalArea : action //{ //} public partial class graphicArea : UserControl

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada { private string actionName = "Compute Area"; private List VL = new List(); Point previousLocation = Point.Empty; void vertex_MouseMove( object sender, MouseEventArgs e ) { if( previousLocation != Point.Empty ) //erase previous circle { Graphics.FromImage( picBox.Image ).DrawEllipse( Pens.White, previousLocation.X - RADIUS, previousLocation.Y - RADIUS, 2 * RADIUS, 2 * RADIUS ); previousLocation = Point.Empty; } if( ( chkEdit.Checked ) && ( editing != null ) ) { //find relative location Label vertex = ( Label )sender; Point location = e.Location; location.Offset( vertex.Location ); previousLocation = location; Graphics.FromImage( picBox.Image ).DrawEllipse( Pens.LightGray, location.X - RADIUS, location.Y - RADIUS, 2 * RADIUS, 2 * RADIUS ); picBox.Invalidate(); } } private void picBox_MouseMove( object sender, MouseEventArgs e ) { if( previousLocation != Point.Empty ) //erase leftover circle { Graphics.FromImage( picBox.Image ).DrawEllipse( Pens.White, previousLocation.X - RADIUS, previousLocation.Y - RADIUS, 2 * RADIUS, 2 * RADIUS ); previousLocation = Point.Empty; } } private void picBox_MouseUp( object sender, MouseEventArgs e ) { lblResult.Visible = true; if( !chkEdit.Checked ) //placement of new points //if( startedAt == e.Location ) //click { Control child = picBox.GetChildAtPoint( e.Location ); if( child != null ) { Point location = child.Location; location.Offset( RADIUS, RADIUS ); //move to center of Label if( location == v[ 0 ] ) {

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada //close: int max = v.Count - 1; this.e.Add( new Edge( max, 0 ) ); makeLine( max, 0, Pens.Black ); chkEdit.Checked = true; checkIntersections(); return; } } //picBox.GetChildAtPoint( e.Location ) has some drawbacks: //1. ignores the circle "leftovers" //2. doesn't compute overlaps //todo: also move away from margin! Point result = e.Location; if( solveOverlaps( ref result ) ) { Label vx; if( v.Count > 0 ) vx = makeVertex( result.X, result.Y, v.Count.ToString() ); else vx = makeVertex( result.X, result.Y, v.Count.ToString(), Color.LightBlue ); picBox.Controls.Add( vx ); v.Add( result ); int i = v.Count - 2; if( i >= 0 ) { this.e.Add( new Edge( i, i + 1 ) ); makeLine( i ); } } } //else //drag //{ // lblResult.Text = "drag what?!?"; //} else //editing if( startedAt == e.Location ) //click -select?!? { if( editing != null ) { //todo: if rightclick, delete lblPreview.Visible = false; editing.BackColor = Color.LightGreen; editing = null; } lblResult.Text = "inconsistent action"; } else //dragged

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada { lblPreview.Visible = false; if( editing == null ) return; //draging action, but nothing had been selected... int i = System.Convert.ToInt32( editing.Tag ); makeGraphLines( i, Pens.White ); int dx = e.X - startedAt.X; int dy = e.Y - startedAt.Y; //lblResult.Text = "moving! " + dx.ToString() + ", " + dy.ToString(); //lblResult.Text += ":\n(" + v[ i ].X.ToString() + ", " + v[ i ].Y.ToString() + ")"; Point p = v[ i ]; p.Offset( dx, dy ); if( !solveOverlaps( ref p, i ) ) { //todo: warn: you can't move there... } dx = p.X - startedAt.X; dy = p.Y - startedAt.Y; v[ i ] = p; //v[ i ].Offset did not work as expected :( //lblResult.Text += "-> (" + v[ i ].X.ToString() + ", " + v[ i ].Y.ToString() + ")"; p = editing.Location; p.Offset( dx, dy ); editing.Location = p; editing.BackColor = Color.LightGreen; editing = null; //lblResult.Text = "moved."; //todo: fix different offsets :( recreatePicture(); } } private void checkIntersections() { int max = v.Count; Point p = new Point(); bool intersections = false; lblPreview.Text = ""; for( int i0 = 0; i0 < max; i0++ ) for( int i1 = i0 + 2; i1 < max; i1++ ) { int i2 = i1 + 1; if( i2 == max ) i2 = 0; if( i2 == i0 ) // and both are 0 continue; lblPreview.Text += Environment.NewLine + "Checking intersection of " + i0.ToString() + " and " + i1.ToString(); if( intersect( v[ i0 ], v[ i0 + 1 ], v[ i1 ], v[ i2 ], ref p ) ) {

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada lblPreview.Text += "... Found!"; intersections = true; //draw red circle at p: Label circle = new Label(); circle.BackColor = Color.Transparent; circle.BorderStyle = BorderStyle.None; circle.Height = circle.Width = 2 * RADIUS; circle.Location = new Point( p.X RADIUS, p.Y - RADIUS ); //make red border: circle.Paint += new PaintEventHandler( circle_RedBorder ); picBox.Controls.Add( circle ); } } System.Windows.Forms.Clipboard.SetDataObject( lblPreview.Text, true ); cmdAction.Enabled = ( !intersections ) && ( e.Count > 0 ? ( e[ e.Count - 1 ].v2 == 0 ) : true ); if( cmdAction.Enabled ) cmdAction.Text = actionName; else cmdAction.Text = "Cannot continue"; } void circle_RedBorder( object sender, PaintEventArgs e ) { base.OnPaint( e ); //int borderWidth = 1; Color borderColor = Color.Red; ControlPaint.DrawBorder( e.Graphics, e.ClipRectangle, borderColor, ButtonBorderStyle.Solid ); //, borderWidth (!!!), ButtonBorderStyle.Solid //, borderColor, borderWidth, ButtonBorderStyle.Solid //, borderColor, borderWidth, ButtonBorderStyle.Solid //, borderColor, borderWidth, ButtonBorderStyle.Solid ); } private bool intersect( Point p1, Point p2, Point p3, Point p4, ref Point i ) { if( p1.Y == p2.Y ) { if( p3.Y == p4.Y ) //both pairs of Y's are equal if( p1.Y != p3.Y ) return false; else { i.X = getMiddle( p1.X, p2.X, p3.X, p4.X );

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada i.Y = p1.Y; return ( i.X > 0 ); } else { double m34 = System.Convert.ToDouble( p3.X - p4.X ) / ( p3.Y - p4.Y ); i.Y = p1.Y; i.X = ( int )Math.Round( p4.X + m34 * ( i.Y - p4.Y ) ); return isBetween( p1, p2, i ) && isBetween( p3, p4, i ); } } else if( p3.Y == p4.Y ) { double m12 = System.Convert.ToDouble( p1.X - p2.X ) / ( p1.Y - p2.Y ); i.Y = p4.Y; i.X = ( int )Math.Round( p1.X + m12 * ( i.Y - p1.Y ) ); return isBetween( p1, p2, i ) && isBetween( p3, p4, i ); } else //both pairs of Y's are different { double m12 = System.Convert.ToDouble( p1.X - p2.X ) / ( p1.Y - p2.Y ); double m34 = System.Convert.ToDouble( p3.X - p4.X ) / ( p3.Y - p4.Y ); if( p1.X == p2.X ) { i.X = p1.X; if( p3.X == p4.X ) if( p1.X == p4.X ) { i.Y = getMiddle( p1.Y, p2.Y, p3.Y, p4.Y ); return ( i.Y > 0 ); } else return false; else { i.Y = ( int )Math.Round( p3.Y + ( i.X - p3.X ) / m34 ); return isBetween( p1, p2, i ) && isBetween( p3, p4, i ); } } else //m12 <> 0 { if( p3.X == p4.X ) { i.X = p4.X;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada i.Y = ( int )Math.Round( p1.Y + ( i.X - p1.X ) / m12 ); return isBetween( p1, p2, i ) && isBetween( p3, p4, i ); } else //m34 <> 0 too, so both pairs of X's are also different { if( ( p1.X - p2.X ) * ( p3.Y - p4.Y ) == ( p1.Y - p2.Y ) * ( p3.X - p4.X ) ) { //parallel! double m14 = System.Convert.ToDouble( p1.X - p4.X ) / ( p1.Y - p4.Y ); if( ( ( int )Math.Round( 1000 * ( m12 - m14 ) ) ) == 0 ) { i.Y = getMiddle( p1.Y, p2.Y, p3.Y, p4.Y ); i.X = p1.X + ( int )Math.Round( m12 * ( i.Y - p1.Y ) ); return ( i.Y > 0 ); } else return false; } else { i.Y = ( int )Math.Round( ( ( m34 * p3.Y - m12 * p1.Y ) + ( p1.X - p3.X ) ) / ( m34 - m12 ) ); i.X = p1.X + ( int )Math.Round( m12 * ( i.Y - p1.Y ) ); if( Math.Abs( ( i.X p3.X ) - m34 * ( i.Y - p3.Y ) ) > 6 ) i.X = p3.X + ( int )Math.Round( m34 * ( i.Y - p3.Y ) ); return isBetween( p1, p2, i ) && isBetween( p3, p4, i ); } } } } } private int getMiddle( int p1, int p2, int p3, int p4 ) { int result = 0; if( isBetween( p1, p2, p3 ) && isBetween( p1, p2, p4 ) ) result = ( p3 + p4 ) / 2; if( isBetween( p3, p4, p1 ) && isBetween( p3, p4, p2 ) ) result = ( p1 + p2 ) / 2; if( isBetween( p1, p2, p3 ) && isBetween( p3, p4, p1 ) )

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada result = ( p1 + p3 ) / 2; if( isBetween( p1, p2, p3 ) && isBetween( p3, p4, p2 ) ) result = ( p2 + p3 ) / 2; if( isBetween( p1, p2, p4 ) && isBetween( p3, p4, p1 ) ) result = ( p1 + p4 ) / 2; if( isBetween( p1, p2, p4 ) && isBetween( p3, p4, p2 ) ) result = ( p2 + p4 ) / 2; return result; } private bool isBetween( Point x1, Point x2, Point y ) { return ( isBetween( x1.X, x2.X, y.X ) ) && ( isBetween( x1.Y, x2.Y, y.Y ) ); } private bool isBetween( int x1, int x2, int y ) { return ( ( x1 <= y ) && ( y <= x2 ) ) || ( ( x2 <= y ) && ( y <= x1 ) ); //return ( ( y - x1 ) * ( y - x2 ) <= 0 ); } private void makeGraphLines( int point, Pen pen ) { if( point < 0 ) return; for( int j = 0; j < e.Count; j++ ) makeLine( e[ j ].v1, e[ j ].v2, pen ); } private bool solveOverlaps( ref Point current ) { return solveOverlaps( ref current, -1 ); } private bool solveOverlaps( ref Point current, int excluding ) { List existing = getTouchyPoints( current.X, current.Y, excluding ); int dx, dy; double dist; //debug: lblResult.Text = "!" + existing.Count.ToString(); switch( existing.Count ) { case 0: break; case 1: lblResult.Text = "solved 1"; //make line from existing[ 0 ] and e.Location dx = current.X - v[ existing[ 0 ] ].X; dy = current.Y - v[ existing[ 0 ] ].Y;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada //move on that same line dist = Math.Sqrt( ( dx * dx ) + ( dy * dy ) ); dx = ( int )Math.Round( dx * 3 * RADIUS / dist ); dy = ( int )Math.Round( dy * 3 * RADIUS / dist ); current.X = v[ existing[ 0 ] ].X + dx; current.Y = v[ existing[ 0 ] ].Y + dy; break; case 2: lblResult.Text = "solved 2"; //move on the segment bisector Point middle = new Point( ( v[ existing[ 0 ] ].X + v[ existing[ 1 ] ].X ) / 2, ( v[ existing[ 0 ] ].Y + v[ existing[ 1 ] ].Y ) / 2 ); dx = v[ existing[ 0 ] ].X - middle.X; dy = v[ existing[ 0 ] ].Y - middle.Y; //line eq: (x-x0)*dy-(y-y0)*dx=0 int value = ( current.X - middle.X ) * dy - ( current.Y - middle.Y ) * dx; int sign = ( value > 0 ? 1 : -1 ); dx = sign * ( v[ existing[ 0 ] ].Y middle.Y ); dy = -sign * ( v[ existing[ 0 ] ].X middle.X ); //move on the S.B. line dist = Math.Sqrt( ( dx * dx ) + ( dy * dy ) ); dx = ( int )Math.Round( dx * 3 * RADIUS / dist ); dy = ( int )Math.Round( dy * 3 * RADIUS / dist ); current.X = middle.X + dx; current.Y = middle.Y + dy; break; default: MessageBox.Show( "Too close to too many points!" ); return false; } return true; } private void recreatePicture() { recreatePicture( false ); } private void recreatePicture( bool saveLabels ) { picBox.Controls.Clear(); Label temp = makeVertex( v[ 0 ].X, v[ 0 ].Y, 0.ToString(), Color.LightBlue ); if( saveLabels )

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada { VL = new List( v.Count ); VL.Add( temp ); } picBox.Controls.Add( temp ); for( int i = 1; i < v.Count; i++ ) { temp = makeVertex( v[ i ].X, v[ i ].Y, i.ToString() ); if( saveLabels ) VL.Add( temp ); picBox.Controls.Add( temp ); //makeLine( i - 1 ); } //makeLine( v.Count - 1, 0, Pens.Black ); -- allow incomplete polylines redrawAllEdges(); checkIntersections(); chkEdit.Checked = ( e.Count > 0 ? ( e[ e.Count - 1 ].v2 == 0 ) : false ); } private void redrawAllEdges() { for( int j = 0; j < e.Count; j++ ) makeLine( e[ j ].v1, e[ j ].v2, Pens.Black ); picBox.Invalidate(); } private int dir = 0; private bool workTriangles; private void cmdAction_Click( object sender, EventArgs e ) { if( dir == 0 ) { area = 0.0; //find the trigonometric circuit: int start = getLowestPoint( v ); int prev = ( start == 0 ? v.Count : start ) 1; int next = ( start + 1 ) % v.Count; recreatePicture( true ); //VL[ 0 ].BackColor = Color.LightGreen; //VL[ start ].BackColor = Color.Pink; //VL[ prev ].BackColor = VL[ next ].BackColor = Color.LightBlue; //Point x = new Point( v[ start ].X, v[ start ].Y ); //x.Offset( 10, 0 ); double anglePrev = getAngle( v[ start ], v[ prev ] ); double angleNext = getAngle( v[ start ], v[ next ] ); VL[ 0 ].BackColor = Color.LightGreen; if( anglePrev > angleNext ) { dir = 1;

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada //VL[ next ].BackColor = Color.Pink; } else { dir = -1; //VL[ prev ].BackColor = Color.Pink; } //compute area through direct formula lblResult.Visible = true; lblResult.Text = useFormula().ToString(); //stepThroughPoints(); currentPoint = next; prevPoint = startPoint = start; } //show step by step tmrWorkDelay.Interval = 400; tmrWorkDelay.Enabled = true; tmrRefresher.Enabled = false; if( !chkShowAll.Checked ) workTriangles = false; } private double useFormula() { double sum = 0.0; for( int i = 0, j; i < v.Count; i++ ) { j = ( i + 1 ) % v.Count; sum += v[ i ].X * v[ j ].Y - v[ j ].X * v[ i ].Y; } return Math.Abs( sum ) / 2; } private double getAngle( Point origin, Point dest ) { int opp = origin.Y - dest.Y; int adj = dest.X - origin.X; if( adj == 0 ) return ( Math.PI / 2 ); double angle = Math.Atan( System.Convert.ToDouble( opp ) / adj ); if( angle < 0 ) angle = Math.PI + angle; return angle; } private double getAngle( Point from, Point corner, Point dest ) { // based on: http://www.vbhelper.com/howto_find_angles.html // Find the dot product AB * BC. Note that AB * BC = |AB| * |BC| * Cos(theta). Point CF = new Point( corner.X - from.X, corner.Y from.Y );

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada Point CT = new Point( corner.X - dest.X, corner.Y dest.Y ); double dotProduct = ( CF.X * CT.X ) + ( CF.Y * CT.Y ); //Find the length of the cross product AB x BC. It equals |AB| * |BC| * Sin(theta) double crossProductLength = ( CF.X * CT.Y ) - ( CF.Y * CT.X ); double angle = 0; if( Math.Abs( dotProduct ) < 0.0001 ) angle = Math.PI / 2; else // angle = Math.Atan( crossProductLength / dotProduct ); /**/ angle = Math.Abs( Math.Atan( crossProductLength / dotProduct ) ); // Test for quadrants 2 or 3. if( dotProduct < 0 ) // angle > PI/2 or angle < PI/2. angle = Math.PI - angle; // Test for quadrants 3 or 4. if( crossProductLength < 0 ) angle = -angle; /**/ return angle; } private int getLowestPoint( List v ) { int result = 0; for( int i = 1; i < v.Count; i++ ) if( ( v[ i ].Y > v[ result ].Y ) || ( ( v[ i ].Y == v[ result ].Y ) && ( v[ i ].X < v[ result ].X ) ) ) result = i; return result; } private void stepThroughPoints() { //for( int i = next, p = start, n; i != start; p = i, i = n ) //{ // // // //

VL[ i ].BackColor = Color.LightBlue; picBox.Refresh(); n = ( i + 1 ) % v.Count; double degrees = 180 * getAngle( v[ start ], v[

//

string info = System.Convert.ToInt32( degrees

i ] ) / Math.PI; ).ToString(); // //thanks to: http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index. htm // double change = Math.Atan2( v[ n ].Y - v[ i ].Y, v[ n ].X - v[ i ].X ) -

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada //

Math.Atan2( v[ i ].Y - v[ p ].Y, v[ i ].X -

v[ p ].X ); // change = 180 * change / Math.PI; // while( change > 180 ) // change -= 360; // while( change < -180 ) // change += 360; // tooltips.SetToolTip( VL[ i ], info + " / " + System.Convert.ToInt32( change ).ToString() ); // if( closingASAP ) // return; // System.Threading.Thread.Sleep( 400 ); // Application.DoEvents(); // if( ( change * dir ) > 0 ) // VL[ i ].BackColor = Color.Pink; // else // VL[ i ].BackColor = Color.LightGreen; //} tmrWorkDelay.Enabled = false; if( currentPoint == startPoint ) { workTriangles = true; tmrWorkDelay.Interval = 2800; tmrWorkDelay.Enabled = ( !chkShowAll.Checked ); remaining = new List( v.Count ); for( int q = 0; q < v.Count; q++ ) remaining.Add( q ); //int max = v.Count, delta = max + dir; //remaining.Add( startPoint ); //for( int q = ( ( startPoint + delta ) % max ); q != startPoint; q = ( ( q + delta ) % max ) ) // remaining.Add( q ); return; } VL[ currentPoint ].BackColor = Color.LightBlue; picBox.Refresh(); int i = currentPoint, n = ( i + 1 ) % v.Count, p = prevPoint; double degrees = 180 * getAngle( v[ startPoint ], v[ currentPoint ] ) / Math.PI; string info = System.Convert.ToInt32( degrees ).ToString(); double change = getAngleAt( p, i, n ); tooltips.SetToolTip( VL[ i ], info + " / " + System.Convert.ToInt32( change ).ToString() ); System.Threading.Thread.Sleep( 200 ); if( ( change * dir ) > 0 ) VL[ i ].BackColor = Color.Pink; else VL[ i ].BackColor = Color.LightGreen; //picBox.Refresh(); //will be done automatically, it seems :| prevPoint = i; currentPoint = n; tmrWorkDelay.Enabled = ( !chkShowAll.Checked ); }

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada private double getAngleAt( int p, int i, int n ) { //thanks to: http://www.euclideanspace.com/maths/algebra/vectors/angleBetween/index. htm double result = Math.Atan2( v[ n ].Y - v[ i ].Y, v[ n ].X - v[ i ].X ) Math.Atan2( v[ i ].Y - v[ p ].Y, v[ i ].X - v[ p ].X ); result = 180 * result / Math.PI; while( result > 180 ) result -= 360; while( result < -180 ) result += 360; return result; } private private private private

int startPoint, currentPoint, prevPoint; List remaining; double area; void tmrWorkDelay_Tick( object sender, EventArgs e

) { if( !workTriangles ) //step through the points, marking concave ones with Pink: stepThroughPoints(); else { lblResult.Text = "tri!"; string output = ""; tmrWorkDelay.Enabled = false; if( remaining.Count == 2 ) { //double final = getTriangleArea( remaining[ 0 ], remaining[ 1 ], remaining[ 2 ] ); //output = area.ToString() + " + " + final.ToString() + " = "; //area += final; //output += area.ToString(); //fillTriangle( remaining[ 0 ], remaining[ 1 ], remaining[ 2 ], Brushes.LightGreen ); //VL[ remaining[ 0 ] ].BackColor = VL[ remaining[ 1 ] ].BackColor = VL[ remaining[ 2 ] ].BackColor = Color.LightGray; //dir = 0; //remaining = new List(); //tmrWorkDelay.Enabled = false; VL[ remaining[ 0 ] ].BackColor = VL[ remaining[ 1 ] ].BackColor = Color.LightGray; dir = 0; remaining = new List(); tmrWorkDelay.Enabled = false; output = "Final area: " + area.ToString(); } else

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada { double current; int max = remaining.Count; for( int i = 0; i < max; i++ ) if( ( !intersectsRemaining( i ) ) || ( max == 3 ) ) { int j = ( i + 1 ) % max, k = ( i + 2 ) % max; current = getTriangleArea( remaining[ i ], remaining[ j ], remaining[ k ] ); Brush fillColor; output = area.ToString(); if( ( getAngleAt( remaining[ i ], remaining[ j ], remaining[ k ] ) * dir ) > 0 ) { output += " - "; area -= current; fillColor = Brushes.Pink; } else { output += " + "; area += current; fillColor = Brushes.LightGreen; } output += current.ToString() + " = " + area.ToString(); fillTriangle( remaining[ i ], remaining[ j ], remaining[ k ], fillColor ); makeLine( remaining[ i ], remaining[ k ], Pens.LightGray ); VL[ remaining[ j ] ].BackColor = Color.LightGray; remaining.RemoveAt( j ); max--; break; } else { //todo: ! show intersection } tmrWorkDelay.Enabled = ( !chkShowAll.Checked ); } lblResult.Text = "Direct result: " + useFormula().ToString() + System.Environment.NewLine + output; } } private void fillTriangle( int i1, int i2, int i3, Brush fillColor ) { Graphics.FromImage( picBox.Image ).FillPolygon( fillColor, new Point[] { v[ i1 ], v[ i2 ], v[ i3 ] } );

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada picBox.Invalidate(); } private bool intersectsRemaining( int i ) { int max = remaining.Count, prev = ( i + max - 1 ) % max; Point dummy = Point.Empty; for( int j = ( i + 3 ) % max, k; j != prev; j = k ) if( intersect( v[ remaining[ i ] ], v[ remaining[ ( i + 2 ) % max ] ], v[ remaining[ j ] ], v[ remaining[ k = ( j + 1 ) % max ] ], ref dummy ) ) { makeLine( remaining[ i ], remaining[ ( i + 2 ) % max ], Pens.Pink ); Graphics.FromImage( picBox.Image ).DrawEllipse( Pens.Red, dummy.X - RADIUS, dummy.Y - RADIUS, 2 * RADIUS, 2 * RADIUS ); picBox.Refresh(); System.Threading.Thread.Sleep( 240 ); return true; } //todo: show return false; } private double { Point p1 //Heron: //double //double //double //double //return

getTriangleArea( int i1, int i2, int i3 ) = v[ i1 ], p2 = v[ i2 ], p3 = v[ i3 ]; a = distance( p1.X, p1.Y, p2.X, p2.Y ); b = distance( p1.X, p1.Y, p3.X, p3.Y ); c = distance( p2.X, p2.Y, p3.X, p3.Y ); sp = ( a + b + c ) / 2; Math.Sqrt( sp * ( sp - a ) * ( sp - b ) * (

sp - c ) ); //determinants: return Math.Abs( ( p2.X * p3.Y - p2.Y * p3.X - p1.X * p3.Y + p1.Y * p3.X + p1.X * p2.Y - p1.Y * p2.X ) / 2.0 ); } } } Exemple de fisiere (poligoane) pentru testare:

test_degrees2. txt

test_degrees1 .txt

test_degrees3 .txt

test_degree s4.txt

test_degrees5 .txt

21 177 203 233 262 291

8 182 243 292 326 172

8 64 26 44 103 108 150 160 73 182 148

6 149 124 62 74 150 22 222 22 110 66

11 179 23 56 55 240 65 61 97 330 142

100 17 17 23 17

22 31 60 103 118

Conf. Dr. Marin Vlada, Universitatea din Bucuresti

www.ad-astra.ro/marinvlada 321 17 338 41 347 74 332 100 349 125 177 136 21 132 44 112 19 79 20 49 55 51 47 16 89 43 97 14 126 21 152 45 21 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15 15 16 16 17 17 18 18 19

35 103 86 52 128 30 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0

296 129 174 83 295 28 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0

222 83 6 0 1 1 2 2 3 3 4 4 5 5 0

166 100 320 51 142 46 342 30 237 11 208 29 11 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 0