Caractériser tout point à l'intérieur d'un triangle quelconque

[Rhydderch]

Bonsoir,


Pour mes recherches personnelles en programmation^a, je dois caractériser tout point présent à l'intérieur d'un triangle. J'ai alors choisi de commencer par un cas plus ou moins simple^b que voici.

Soit un triangle quelconque dans un référentiel , tel que^c:

• soit confondu avec l'origine du repère;
• le segment ait une longueur connue;
• le segment ait une longueur connue;
• l'angle vale et soit compris dans l'intervalle ;
• se situe sur l'axe des abscisses.

J'ai fait quelques calculs tout ce que je trouve c'est la longueur du segment , la position de et la valeur des angles et . Cependant je ne vois pas comment aller loin et donc parvenir à mes fins. Auriez-vous un ou plusieurs indices, s'il vous plaît ?


Merci d'avance.

______________________________ ___
^a : On s'occupe comme on peut...
^b : En fait, pas tant que ça...
^c : Al-Kashi ! Quand tu nous tiens !
-----

[Tryss]

On peut le faire en passant par le produit vectoriel (c'est d’ailleurs la meilleure méthode d'un point de vue programmation).

En effet, si le point M est à l’intérieur du triangle ABC, les angles AMB, BMC et CMA ont la même orientation, tandis que si le point M est à l’extérieur du triangle un des 3 angles à une orientation opposée.

Or l'orientation de l'angle est donné par le signe de la composante en z d'un produit vectoriel. En utilisant les formules pour calculer le produit vectoriel, il vient que si





sont de même signe, alors M est à l’intérieur du triangle, sinon il est à l’extérieur.

Cette méthode permet d'éviter d'utiliser autre chose que des opérations de base, ce qui la rend très efficace.

[Rhydderch]

OK. Dans le genre «*simple*», on ne fait guère mieux. Et vu que j'ai tendance à chercher midi à quatorze heures...

Je suppose d'une part que pour que M soit à l'intérieur du quadrilatère il faut que les équations

• ,
• ,
• et
• 

soient de même signe, et d'autre part que cette formule puisse être généralisée à tous les polygones.

[albanxiii]

Bonjour,

J'ai une idée, mais je ne sais pas si elle sera d'application plus simple que la méthode de Tryss.

Si un point est à l'intérieur d'un triangle, il peut être considéré comme le barycentre des sommets, effectés de poids (masses) de même signe.

Mais je n'ai pas creusé....

[A voir en vidéo sur Futura]

[Tryss]

Malheureusement cette formule ne se généralise que pour les polygones convexes.

Pour le cas général, on pourrait (c'est une des solutions) trianguler le polygone, puis tester si il est dans un des triangles composant le polygone

[Rhydderch]

OK. Merci beaucoup, Tryss.

[Tryss]

Albanxii :

Ta méthode est en effet possible, cela revient à résoudre le système :



Puis de regarder les signes de a, b et c

C'est plus lourd en calcul que ma méthode mais c'est possible (il y a cependant un cas limite à traiter à part si A, B et C sont alignés).

En dimension 3 (ou supérieure), je pense que c'est une bonne méthode

[albanxiii]

Re,

C'est plus lourd en calcul que ma méthode mais c'est possible (il y a cependant un cas limite à traiter à part si A, B et C sont alignés).

Merci pour avoir fait les calculs, je dois dire que j'ai été occupé à d'autres tâches depuis.

Si on vivait dans un espace (c'est peut-être le cas, mais on ne perçoit que 3 dimensions, en tout cas, c'est mon cas ) à n dimensions.... d'accord. Je crrois qu'il vaut mieux rester sur votre méthode plus élégante.

Bonne journée.

[pgs.dev]

Bonjour,
Je sais que la discussion est un peu vieille, mais il existe aussi une autre méthode qui marche avec tous les polygones convexes dont on connait l'aire.
Si A est l'aire du polygone convexe, alors un point à l'intérieur du polygone vérifiera une propriété toute simple : la somme des aires des triangles consécutifs de base l'aire d'une arête et de sommet opposé le point M sera égale à l'aire du polygone.
Il suffit donc d'itérer pour les arêtes consécutives le calcul de l'aire d'un triangle (qu'on peut faire de manière simple par base*hauteur/2, ou en utilisant une formule adaptée aux données qu'on a, comme la formule de Héron, ou celle de Kahan, ou la moitié de la norme du produit vectoriel, etc. cf. https://fr.wikipedia.org/wiki/Aire_d'un_triangle ), et de faire la somme.

C'est une méthode pouvant n'utiliser que des opérations de base, et qui est facilement codable pour un polygone convexe de taille quelconque.

[joel_5632]

bonjour

@pgs.dev

Es-tu sur qu'il n'y a pas des points à l'extérieur tels que le calcul d'aire indiqué donnerait aussi l'aire du polygone ?
D'ailleurs, faut-il sommer des aires algébriques (signée) ou pas ?

EDIT: Non, à priori pour un point extérieur on devrait obtenir une aire supérieure

[Dlzlogic]

Bonjour,
La gestion des zones est une chose difficile.
Concernant le test "point intérieur ou pas à une zone ?", j'ai adopté la méthode suivante : je calcule toutes les intersections de la droite passant par l'abscisse du point à tester et parallèle à l'axe des Y, avec les côtés du polygone.
Le nombre de points d'intersection avec le polygone est forcément pair. Il suffit de tester l'ordonnée du point à tester par rapport aux ordonnées des points d'intersections.
Si le nombre des intersections est impair, alors la droite passe par un sommet du polygone. Il suffit par exemple de faire le même calcul, mais avec une droite parallèle à l'axe des X.

[pgs.dev]

- il faut utiliser des aires absolues, non algébriques
- aucun point à l'extérieur ne permet d'obtenir la même aire.

La limitation est qu'il faut nécessaire un polygone convexe.

Pour une utilisation informatique, il faut tout de même prévoir une marge d'erreur liée aux arrondis, donc calculer l'erreur maximale possible de l'algorithme implémenté, et définir une politique de choix (inclusion ou exclusion). Mais ça devient une considération pratique, et pas théorique.

Un exemple en Java :

    /** @return the surface of a triangle given by its vertices A, B and C*/
    protected double surfaceTriange(final GeoPoint2D A, final GeoPoint2D B, final GeoPoint2D C) {
        final double xA, xB, xC, yA, yB, yC;
        xA = A.getAbscissa();
        xB = B.getAbscissa();
        xC = C.getAbscissa();
        yA = A.getOrdinate();
        yB = B.getOrdinate();
        yC = C.getOrdinate();
        // from the norm of the cross product AB x AC : ||AB x AC||/2
        return Math.abs((xB - xA) * (yC - yA) - (xC - xA) * (yB - yA)) / 2;
    }

    /**
     * @param vertices is an oriented list of vertices (consecutive list of vertices : one vertex
     *            after the other).
     * @return the surface of the convex polygon defined by <b>vertices</b>.
     */
    protected double surfacePolygon(final List<GeoPoint2D> vertices) {
        // A convex polygon can always be divided in n-2 triangles, where n is the number of
        // vertices. The surface of the polygon is the sum of the triangles surfaces.
        // for instance, for pentagon ABCDE, the surface is the sum of triangles ABC+ACD+ADE.
        double totalSurface = 0;
        final GeoPoint2D A = vertices.get(0);
        for (int edgeIndex = 1; edgeIndex < vertices.size() - 1; edgeIndex++) {
            final GeoPoint2D B = vertices.get(edgeIndex);
            final GeoPoint2D C = vertices.get(edgeIndex + 1);
            totalSurface += surfaceTriange(A, B, C);
        }
        return totalSurface;
    }

    /**
     * @param M is a {@linkplain GeoPoint2D point}
     * @param vertices is an oriented list of vertices (consecutive list of vertices : one vertex
     *            after the other).
     * @return true of point <b>M</b> is inside the convex polygon defined by <b>vertices</b>.
     */
    protected boolean isInConvexPolygon(final GeoPoint2D M, final List<GeoPoint2D> vertices) {
        boolean result = false;
        if (!vertices.isEmpty()) {
            final List<GeoPoint2D> fakePolygonM = new ArrayList<>();
            fakePolygonM.add(M);
            fakePolygonM.addAll(vertices);
            fakePolygonM.add(vertices.get(0));
            // for instance, for quadrilateral ABCD, to compute the sum of triangles MAB+MBC+MCD+MDA
            // is the same than compute the surface of (fakely) supposed convex polygon MABCDA.
            // We take margins (1/1000) in order to avoid too strict computation
            result = surfacePolygon(fakePolygonM) <= (surfacePolygon(vertices) * 1.001);
        }
        return result;
    }   

    // To avoid to compute many times the same surface
    /** 
     * @param M is a {@linkplain GeoPoint2D point}
     * @param vertices is an oriented list of vertices (consecutive list of vertices : one vertex
     *            after the other).
     * @param surface is the surface of the convex polygon defined by <b>vertices</b>
     * @return true of point <b>M</b> is inside the convex polygon defined by <b>vertices</b>.
     * @see #isInConvexPolygon
     */
    private boolean dirtyIsInConvexPolygon(final GeoPoint2D M, final List<GeoPoint2D> vertices, final double surface) {
        boolean result = false;
        if (!vertices.isEmpty()) {
            final List<GeoPoint2D> fakePolygonM = new ArrayList<>();
            fakePolygonM.add(M);
            fakePolygonM.addAll(vertices);
            fakePolygonM.add(vertices.get(0));
            result = surfacePolygon(fakePolygonM) <= (surface * 1.001);
        }
        return result;
    }

Notez que j'utilise un "pseudo polygone convexe" pour faire de la réutilisation de fonctions.
Pour être complètement fonctionnel, ce code implique :
- l'existence d'une classe GeoPoint2D fournissant les méthodes getAbscissa() et getOrdinate().
- l'accessibilité à java.lang.Math, java.util.ArrayList, java.util.Arrays et java.util.List.