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;
} |
Trouver si un point est dans un polygone
Répondre avec citation
ton poste tu dois marquer quand la bonne réponse tu as obtenu.
Envoyé par ToTo13
Partager