Partiționarea în triunghiuri a unui poligon

Enunţul problemei

Se dă un poligon oarecare şi se cere împărţirea acestuia în triunghiuri prin trasarea diagonalelor interioare corespunzătoare.

Modelarea problemei

- Poligon

- Trasarea diagonalelor

Etapele problemei

OBS Există teorema de colorare a hărţilor : orice graf plan poate fi colorat cu cel mult 4 culori.

Lemă: Orice poligon cu n laturi ( ) admite cel puţin un unghi convex.

Poligonul: ne situăm în - planul euclidian văzut atât ca spaţiu punctula cât si ca spaţiu euclidian.

Definiţie: Se numeşte poligon regiunea închisă din plan delimitată de o curbp poligonală simplă şi închisă.

Teoremă: Orice poligon cu n vârfuri ( ) admite o partiţie în triunghiuri

Demonstraţie : Se face inducţie matematică după numărul de vârfuri.

Afirmaţia este adevărată pentru n = 3.

Pentru n > 3 :

Fie un poligon cu n+1 vârfuri n>4.

Fie o diagonală în poligonul P, atunci putem considera partiţia lui P în două poligoane separate de acea diagonală.

Conform ipotezei de inducţie există o partiţie in triunghiuri prin diagonale în poligonul P’ şi o partiţie în triunghiuri prin diagonale în poligonul P’’.

Notăm D’= mulţimea diagonalelor ce realizează partiţonarea lui P’.

D’’=mulţimea diagonalelor ce realizează partiţionarea lui P’’.

determină o partiţie în triunghiuri a poligonului iniţial prin diagonala d.

OBS: Demonstrarea acestei teoreme furnizează o primă metodă pentru determinarea partiţiilor in triunghiuri a unui poligon. Algoritmul este de tipul divide et impera:

1. se determină o diagonală d1.

2. se împarte poligonul în două poligoane .

3. se apelează algoritmul pentru P’ şi P’’.

Testul de oprire: Când numărul de vârfuri al poligonului rezultat este trei .

Definiţie : Un vârf are statutul de ureche dacă vârfurile adiacente formează o diagonală.

Două vârfuri formează o diagonală dacă:

- Aceasta nu intersectează laturile poligonului;

- Aceasta se află in interiorul poligonului ;

- Aceasta nu interseactează alte diagonale din interiorul poligonului;

Algoritmul de partiţionare în triunghiuri prin eliminarea urechilor

1. se determină o ureche;

2. se elimină urechea respectivă;

3. se obţine un nou poligon având cu un vârf mai puţin;

4. se reia algoritmul până când au mai rămas doar 3 vârfuri.

Pentru fiecare vârf al poligonului se determină dacă este ureche sau nu:

Odată găsită o ureche se continuă algoritmul cu următorul vârf până când se găsesc n-3 varfuri care au statutul de ureche.

Programul in C

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# include <graphics.h>

# include <math.h>

typedef struct{

int x,y;

}punct;

typedef struct {

punct p;

int succ;

int pred;

int cul;

}poligon;

poligon varf[200];

int legatura[200][100];

int aria(int a,int b,int c){

if ((varf[b].p.x-varf[a].p.x)*(varf[c].p.y-varf[a].p.y)-(varf[c].p.x-varf[a].p.x)*(varf[b].p.y-varf[a].p.y) < 0 ) return -1;

else if ((varf[b].p.x-varf[a].p.x)*(varf[c].p.y-varf[a].p.y)-(varf[c].p.x-varf[a].p.x)*(varf[b].p.y-varf[a].p.y) == 0 ) return 0;

else return 1;

}

int inter_proprie(int a,int b,int c,int d){

if ( (aria(a,b,c)*aria(a,b,d)<0) && (aria(c,d,a)*aria(c,d,b)<0) ) return 1;