Diagram Voronoi

In the simplest case, shown in the first picture, we are given a finite set of points {p1, …, pn} in the Euclidean plane. 
In this case each site pk is simply a point, and its corresponding Voronoi cell Rk consists of every point in the Euclidean plane whose distance to pk is 
less than or equal to its distance to any other pk. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. 
The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are 
the points equidistant to three (or more) sites.

Let X {\displaystyle \scriptstyle X} be a metric space with distance function d {\displaystyle \scriptstyle d} . Let K {\displaystyle \scriptstyle K} be a set of indices and let ( P k ) k ∈ K {\displaystyle \scriptstyle (P_{k})_{k\in K}} be a tuple (ordered collection) of nonempty subsets (the sites) in the space X {\displaystyle \scriptstyle X} . The Voronoi cell, or Voronoi region, R k {\displaystyle \scriptstyle R_{k}} , associated with the site P k {\displaystyle \scriptstyle P_{k}} is the set of all points in X {\displaystyle \scriptstyle X} whose distance to P k {\displaystyle \scriptstyle P_{k}} is not greater than their distance to the other sites P j {\displaystyle \scriptstyle P_{j}} , where j {\displaystyle \scriptstyle j} is any index different from k {\displaystyle \scriptstyle k} . In other words, if d ( x , A ) = inf { d ( x , a ) ∣ a ∈ A } {\displaystyle \scriptstyle d(x,\,A)\;=\;\inf\{d(x,\,a)\mid a\,\in \,A\}} denotes the distance between the point x {\displaystyle \scriptstyle x} and the subset A {\displaystyle \scriptstyle A} , then

R k = { x ∈ X ∣ d ( x , P k ) ≤ d ( x , P j ) for all j ≠ k } {\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}}

The Voronoi diagram is simply the tuple of cells ( R k ) k ∈ K {\displaystyle \scriptstyle (R_{k})_{k\in K}} . In principle some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography), but again, in many cases only finitely many sites are considered.

In the particular case where the space is a finite-dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, 2-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. However, in general the Voronoi cells may not be convex or even connected.

In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon R k {\displaystyle \scriptstyle R_{k}} is associated with a generator point P k {\displaystyle \scriptstyle P_{k}} . Let X {\displaystyle \scriptstyle X} be the set of all points in the Euclidean space. Let P 1 {\displaystyle \scriptstyle P_{1}} be a point that generates its Voronoi region R 1 {\displaystyle \scriptstyle R_{1}} , P 2 {\displaystyle \scriptstyle P_{2}} that generates R 2 {\displaystyle \scriptstyle R_{2}} , and P 3 {\displaystyle \scriptstyle P_{3}} that generates R 3 {\displaystyle \scriptstyle R_{3}} , and so on. Then, as expressed by Tran et al^[3] “all locations in the Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidian plane”.

//Diagrame Voronoi		


#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <graphics.h>
#include <conio.h>
#define nmax 40

typedef struct{
  float x,y;
 }vector;

typedef struct{
  float x,y;
 }punct;

typedef struct{
  int v[4];
  }triunghi;

punct p[40];
int n,nt=0;
triunghi T[2*nmax];

// functia de citire a punctelor, maxim 40 de puncte 
void citire(){
 int i;
 printf("n=");
 scanf("%d",&n);
 randomize();
 for (i=0;i<n;i++){
     p[i].x=100+random(300);
     p[i].y=100+random(300);
 }
}

//desenarea punctelor 
void desenare(){
   char c[3];
   int i;
   for(i=0;i<n;i++){
       itoa(i,c,10);
       setcolor(YELLOW);
       circle(p[i].x,p[i].y,1);
       setcolor(RED);
       outtextxy(p[i].x+3,p[i].y+3,c);
   }
   getch();
}

//desenarea triunghiului
void desenare_triunghi(punct A,punct B,punct C,int culoare){
     setcolor(culoare);
     moveto(A.x,A.y);
     lineto(B.x,B.y);
     lineto(C.x,C.y);
     lineto(A.x,A.y);
     getch();
}

//calcularea produsului scalar a doi vectori
float produs_scalar(vector u,vector v){
        return (u.x*v.x+u.y*v.y);
}

//diferenta A-B
vector scade(punct A,punct B){
      vector v;
      v.x=A.x-B.x;
      v.y=A.y-B.y;
      return v;
}

//calcularea distantei dintre doua puncte
float dist(punct a,punct b){
      return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}

//functia pt calcularea tangentei triunhiului ABC
float tangenta(punct A,punct B,punct C){
  vector u=scade(A,B),v=scade(C,B);
  return sqrt(produs_scalar(u,u)*produs_scalar(v,v)-produs_scalar(u,v)*produs_scalar(u,v))/produs_scalar(u,v);
}

//functia ce returneaza centrul cercului circumscris triunghiului(punctul de intersectia a mediatoarelor)
punct centru_cerc(punct A,punct B,punct C){
  vector v1=scade(B,A);
  vector v2=scade(C,B);
  vector v3=scade(A,C);
  punct o;              //centrul cercului
  if(produs_scalar(v1,v3)==0){        //A-drept
      o.x=(B.x+C.x)/2;
      o.y=(B.y+C.y)/2;
      return o;
  }
  if(produs_scalar(v1,v2)==0){        //B-drept  
      o.x=(A.x+C.x)/2;
      o.y=(A.y+C.y)/2;
      return o;
  }
  if(produs_scalar(v2,v3)==0){
      o.x=(B.x+A.x)/2;
      o.y=(B.y+A.y)/2;
      return o;
  }
  float ta=tangenta(B,A,C),tb=tangenta(A,B,C),tc=tangenta(A,C,B);
  float suma=ta+tb+tc;
  o.x=((tb+tc)*A.x+(ta+tc)*B.x+(ta+tb)*C.x)/(2*suma);
  o.y=((tb+tc)*A.y+(ta+tc)*B.y+(ta+tb)*C.y)/(2*suma);
  return o;
}

//functia pt desenarea semidreptei cu originea in M
void semidreapta(punct M,vector v,int culoare){
  float tmax=200,past=0.5;
  float t;
  for(t=0;t<=tmax;t+=past){
    putpixel(M.x+t*v.x,M.y+t*v.y,culoare);
    }
}

//determinarea semnului 
int semn(punct a,punct b,punct c){
  double d1;
  d1=(double)(b.x-a.x)*(c.y-a.y)-(double)(c.x-a.x)*(b.y-a.y);
  if (d1>0)return 1;
           else if(d1<0)return -1;
	           else return 0;
}

//trasarea mediatoarelor
void mediatoare(punct A,punct B,punct C,int culoare){
//deseneaza mediatoarea laturii BC
   vector v;
   if (semn(A,B,C)>0) {
       v.x=C.y-B.y;
       v.y=-(C.x-B.x);
      }
      else{
            v.x=-(C.y-B.y);
            v.y=C.x-B.x;
	  }
   float t=sqrt(produs_scalar(v,v));
   v.x=v.x/t;v.y=v.y/t;
   punct O=centru_cerc(A,B,C);
   semidreapta(O,v,culoare);
}

void mediatoare_triunghi(punct a,punct b,punct c,int culoare){
   mediatoare(a,b,c,culoare);
   mediatoare(b,c,a,culoare);
   mediatoare(c,a,b,culoare);
}

//verifica daca un punct este in interiorul unui triunghi
int punct_in_triunghi(punct M,punct A,punct B,punct C){
  if (semn(A,B,C)>0)
      return (semn(M,A,B)>=0&& semn(M,B,C)>=0 &&semn(M,C,A)>=0);
      else  return (semn(M,A,B)<=0&& semn(M,B,C)<=0 &&semn(M,C,A)<=0);
}

//testeaza daca M se afla in interiorul cercului circumscris, returneaza 1 daca e, 0 altfel
int punct_in_cerc(punct M,punct A,punct B,punct C){
     punct O=centru_cerc(A,B,C);
     float raza=dist(O,A);
     if(dist(O,M)<=raza) return 1;
             else return 0;
}

//triangulare Delaunay
void triangulare_delaunay(){
    int i,j,k,l,ok;
    for(i=0;i<n-2;i++)
       for(j=i+1;j<n-1;j++)
	  for(k=j+1;k<n;k++){
	     ok=1;
	     l=0;
	     while(ok && l<n){
		 if(l!=i&&l!=j&&l!=k&&punct_in_cerc(p[l],p[i],p[j],p[k])) ok=0;
		 l++;
	     }
	     if(ok){
	      desenare_triunghi(p[i],p[j],p[k],3);
	      //mediatoare_triunghi(p[i],p[j],p[k],4);
	      nt++;
	      T[nt].v[1]=i;
	      T[nt].v[2]=j;
	      T[nt].v[3]=k;

	     }
	  }
}


//functia care verifica latura 

void verifica_latura(int i0,int j0,int k0,int i,int culoare){
    //io,jo,ko sunt virfurile triunghiului i
    //functia analizeaza latura iojo
      int ok=0,j,ind,k;
      punct O1=centru_cerc(p[i0],p[j0],p[k0]);
      for(j=1;j<=nt;j++){
	ind=0;
	if(j!=i){
		for(k=1;k<=3;k++){
			if(T[j].v[k]==i0) ind++;
			if(T[j].v[k]==j0) ind++;
			}
		if(ind==2){
			punct O2=centru_cerc(p[T[j].v[1]],p[T[j].v[2]],p[T[j].v[3]]);
			setcolor(culoare);
			line(O1.x,O1.y,O2.x,O2.y);
			ok=1;
			}
		}
      }
if(ok==0) mediatoare(p[k0],p[i0],p[j0],culoare);
}

//functia care realizeaza diagrama Voronoi

void diagrama_voronoi(int culoare){
int i,i0,j0,k0;
for(i=1;i<=nt;i++){
	i0=T[i].v[1];j0=T[i].v[2];k0=T[i].v[3];
	verifica_latura(i0,j0,k0,i,culoare);
		verifica_latura(j0,k0,i0,i,culoare);
	verifica_latura(k0,i0,j0,i,culoare);
	}
}

void main(){
   citire();
   int gm, gd=DETECT;
   initgraph(&gd, &gm, "C:\\borlandc\\bgi");
   desenare();
   triangulare_delaunay();
   diagrama_voronoi(RED) ;
   getch();
}

35,669 total views, 1 views today