polygone de l'union sans trous
Im la recherche pour certains assez facile (je sais polygone de l'union n'est PAS une opération facile, mais peut-être que quelqu'un pourrait me diriger dans la bonne direction avec un en facile) algorithme de fusion de deux polygones qui s'intersectent. Les polygones pourraient être concave, sans trous et aussi de sortie de polygone ne devrait pas avoir de trous. Les polygones sont représentés dans le sens antihoraire. Ce que je veux dire, est présenté sur la photo. Comme vous pouvez le voir, même si il y a un trou dans l'union de polygones je n'ai pas besoin de lui à la sortie. D'entrée de polygones pour sûr, sans trous. Je pense que sans trous, il devrait être plus facile à faire, mais encore je n'ai pas une idée.
- J'ai posté la réponse sur la même question ici: stackoverflow.com/a/19475433/904679
Vous devez vous connecter pour publier un commentaire.
Vous pouvez procéder comme ci-dessous:
d'abord l'ajouter à votre ensemble de points de tous les points d'intersection de vos polygones.
alors je voudrais procéder comme graham analyse de l'algorithme de mais avec une plus contrainte.
Au lieu de sélectionner le point de faire la plus haute de l'angle avec la ligne précédente (voir graham scanner pour voir ce que je veux dire (*)), a choisi l'un avec th la plus élevée de l'angle qui faisait partie de l'un des précédente de polygone.
vous obtiendrez une envellope (non convexe) qui décrira votre forme.
Remarque:
il est similaire à trouver l'enveloppe convexe de ses points.
Par exemple graham analyse de l'algorithme de va vous aider à trouver l'enveloppe convexe de l'ensemble des points en O(N*ln(N)) où N est le nombre de points.
pour l'enveloppe convexe de ces algorithmes, et vous pouvez trouver quelques idées.
Espère que cela aide.
remarques:
(*)à partir de wikipedia:
Dans l'enveloppe convexe de l'algorithme que vous avez choisi le point de l'angle que fait le plus grand angle avec la précédente de côté.
De "memory stick" avec votre ancien polygone, il suffit d'ajouter la contrainte que vous devez sélectionner un côté qui existait auparavant.
et vous enlever la contrainte de haveing angle inférieur à 180°
espère que je suis clair,
Je n'ai pas de réponse mais je suis sur le point de s'embarquer sur un problème similaire. Je pense qu'il y a deux étapes qui sont assez important. La première serait de trouver un point sur certains polygones qui se trouve sur le bord extérieur. La deuxième serait de faire une liste des boîtes englobantes pour tous les sommets et de voir laquelle de ces chevauchements. Cela signifie que lorsque vous itérer sur les sommets, vous n'avez pas à faire des tests pour eux tous, seulement ceux qui auront une chance de l'intersection (boîte englobante problèmes sont légers).
Maintenant que vous avez un point à l'extérieur, vous pouvez maintenant parcourir points de connexion jusqu'à ce que vous détecter une intersection. Si vous savez de quel côté est à l'intérieur et qui à l'extérieur (vous devrez peut-être faire un peu de travail sur le premier sommet de savoir ce), vous savez où aller sur l'intersection. Il est alors simplement une question de la commutation des polygones.
Cela devient un peu plus intéressant si vous voulez maintenir que le trou (ce que je fais), dans ce cas, je serais probablement assurez-vous que j'avais utilisé toutes mes intersection des boîtes englobantes. Vous aussi vous ne spécifiez pas ce qui devrait se produire si votre polygones ne se coupent à tous. Mais c'est soit d'aller à être les laisser seuls (ce qui pourrait être un problème si vous vous attendez à un polygone) ou retourner une erreur.