Intersection de deux polygones convexes

J'ai deux polygones convexes. Les polygones sont mis en œuvre comme cyclique des listes de leurs sommets. Comment trouver une intersection de deux polygones?

InformationsquelleAutor DaZzz | 2012-10-27
  1. 9
    For each edge V1-V2 in the first polygon,
    Let H := Half-plane tangenting V1-V2, with the remaining
        vertices on the "inside".
    Let C := New empty polygon.
    For each edge V3-V4 in the second polygon,
        Let X := The intersection between V3-V4 and H.
        If V3 inside H, and V4 is outside H then,
            Add V3 to C.
            Add X to C.
        Else if both V3 and V4 lies outside H then,
            Skip.
        Else if V3 outside H, and V4 is inside H then,
            Add X to C.
        Else
            Add V3 to C.
    Replace the second polygon with C.

    Cela devrait suffire pour une utilisation simple; de 10 à 20 sommets et de ne pas recalculer à chaque image. — O(n2)

    Voici quelques liens:

    • Êtes-vous sûr que j'ai à ajouter V3 à l'intersection dans le cas 3? Il semble incorrecte.
    • Je l'ai réécrit afin de mieux harmoniser le Sutherland-Hudgman algorithme.
    InformationsquelleAutor Markus Jarderot
  2. 6

    Vous pouvez bénéficier du fait que les deux polygones convexes. Et avec cette connaissance, vous pouvez atteindre O(n) du temps en utilisant ce qui suit balayage de la ligne de l'algorithme:

    Trouver le plus de points dans les deux polygones. Pour des raisons de simplicité, supposons que vous avez pas de bords horizontaux. Créer des listes de bords de contribuer à Gauche et à Droite périmètre d'un polygone.

    Tout en balayant vers le bas de l'avion vous stockez les 4 bords. left_edge_C1, right_edge_C1, left_edge_C2, right_edge_C2. Vous n'avez pas besoin d'aucun complexe à strore les bords, parce qu'il y a seulement quatre d'entre eux. Vous pouvez trouver l'événement suivant point par l'itération sur toutes les options possibles.

    À chaque point d'événement quelques bords apparaissent à la limite de leur intersection. En gros, à chaque point d'événement, vous pouvez avoir l'un des trois cas (voir le pic.).

    Intersection de deux polygones convexes

    • Ce n' event point signifie?
    InformationsquelleAutor Yola
  3. 2

    Outre @Yola est agréable plan de balayage de la description,
    il est linéaire en temps de l'algorithme décrit dans
    Calcul de la Géométrie en C, Chapitre 7. Et C & code Java est disponible (sur le même lien). Il y a plusieurs délicate cas dégénérés, par exemple, lorsque les deux polygones se coupent en un point, ou l'intersection est un segment.

    InformationsquelleAutor Joseph O'Rourke