Supprimer des trous dans un polygone

Question

J'ai un polygone déterminé par un tableau de points.

Ce polygone se croise en faisant quelques trous dans le polygone lui-même. Mes questions sont les suivantes: Comment puis-je omettre ces trous et obtenir les points extérieurs du polygone?

Ou ce qui sera le même et probablement plus facile: Quel algorithme pour vérifier si un point est à l'intérieur d'un polygone dois-je utiliser pour détecter les points dans les trous du polygone comme points à l'intérieur?

Merci à l'avance,

/roger

Answer 1

D'abord, trouver toutes les intersections des arêtes, ajoutent ces intersections à la liste des sommets, et de diviser les arêtes à ces intersections. Ensuite, commencez par un sommet qui est évidemment externe (par exemple le "plus à droite") et tracez le contour, en ajoutant les arêtes et les sommets aux ensembles de résultats. Tracer le contour est simplement aller le long du bord avec un angle minimum par rapport au dernier bord.

Answer 2

Vous pourriez vouloir trouver la coque convexe de tous les points de votre polygone. Un algorithme pour faire ceci est Graham-Scan avec la complexité O (nlgn). De Cormen:

Let Q be the set of all points in your polygon 
Graham-Scan(Q) 

1 let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie 
2 let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0 
     if more than one point shares the same polar angle, keep the farthest point 

3 let S be an empty stack 
4 PUSH(p0, S) 
5 PUSH(p1, S) 
6 PUSH(p2, S) 
7 for i = 3 to m 
8 while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn 
9  POP(S) 
10 PUSH(pi, S) 
11 return S 

S contient maintenant tous les points externes de votre polygone. Vous devrez faire des calculs polaires, mais c'est assez simple. Pour trier par ordre polaire, trier tous les points sur leur cotangente avec le point le plus bas. J'oublie le code pour vérifier un virage à droite, mais c'est sur Internet si vous cherchez juste pour Graham-Scan. J'espère que cela t'aides!