Répondre à la discussion
Affichage des résultats 1 à 5 sur 5

Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée



  1. #1
    Chani

    Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée


    ------

    Définition :

    Poly ligne plane fermée :
    - C’est une succession de segments de droites et d’arcs de cercle consécutifs.
    - Ils sont tous inscrits dans un même plan de l’espace 3D.
    - Le premier point et le dernier de la polyligne sont confondus.
    - Sur tout le pourtour, il y a continuité de la bordure.
    - La polyligne peut être aussi bien concave que convexe.
    - Elle permet de définir deux surfaces, l’une intérieure et l’autre extérieure à la bordure.
    - Il n’y a pas de coupure dans la polyligne et ses éléments ne s’intersectent pas (exemple de deux segments se coupant est impossible)
    - Un point peut appartenir à plusieurs éléments de la polyligne (exemple : un 8 est possible si des portions de la polylignes ne se coupent pas)
    - Il n’y a pas de trou dans la polyligne.

    Point projeté :
    - Point de l’espace 3D projeté sur le plan de la Polyligne

    Question :

    Comment déterminer si un point projeté est à l’intérieur ou à l’extérieur d’une polyligne plane fermée ?

    Réponse recherchée :

    - Une aide pour trouver une solution ou
    - un algorithme ou
    - une indication sur un livre, un article, un lien internet parlant de ce sujet ou
    - un code informatique écrit en C

    -----

  2. Publicité
  3. #2
    vuibert

    Re : Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée

    L'algo classique consiste a prendre une demi-droite qui part du point considere. On peut prendre la demi-droite horizontale pour simplifier les calculs. Ensuite, on compte le nombre d'intersections entre la demi-droite et la polyline en examinant tous les segments. Si ce nombre est pair, le point est en dehors, sinon il est dedans.

  4. #3
    Lambda0

    Re : Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée

    Bonjour

    Cette méthode est théoriquement correcte mais son implémentation est plus compliquée qu'il n'y parait. Une implémentation directe par des calculs en virgule flottante de précision finie ne permet pas d'écrire un programme qui fonctionne : on peut toujours trouver des cas dégénérés qui mettent en défaut l'algorithme.
    Dans le cas d'un contour polygonal, le problème se résoud rigoureusement en calculant en arithmétique rationnelle.
    Si le contour contient des arcs de degré supérieur, je ne suis pas sur qu'il existe un algorithme mathématiquement prouvé basé sur cette méthode.

    Donc: cette méthode est simple à programmer à un niveau élémentaire, mais n'est pas d'une fiabilité absolue dans la pratique. C'est plus ou moins acceptable suivant l'application, mais en général suffisant pour du graphique par exemple, en traitant les cas pathologiques les plus courants.

    Autre méthode : décomposition du domaine 2D en quadtree
    Cette méthode nécessite un précalcul et un stockage de données, mais l'algorithme de classification d'un point est ensuite très rapide et très stable.

    Il existe de nombreux algorithmes. Le choix du meilleur dépend de ce que l'on cherche à optimiser : temps de précalcul, temps de classification d'un point, occupation mémoire, stabilité, etc.
    Donc, la bonne réponse dépend de l'application.
    Il y a des rapport de recherche sur le sujet sur le site de l'INRIA (entre autre) : www.inria.fr

    A+

  5. #4
    Stephen

    Re : Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée

    Citation Envoyé par Chani
    - une indication sur un livre, un article, un lien internet parlant de ce sujet ou
    A un niveau avancé, c'est de la topologie différentielle (licence de maths je dirais). Voir Milnor : Topology From the Differentiable Viewpoint. Ca généralise ce que dit Vuibert

  6. A voir en vidéo sur Futura
  7. #5
    Chani

    Re : Déterminer l’intérieur / l’extérieur d’une polyligne plane fermée

    Je remercie toutes les personnes qui auront bien voulu me donner quelques conseil. Je suis en train de tester une méthode en calculant la somme des angles du point à tous les sommets de la polyligne.

Discussions similaires

  1. Déterminer une équation de parabole
    Par nancy54 dans le forum Mathématiques du collège et du lycée
    Réponses: 12
    Dernier message: 14/10/2007, 22h50
  2. Isolation par l’extérieur à l’intérieur ?
    Par alphaval dans le forum Habitat bioclimatique, isolation et chauffage
    Réponses: 8
    Dernier message: 21/09/2007, 00h24
  3. déterminer une tension
    Par scholasticus dans le forum Électronique
    Réponses: 2
    Dernier message: 31/08/2007, 21h07
  4. determiner une configuration absolue
    Par trinity9 dans le forum Chimie
    Réponses: 6
    Dernier message: 04/11/2005, 07h41
  5. déterminer une coordonnée ...
    Par Tix dans le forum Mathématiques du supérieur
    Réponses: 24
    Dernier message: 12/12/2004, 12h53