Programmation polygone plan quelconque mais non croisé

Bonjour,

Si vous êtes sûr d'avoir un polygone non croisé (intersection entre deux arêtes) vous pouvez faire comme suit :

1) vous calculez le barycentre de votre polygone en moyennant les coordonnées de tous les sommets
2vous calculez l'aire de chacun des triangles formés par un arrête du polygone comme base et le barycentre en sommet
3) vous faites la somme de toutes les aires, cela te donne l'aire du polygone total
La méthode pose deux problèmes :
1. Elle ne fonctionne que pour des polygones convexes. Hors dans le cas présent il peut être concave.
2. Admettons que le polygone présenté ici ai été convexe. Avec ta méthode, vous calculez l'aire de 6 triangles alors qu'on peut décomposer le figure en 4 triangles.

Maintenant il faut des tests. Découpez plusieurs polygones en un minimum de triangles et analysez la démarche que tu as faite pour essayer de l'implémenter dans ton programme.
Je sais que ce n’est pas si facile à faire qu'à dire mais c'est la méthode la plus efficace et la plus didactique.
En utilisant des aires algébriques ma méthode fonctionne pour des polygones concaves comme convexes.

En revanche j'admets qu'elle ne permet pas de minimiser le nombre de triangle utilisés....

Si on prend comme origine du repère un des sommets du polygone et que l'on trace les triangles à partir de celui-ci plutôt qu'à partir du barycentre

On nomme successivement les sommets du polygone A0, A1, ...An (Ai et Ai+1 sont donc deux sommets successifs du polygone)
Soit A0 l'origine du repère et (xi, yi) les coordonnées associées au sommet Ai.

On calcul l'aire des triangles (A0A1A2), (A0A2A3), ..., (A0An-1An).
l'aire de chacun des triangles se calcul avec un produit vectoriel :
aire de (A0AiAi+1) = 1/2[(xiyi+1)-(yixi+1)]

Donc si on somme sur tous les triangles on obtient bien :


Il est important de bien ordonner les coordonnées de façon à ce que deux coordonnées successives correspondent à deux sommets successifs du polygone.

Le calcul vectoriel et les aires algébriques permettent de régler le problème du recouvrement des triangles dans le cas d'un polygone concave.
Pour A0
Si ton origine est déjà fixé et que les coordonnées de A0 ne sont pas (0,0) vous pouvez adapter la formule comme ça :

xiyi+1 -> (xi-x0)*[(yi+1)-y0]
xi+1yi -> [(xi+1)-x0]*(yi-y0)
Par exemple 5 sommets ,voilà leur coordonnées :
A0(2,3) A1(3,1) A2(4,2) A3(2,5) A4(7.3)
Les coordonnées de A0 sont non nulles, donc tu prends celle de mon dernier message :

1/2∑[(xi−x0)∗(yi+1−y0)−(xi+1−x0)∗(yi−y0)]1/2∑[(xi−x0)∗(yi+1−y0)−(xi+1−x0)∗(yi−y0)]
Après 3 Aspirine on va passer a plus difficile à vous d’adapter
Sans prise de tête
https://www.mathematiquesfaciles.com/figures-aire-de-quelques-polygones_2_18073.htm

#include "Polygone.h"
#include <stdio.h>

bool Inside(int n,POINT pg[],int X,int Y) {
  bool b=false; // (u,v) = point "précédent"
  int x=pg[0].x,u=pg[n-1].x,y=pg[0].y,v=pg[n-1].y;
  for (int i=0; i<n; ++i,u=x,x=pg[i].x,v=y,y=pg[i].y)
    if (((u>X)!=(x>X)) && (Y<(v+(X-u)*(y-v)/(x-u)))) b=!b;
  return b;
}

bool InsideBis(int n,POINT pg[],int X,int Y) {
  bool b=false;
  for (int j=n-1,i=0; i<n; j=i++) // j = index "précédent"
    if (((pg[j].x>X)!=(pg[i].x>X)) && (Y<(pg[j].y+(X-pg[j].x)*(pg[i].y-pg[j].y)/(pg[i].x-pg[j].x)))) b=!b;
  return b;
}

bool Inside(int n,real xx[],real yy[],real X,real Y) {
  bool b=false; // (u,v) = point "précédent"
  real x=xx[0],u=xx[n-1],y=yy[0],v=yy[n-1];
  for (int i=0; i<n; ++i,u=x,x=xx[i],v=y,y=yy[i])
    if (((u>X)!=(x>X)) && (Y<(v+(X-u)*(y-v)/(x-u)))) b=!b;
  return b;
}

real Area(int n,POINT pg[]) {
  real A=0; // j = index "précédent"
  for (int j=n-1,i=0; i<n; j=i++) A+=pg[j].x*pg[i].y-pg[j].y*pg[i].x;
  return A/2;
}

real Area(int n,real xx[],real yy[]) {
  real A=0; // j = index "précédent"
  for (int j=n-1,i=0; i<n; j=i++) A+=xx[j]*yy[i]-yy[j]*xx[i];
  return A/2;
}

real AreaCenter(int n,POINT pg[],real *xCenter,real *yCenter) {
  real A=0,a,xC=0,yC=0;
  for (int j=n-1,i=0; i<n; j=i++) { // j = index "précédent"
    A+=(a=(real)(pg[j].x*pg[i].y-pg[j].y*pg[i].x));
    xC+=a*(pg[j].x+pg[i].x); yC+=a*(pg[j].y+pg[i].y);
  }
  *xCenter=xC/A/3; *yCenter=yC/A/3; return A/2;
}

real AreaCenter(int n,real xx[],real yy[],real *xCenter,real *yCenter) {
  real A=0,a,xC=0,yC=0;
  for (int j=n-1,i=0; i<n; j=i++) { // j = index "précédent"
    A+=(a=xx[j]*yy[i]-yy[j]*xx[i]);
    xC+=a*(xx[j]+xx[i]); yC+=a*(yy[j]+yy[i]);
  }
  *xCenter=xC/A/3; *yCenter=yC/A/3; return A/2;
}

POINT *PolygoneRegulier(int n,int r,int X,int Y) { // n>=3
  POINT *pg=(POINT*)malloc(n*sizeof(POINT));
  real da=(2*(real)3.14159265358979324)/n,a=0;
  for (int i=0; i<n; ++i,a+=da) {pg[i].x=X+(int)(r*cos(a)); pg[i].y=Y+(int)(r*sin(a));}
  return pg; // after use ==> free(pg)
}

POINT *PolygoneEnSpirale(int n,int siz,int X,int Y) { // n: number of "branche"
  POINT *pg=(POINT*)malloc(2*(1+n)*sizeof(POINT));
  for (int i=0,m=2*(1+n)-1; i<=n; ++i,--m) {
    int u=siz*((i&2)?-i:i),v=siz*((i&2)?-i-2:i+2);
    if (i&1) {pg[i].x=pg[m].x=X; pg[i].y=Y-u; pg[m].y=Y-v;} // i impair
    else     {pg[i].y=pg[m].y=Y; pg[m].x=X+v; pg[i].x=X+u;} // i pair
  }
  return pg; // after use ==> free(pg)
}


Polygone.h

#include <math.h>
#include <windows.h>

typedef float real; // ou typedef double real;
// typedef struct tagPOINT {LONG x; LONG y;} POINT;

bool Inside(int n,POINT *pg,int X,int Y);
bool Inside(int n,real xx[],real yy[],real X,real Y);

real Area(int n,POINT *pg);
real Area(int n,real *x,real *y);

real AreaCenter(int n,real x[],real y[],real *xCenter,real *yCenter);
real AreaCenter(int n,POINT pg[],real *xCenter,real *yCenter);

POINT *PolygoneRegulier(int n,int r,int X,int Y);
POINT *PolygoneEnSpirale(int n,int siz,int X,int Y);

#include <stdio.h>
#include "polygone.h"

char str[256]; // Pour MessageBox
struct StructPg { // Simple exemple de structure
  char *title;
  COLORREF color;
  int nbPoint;
  POINT *points;
  real Area,xCentre,yCentre;

  void Paint(HDC hdc) {
    SelectObject(hdc,CreateSolidBrush(color)); Polygon(hdc,points,nbPoint);
    MoveToEx(hdc,(int)xCentre-49,(int)yCentre,0); LineTo(hdc,(int)xCentre+49,(int)yCentre);
    MoveToEx(hdc,(int)xCentre,(int)yCentre-49,0); LineTo(hdc,(int)xCentre,(int)yCentre+49);
  }
  void Calcul(){Area=AreaCenter(nbPoint,points,&xCentre,&yCentre);}
  void Out(){sprintf_s(str,256,"Aire = %.1f, xCentre = %.1f, yCentre = %.1f",Area,xCentre,yCentre);}
};

POINT triangle[]={{50,250},{450,250},{50,400}};
POINT rectangle[]={{30,50},{30+300,50},{30+300,50+150},{30,50+150}};
StructPg pgs[]={{"Triangle",0X0099FF,3,triangle}
  ,{"Spiral",0XFF0000,50,PolygoneEnSpirale(24,8,220,210)}
  ,{"Polygone régulier à 5 côtés",0X0000FF,5,PolygoneRegulier(5,100,350,160)}
  ,{"Rectangle",0X00FF00,4,rectangle}};

LRESULT CALLBACK wndProc(HWND hwnd,UINT mess,WPARAM wP,LPARAM lP) {
  switch(mess) {
    case WM_CREATE: {for (int i=0; i<4; ++i) pgs[i].Calcul();} break;
    case WM_PAINT: {
      PAINTSTRUCT s;
      BeginPaint(hwnd,&s);
      for (int i=3; i>=0; --i) pgs[i].Paint(s.hdc);
      EndPaint(hwnd,&s);
    } break;
    case WM_LBUTTONDOWN: {
      POINT p; GetCursorPos(&p);
      ScreenToClient(hwnd,&p);
      for (int i=0; i<4; ++i) {
        StructPg *pg=&pgs[i];
        if (Inside(pg->nbPoint,pg->points,p.x,p.y))
          {pg->Out(); MessageBox(hwnd,str,pg->title,MB_OK|MB_ICONINFORMATION); break;}
      }
    } break;
    case WM_CLOSE: DestroyWindow(hwnd); break;
    case WM_DESTROY: PostQuitMessage(0); break;
    default: return DefWindowProc(hwnd,mess,wP,lP);
  }
  return 0;
}

HWND SysWin(HINSTANCE hIns,WNDPROC wndProc,char *title,int width,int height) {
  WNDCLASSEX wc;
  wc.cbSize=sizeof(WNDCLASSEX);
  wc.style=CS_HREDRAW|CS_VREDRAW|CS_DBLCLKS;
  wc.lpfnWndProc=wndProc;
  wc.cbClsExtra=0;
  wc.cbWndExtra=0;
  wc.hInstance=hIns;
  wc.hIcon=LoadIcon(NULL,IDI_APPLICATION);
  wc.hCursor=LoadCursor(NULL,IDC_ARROW);
  wc.hbrBackground=CreateSolidBrush(0X00FFFF);
  wc.lpszMenuName=NULL;
  wc.lpszClassName="MyClass";
  wc.hIconSm=LoadIcon(NULL,IDI_APPLICATION);
  if (!RegisterClassEx(&wc)) {
    MessageBox(0,"RegisterClass failed","Error",MB_ICONEXCLAMATION|MB_OK);
    exit(1);
  }
  HWND h=CreateWindowEx(WS_EX_CLIENTEDGE,"MyClass",title,WS_OVERLAPPEDWINDOW,
    CW_USEDEFAULT,CW_USEDEFAULT,width,height,NULL,NULL,hIns,NULL);
  if (!h) {
    MessageBox(0,"CreateWindow failed","Error",MB_ICONEXCLAMATION|MB_OK);
    exit(1);
  }
  return h;
}

int WINAPI WinMain(HINSTANCE hIns,HINSTANCE hPrev,LPSTR lCL,int nCS ) {
  HWND hWnd=SysWin(hIns,wndProc,"Title",500,450);
  ShowWindow(hWnd,nCS);
  MSG m;
  while (GetMessage(&m,NULL,0,0)>0) {TranslateMessage(&m); DispatchMessage(&m);}
  return m.wParam;
}

Perso j'aide beaucoup les étudiants en alimentant les forums, car il n'est pas facile d'étudier dans des amphithéâtres, vu le Covid.
Je trouve que les études sont chères, pour enseigner en Fac cela m’a demandé beaucoup de travail, je suis à la retraite alors j’aide tout le monde n’est pas matheux.
Pour moi l’informatique est un bon outil pour modéliser des équations, j’enseigne l’informatique.
Etant jeune je me posais des questions pourquoi on ne peut pas dépasser la vitesse lumière, Einstein et les scientifiques ont détruit beaucoup de leur travaux car avec l’énergie du point zéro l’homme aurait détruit la planète, il avait raison a 98% mais les 2 % de l’espace-temps n’est pas réglé par la physique que nous connaissant.
Perso je vous le dis vous n’êtes pas sur le bon forum, je vais me prendre une bordée d’injure
Bon courage dans vos études