Discussion :

[bigbossjohn95]

Bonjour tout le monde,

Je suis à la recherche d'une fonction ou d'un outil informatique, qui prend en entrée une matrice de points (sommets de la figure), calcule l'air de celui-ci, et le fractionne en N part égales (égales par rapport à l'air de la zone ou part calculer). Donc il revoit en sortie les coordonnées des différentes zones/parts tout simplement.

Bien évidement, étant un programmeur débutant j'ai une idée de l'algorithme, sauf que je n'arrive pas à voir comment calculer l'air d'une figure quelconque. Mon idée serait justement de calculer les aires des différents parts de la figure et dès lors que celle-ci a une aire sensiblement égale à l'air de la figure totale/N alors je prends les coordonnées de cette zone, et je continue la calcul de proche en proche de l'air jusqu'à recouvrir toute la figure.

Bref je me suis dit qu'il pourrait déjà avoir un outil qui le fait, donc si vous en connaissez j'aimerais bien en être informé.

Voila Voila...

Merci d'avance pour vos contributions,

Cordialement

[Flodelarab]

Bonjour

Pas compris.
Tes points sont-ils sur l'intersection d'un quadrillage ?

[wiwaxia]

Bonjour,

La demande, telle qu'elle est exprimée, est en effet incompréhensible:

Tu envisages au départ de "fractionner un solide en plusieurs parts égales", donc de même volume, et il n'est plus question dans l'exposé que de partager une figure en (N) secteurs d'aires identiques ... Alors combien de dimensions pour l'objet étudié: 2 ou 3 ?

D'autre part, comment cet objet est-il délimité ? Par un ensemble de droites ou de plans ? Les données évoquées

... matrice de points (sommets de la figure) ...

correspondraient-elles aux sommets d'un polygone ou d'un polyèdre ?

Enfin comment le découpage est-il effectué ? À l'aide de droites ou de plans parallèles, ou passant par un même point, ou une droite donnée ? Et que sont les coordonnées d'une zone ?

... il revoit en sortie les coordonnées des différentes zones/parts tout simplement ...
... alors je prends les coordonnées de cette zone ...

Des précisions supplémentaires permettraient peut-être d'y voir plus clair ...

[bigbossjohn95]

Les points en questions sont les sommets du polygone à diviser.

Bonjour

Pas compris.
Tes points sont-ils sur l'intersection d'un quadrillage ?

[bigbossjohn95]

Hello, désolé d'avoir été très peu claire. Etant donné qu'une image vaut mieux que milles mots. Considérons donc ce polygone.




Les points A,B,C,D,E,F,G,H sont connus et entrés par l'utilisateur. Ceux-ci constituent notre polygone. On est bien là en 2D. L'outil divise en N parts justement le polygone en question à l'aide des droites comme l'illustre l image. Cet outil renvoie les points P1, P2, P3, P4 des droites qui divisent en parts égales ou sensiblement égales le polygone en question. Notons ici que P2=B pour ce cas précis mais les points doivent être sur le contour du polygone, et ne sont pas forcément les sommets du polygone.

la notion de part égale peu justement renvoie à la notion d'égalité d'air (notion mathématique) ou de surface (notion physique).

Voilà tout. Je pense avoir été un peu plus claire que précédemment.

Alors existe t il un outil ou une fonction qui pourrait faire ce calcul?

[wiwaxia]

Comment les droites de partage (P1P2, P3P4) sont-elle orientées ? Sont-elles parallèles ?

[bigbossjohn95]

Comment les droites de partage (P1P2, P3P4) sont-elle orientées ? Sont-elles parallèles ?

Elles sont orientées. Elles peuvent être verticales ou horizontales tout simplement. Après s'il y'a moyen d'avoir plus (ça j'en doute car ça complexifierai le tout) je suis preneur. Mas bon je me contenterai du peu que je pourrais avoir

[Flodelarab]

- Tes points sont-ils sur l'intersection d'un quadrillage ?
- Les points en questions sont les sommets du polygone à diviser.

J'avais compris. Mais ce n'est pas ma question.

je n'arrive pas à voir comment calculer l'air d'une figure quelconque.

Si tes sommets sont sur l'intersection d'un quadrillage, tu peux appliquer le théorème de Pick :

S = F/2 + I - 1

où S est l'aire de la figure quelconque
F est le nombre de points du quadrillage sur la Frontière
I est le nombre de points du quadrillage à l'Intérieur de la figure

Exemple de cette image prise au hasard sur internet :

F = 10
I = 24
Donc S = 10/2 +24 - 1 = 28 "carreaux carrés"

Pas besoin de formule de calcul d'aire. Compter les points de quadrillage est suffisant.

Comme un ordinateur ne connaît que les nombres entiers, tu devrais toujours pouvoir créer un quadrillage pour appliquer le théorème. (Même si tu n'en as pas initialement)
Charge pour toi de trouver la méthode la plus simple.

[Invité]

hello,

je sais pas si il existe des softs déjà dispo mais tu peux "décomposer" ton pb comme suit.

1) tu triangularises ton polygone (ya déjà des algo pour traiter tous les polygones (sauf ptet ceux qui ont des "trous")
2) la surface est trivialement la somme des aires de tes triangles
3) tu prends un triangle qui n'a qu'un seul "voisin" (ses deux autres cotés font parti des contours du polygone. Tu parcours tes triangles de proche en proche. Quand ta surface cumulée est supérieure à n, tu splittes ton triangle en deux pour avoir "juste ce qu'il faut"
puis rebelotte à partir de l'autre moitié de ton triangle splitté

edit: ne marche pas il faut plus de précision sur la triangulation (dans le cas de polygones concave)

[wiwaxia]

La solution proposée par Flodelarab apparaît la plus appropriée.

Reste à caractériser les points situés à l'intérieur du polygone constitué de la ligne brisée fermée (A₁, A₂, ... , A_n).
Le critère est relativement simple: l'angle orienté (MA₁, MA_k) doit varier de (± 2*Pi) lorsque l'on parcourt la boucle fermée (A₁, A₂, ... , A_n, A₁) en revenant à la position initiale, pour tout point (M) situé à l'intérieur de celle-ci, puisque l'on en fait le tour; la variation est nulle pour tout point à l'extérieur.

Cette fonction existe probablement prête à l'emploi dans de nombreux langages.

[tbc92]

Je ne connaissais pas ce théorème de Pick, et il est ma foi bien sympathique.
Mais ici, il risque de ne pas vraiment aider. SI on prend ta forme exemple, et qu'on nous demande de la diviser en 3, 28/3 ce n'est pas un nombre entier ni demi-entier. On n'aura donc pas de solution en passant par des sommets (X,Y) avec X et Y des nombres entiers.

...En écrivant mon message, je me pose une question : Ok, donc faisons un changement de repère, divisons chaque case du quadrillage en 3x3. La surface est donc maintenant 28x3x3 = 252, et l'objectif est maintenant de trouver 3 formes de surface 84. Mais rien ne nous assure qu'il y a une solution avec des sommets sur le quadrillage.

On a donc besoin de savoir calculer la surface d'une forme même si les sommets ne sont pas entiers.

[wiwaxia]

L'inconvénient est réel, mais n'invalide pas le procédé dans la mesure où l'auteur de la discussion paraît se satisfaire d'une solution approchée:

... Mon idée serait justement de calculer les aires des différents parts de la figure et dès lors que celle-ci a une aire sensiblement égale à l'aire de la figure totale/N alors je prends les coordonnées de cette zone, et je continue la calcul de proche en proche de l'air jusqu'à recouvrir toute la figure ...

... Cet outil renvoie les points P1, P2, P3, P4 des droites qui divisent en parts égales ou sensiblement égales le polygone en question ...

Il est toujours possible de travailler sur des valeurs entières approchées, en multipliant les coordonnées par un facteur approprié (f = 10, 100, 1000 ...). Mais alors apparaît un obstacle beaucoup plus grave, à la réflexion, lorsque le nombre de points à dénombrer augmente: le temps de calcul sera multiplié par f², soit 10² , 10⁴, 10⁶ ...

[Invité]

Mais ici, il risque de ne pas vraiment aider. SI on prend ta forme exemple, et qu'on nous demande de la diviser en 3, 28/3 ce n'est pas un
nombre entier ni demi-entier. On n'aura donc pas de solution en passant par des sommets (X,Y) avec X et Y des nombres entiers.

une possibilité:
Tu tries par x,
Tu tries par y
Tu calcules les distances case à case sur x, idem sur y
Tu multiplies tous tes floats par 1e8(arbitraire...), puis tu roundes
Tu calcules le ppcm de toutes tes distances.
Tu as la largeur d'une case

Maintenant ca donne l'aire (que faut diviser par 1e8*1e8), mais je vois pas trop comment "joliment" découper le polygone -->concave<--
Sans parler des imprécisions et tps de calcul


Par polygone concave j'entends un truc un peu bizarre type:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
x--x--x
x---x  \
     \  x
      x--x

donc bien sûr on peu faire des "sweep" line et concaténer des surface mais l'idée c'est quand même (je pense) d'avoir des polygones sans trou (lol vazy que j'enquille un barycentre et que je dessine ma figure par rapport homothétique de sqrt(nbDivisions)), et si possible(?) convexes en sortie

[wiwaxia]

Autre idée:

Si l'on dispose du critère de situation d'un point quelconque à l'intérieur d'un polygone donné, et si les frontières de partition de la figure sont relativement simples (par exemple, des droites parallèles à l'un des axes), pourquoi ne pas recourir à la méthode de Monte-Carlo ?



Le tirage aléatoire d'un nombre de points suffisamment élevé permettrait de connaître (en valeur approchée) l'aire de la zone interne de chaque tranche, puisque la probabilité de sortie (P_k) d'un point lui est proportionnelle.

On a en effet, en notant (S) l'aire du polygone et (S_k) celle de la zone de rang (k):
P_k = S_k/S ,
et pour (N) points aléatoirement obtenus à l'intérieur de la figure:
N_k /N ~ P_k
la relation étant d'autant mieux vérifiée que le nombre total de points est plus élevé.

On pourrait ainsi travailler directement sur des coordonnées non-entières.

[Invité]

@wiwaxia
comment addressse-tu le cas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
 
 
  +----------------+
  |                |
  +-----------+    |
              |    |
  +-----------+    |
  |                |
  +----------------+

C'est justement pour ca que je radote avec mon concave : D

J'ai une piste consistant à trouver les points dont l'angle est supérieur à 180
à de fait decomposer le polygone en polygones convexes
à creer un arbre mettant en relation ses polygones(considérés comme noeuds) (pas de cycles car je m'impose pas de trous)
et à bidouiller par "proximité" pour fusionner/splitter les noeuds

dans la théorie ca marche, mais dans la pratique ya pas mal de cas à gérer ai-je l'impression

[wiwaxia]

@wiwaxia
comment addressse-tu le cas

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
  +----------------+
  |                |
  +-----------+    |
              |    |
  +-----------+    |
  |                |
  +----------------+

Le critère général a déjà été donné (#10): pour le parcours orienté (ABCDEFGHA), la variation d'angle vaut (+ 2*Pi) pour tout point (P) situé à l'intérieur (et dont la ligne brisée fait le tour dans le sens direct), et 0 pour tout point (Q) situé à l'extérieur.

Il n'y a aucune complication, tant que les arêtes du polygone ne se croisent pas.

La simplicité de l'exemple proposé fait que le problème initial peut être résolu manuellement, et d'une manière rigoureuse.

Et si l'on voulait appliquer le procédé aléatoire précédemment décrit, il suffirait d'utiliser le critère suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
 
FUNCTION Point_Interieur( VAR x, y: Reel): Bool;
  VAR Test1, Test2, Tx1, Tx2, Ty1, Ty2: Bool;
  BEGIN
    Tx1:= ((2<=x) AND (x<=6));      // Valeurs limites estimées
    Ty1:= ((3<=y) AND (y<=9));
    Test1:= Tx1 AND Ty1;
    Tx2:= ((2<=x) AND (x<=4));
    Ty2:= ((5<=y) AND (y<=7));
    Test2:= Tx2 AND Ty2;
    Point_Interieur:= Test1 AND (NOT Test2)
  END;

[Invité]

Trouver si un point est à l'intérieur, ca va...

Comment décomposes-tu la figure (U horizontal ci-dessus) avec des bandes verticales ?
en particulier on voit bien qu'il y a __des unions de bandes__ parce que la bande est __coupée en deux__

[wiwaxia]

...Comment décomposes-tu la figure (U horizontal ci-dessus) avec des bandes verticales ? ...

Par le même procédé que celui décrit pour le polygone (#14).
L'interruption des bandes de gauche par l'échancrure ne change rien au principe du calcul; on y trouvera statistiquement (1/3) de points en moins, par comparaison avec les bandes verticales complètes de même largeur.

[AbsoluteLogic]

Salut, je me mêle à la discussion.
La "pixelisation" peut résoudre le problème, mais pour des performances correctes, il faudrait rester selon des approches plus mathématiques.

En voyant le problème, j'ai imaginé une solution plutot comme l'imaginait galerien69:

hello,

je sais pas si il existe des softs déjà dispo mais tu peux "décomposer" ton pb comme suit.

1) tu triangularises ton polygone (ya déjà des algo pour traiter tous les polygones (sauf ptet ceux qui ont des "trous")
2) la surface est trivialement la somme des aires de tes triangles
3) tu prends un triangle qui n'a qu'un seul "voisin" (ses deux autres cotés font parti des contours du polygone. Tu parcours tes triangles de proche en proche. Quand ta surface cumulée est supérieure à n, tu splittes ton triangle en deux pour avoir "juste ce qu'il faut"
puis rebelotte à partir de l'autre moitié de ton triangle splitté

Je prend l'exemple suivant:


La triangulation est plutot facile: https://fr.wikipedia.org/wiki/Triang...%27un_polygone
On obtient par exemple ça:


On alors peut imaginer un graphe dont les noeuds sont les triangles et les liens relient deux triangles côte à côte:


Si ce graphe était "linéaire", c'est à dire qu'il n'y avait pas de noeud avec strictement plus de 2 arêtes, on pourrait faire ce qu'à dit galerien69 dans l'étape 3. Cependant, ce graphe ne peut pas toujours se ramener dans ce cas (cf exemple). J'ai donc imaginé ce qui suit (l'exemple consiste à divise le polygone en 3):

On commence d'une extrémité du graphe et on génère la premier polygone triangle par triangle.

Quand on arrive à une intersection, il faut prendre une direction, mais il faut pouvoir faire demi-tour quand on arrivera au bout. On partage alors le triangle en deux:

On continue donc en ne prenant que la moitié des triangles:

On calcule l'aire accumulée au fur et à mesure. Et on se rend compte que si l'on rajoute le triangle suivant, on dépasse le tiers voulu de la surface totale. On prend alors uniquement ce qu'il nous faut:

Puis on complète avec le polygone suivant:

et on continue:

Une fois arrivé à une extrémité, il faut faire demi-tour:

et on complète la surface laissée en revenant:

...

Je vous laisse deviner la fin. J'avais préparé les images mais j'ai pas le droit à plus de 12 fichiers joints.

[wiwaxia]

J'ai regardé ce que pouvait donner le procédé aléatoire appliqué au polygone précédent, dont les dimensions exactes ont été reprises:

_

Les tirs ont été restreints au domaine rectangulaire circonscrit au polygone, et défini par:
0 <= x < Xmax = 6 et 0 <= y < Ymax = 6 ;
Le rapport du nombre de points obtenus au nombre total de tirs (N_eff/N_tir) est proche de la valeur théorique (r_th = 28/36 = 7/9 = 0.7778).

Voici les résultats obtenus pour N_eff = 900000 en un peu moins de trois minutes (j'ai dû rectifier la valeur de cette donnée, pour des raisons de lisibilité de l'écran):



Supposons rechercher les deux frontières verticales délimitant trois zones de même aire:
12 bandes de largeur identique découpant le domaine horizontal, dont la valeur est L_x = (Xmax - Xmin) = 6 , chacune d'entre elles correspond à une variation d'abscisse D_x = L_x/12 = 0.5 .
a) La première frontière délimitant la zone de gauche correspondant au tiers de l'aire totale du polygone (S₁ =33.33%*S) se situe ainsi à l'intérieur de la 5^me bande, et admet pour abscisse:
X₁ = 4*0.5 + 05*(33.33 - 28.62)/(35.75 - 28.62) = 2.3303 .
b) la seconde frontière, pour laquelle S - S₃ = 66.67%*S , se trouve dans la 9^me bande, et son abscisse vaut:
X₂ = 8*0.5 + 05*(66.67 - 57.19)/(67.90 - 57.19) = 4.4426 .

La simplicité de la figure autorise des vérifications rigoureuses: on trouve (calculs niveau CM₂ - vérifiez malgré tout, je peux très bien me gourer ):
X_1th = S/(3*L_gauche) = 28/(3*4) = 2.3333 ;
X_2th = L_x - S/(3*L_droite) = 6 - 28/(3*6) = 4.4444 .
Les écarts relatifs restent de l'ordre du millième, ce qui paraît tout à fait acceptable pour une solution graphique.

Les calculs sont probablement plus rapides en langage (C) ou apparentés. La fonction permettant de connaître la situation d'un point par rapport à un polygone (et calculant en fait le nombre de tours effectués par la suite des arêtes autour de ce point) fait appel à des instructions simples:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 FUNCTION Det2V(V1, V2: Ve2D): Reel;
   VAR p, q: Reel;
   BEGIN
     p:= V1.x * V2.y; q:= V1.y * V2.x;
     Det2V:= p - q
   END;

 FUNCTION Pscal2V(V1, V2: Ve2D): Reel;
   VAR Px, Py: Reel;
   BEGIN
     Px:= V1.x * V2.x; Py:= V1.y * V2.y;
     Pscal2V:= Px + Py
   END;

 FUNCTION Norme1(V1: Ve2D): Reel;
   VAR X2, Y2: Reel;
   BEGIN
     X2:= Sqr(V1.x); Y2:= Sqr(V1.y);
     Norme1:= Sqrt(X2 + Y2)
   END;

 FUNCTION AnglePol(W1, W2: Ve2D): Reel;
   VAR De, N1, N2, N1N2, Ps, u, v: Reel;
   BEGIN
     N1:= Norme1(W1);    N2:= Norme1(W2);    N1N2:= N1 * N2;
     De:= Det2V(W1, W2); Ps:= Pscal2V(W1, W2);
     IF (Abs(De)<Abs(Ps))
       THEN BEGIN
              u:= ArcSin(De / N1N2);
              IF (Ps>0) THEN v:= u
                        ELSE IF (u>0) THEN v:= Pi - u
                                      ELSE v:= -u - Pi
            END
       ELSE BEGIN
              u:= ArcCos(Ps / N1N2);
              IF (De>0) THEN v:= u
                        ELSE v:= -u
            END;
     AnglePol:= v
   END;

 FUNCTION Enlacement(W: Ve2D; L_: LstV): Z_08;
   CONST D_Pi = 2 * Pi;
   VAR i, j: Byte; Aij, Arot, s: Reel; Wi, Wj:Ve2D;
   BEGIN
     Arot:= 0;
     FOR i:= 1 TO Npoint DO
       BEGIN
         j:= i + 1;              IF (j>Npoint) THEN j:= 1;
         Wi.x:= L_[i].x - W.x;   Wi.y:= L_[i].y - W.y;
         Wj.x:= L_[j].x - W.x;   Wj.y:= L_[j].y - W.y;
         Aij:= AnglePol(Wi, Wj); s:= Arot + Aij;
         Arot:= s
       END;
     Enlacement:= Round(Arot / D_Pi)
   END;

L'appel conjoint des fonctions ArcSin(.) et ArcCos(.) permet d'éviter les points singuliers où elles ne sont plus dérivables, et le plantage accidentel de l'exécution dû à l'inévitable imprécision du calcul - lorsque l'on obtient fortuitement ArcSin(1.000000000000000001), par exemple.

Le procédé peut être appliqué à des types variés de découpage, utilisant des droites inclinées, des cercles ou des hyperboles (1) ... L'énoncé du sujet ne dit rien sur ce point, d'où la variété des réponses données.

(1) PS: Là, je suis involontairement sorti du cadre de l'énoncé: bigbossjohn95 indique des frontières rectilignes.