1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
|
#define Maxs(a, b) (((a) > (b)) ? (a) : (b))
#define Mins(a, b) (((a) < (b)) ? (a) : (b))
#define next(i) (i+1) % np
short np;
struct Crd Sommets[Max_Sommets];
struct Crd S1[Max_Sommets+1];
static short Where_do_we_have_to_insert_point ( double Px, double Py )
{
short n1, i_next;
double D1, D2, d2;
double P1=1e100;
for ( short i=0; i < np; i++)
{
i_next = next(i);
// doite allant du point i au point i_next
double dx, dy;
dx = Sommets[i_next].x-Sommets[i].x;
dy = Sommets[i_next].y-Sommets[i].y;
if ( fabs(dx) < 1e-40) // dx=0 => droite verticale
{
double Ud = 0; // on suppose le point entre Yi et Yi_next
if ( Py > Maxs( Sommets[i_next].y,Sommets[i].y))
Ud = Py - Maxs( Sommets[i_next].y,Sommets[i].y); // correction si trop haut
else
if ( Py < Mins( Sommets[i_next].y,Sommets[i].y)) // correction si trop bas
Ud = Mins( Sommets[i_next].y,Sommets[i].y) - Ud;
d2 = sqr(Sommets[i].x-Px) + sqr(Ud);
}
else
if ( fabs(dy) < 1e-40) // dy=0 => droite horizontale
{
double Ud = 0; // on suppose le point ente Xi et Xi_next
if ( Px > Maxs( Sommets[i_next].x,Sommets[i].x) )
Ud = Px - Maxs( Sommets[i_next].x,Sommets[i].x); // correction trop à droite
else
if ( Px < Mins( Sommets[i_next].x,Sommets[i].x)) //correction trop à gauche
Ud = Mins( Sommets[i_next].x,Sommets[i].x) - Ud;
d2 = sqr(Sommets[i].y-Py) + sqr(Ud);
}
else // droite oblique y= px + q
{
double p, q, al, ax, ay;
p = dy / dx;
q = Sommets[i].y - p*Sommets[i].x;
d2 =sqr(Py - p*Px - q) / (1+ sqr(p)); // distance^2 point droite si elle etait non bornée
//Point A => A' tel que AA' orthogonal au segment (Pi,Pinext)
// A' = (Px+al, Py-al/p)
// si A' est sur la droite (Pi,Pinext) alors
// Py-al/p= p*(Px+al) + q => al(p+1/p) = Py-q-p*Px
al = (Py - q - p*Px) / (p + 1/p); // droite oblique => p !=0 et p != infini, p+1/p toujours !=0 dans R
// d'où A'(ax,ay)
ax = Px + al;
ay = Py - al/p;
// A' est il entre les 2 extremitées du segment?
if ((ax-Sommets[i].x)*(ax-Sommets[i_next].x) + (ay-Sommets[i].y)*(ay-Sommets[i_next].y) > 0)
{
// produit scalaire > 0 => A' hors de Pi, Pi_next ( angle =0 => cos=1)
D1 = sqr(ax - Sommets[i].x) + sqr(ay-Sommets[i].y);
D2 = sqr(ax - Sommets[i_next].x) + sqr(ay-Sommets[i_next].y);
d2 += Mins(D1,D2); // correctif à d2
}
}
if ( d2 < P1 )
{
P1=d2;
n1 = i;
}
}
return
n1; // on insere entre n1 & n1+1 % np
}
double area ( bool b , double Px, double Py)
{
if (b)
{
double d2 = 0;
for ( short i=0; i < np; i++)
d2 += (Sommets[i].y + Sommets[(i+1) % np].y ) * ( Sommets[i].x-Sommets[(i+1)%np].x);
return
fabs(d2) / 2;
}
else
{
short n1;
n1 = Where_do_we_have_to_insert_point(Px, Py);
// le point entré est le plus proche du seg n1, (n1+1)%np)
if ( n1 >=0 )
for (short i=0; i <= n1; i++ )
S1[i] = Sommets[i];
S1[n1+1].x = Px;
S1[n1+1].y = Py;
if ( n1 < np-1 )
for (short i=n1+1; i < np; i++ )
S1[i+1] = Sommets[i];
double d2 = 0;
for ( short i=0; i <= np; i++)
d2 += (S1[i].y + S1[(i+1) % (np+1)].y ) * ( S1[i].x-S1[(i+1)%(np+1)].x);
return
fabs(d2) / 2;
}
}
double Aire_Polygone(void) // Sommets[0..np-1].x et .y
{
double A = area(true,0,0);
return A;
}
bool Inside(double X, double Y) // Sommets[0..np-1].x et .y, on teste le point (X,Y)
{
double A = area (false,X, Y);
double B = Aire_Polygone();
return
A < B;
} |
Partager