Point à l'intérieur polygone composé

Question

J'ai vu beaucoup d'algorithmes pour le point à l'intérieur du polygone. Ce que je appris à ce jour est venu de ce site: http://alienryderflex.com/polygon/

Le meilleur algorithme ressemble habituellement à ceci:

var inside = false; 
for (int i = poly.Count - 1, j = 0; j < poly.Count; i = j++) 
{ 
    var p1 = poly.Vertices[i]; 
    var p2 = poly.Vertices[j]; 

    if ((p1.Y < testY != p2.Y < testY) && //at least one point is below the Y threshold and the other is above or equal 
     (p1.X >= testX || p2.X >= testX)) //optimisation: at least one point must be to the right of the test point 
    { 
     if (p1.X + (testY - p1.Y)/(p2.Y - p1.Y) * (p2.X - p1.X) > testX) 
      inside = !inside; 
    } 
} 

Mais segments de polygone composé peut être soit une ligne droite ou un arc. Les segments d'arc sont définis par les 2 points normaux et un renflement est utilisé pour trouver le centre et le rayon de l'arc. Les 2 points sont utilisés pour trouver l'angle de début et de fin de l'arc. En utilisant le point de test Y et Math.Asin((testY - arc.Center.Y)/arc.Radius) je peux trouver l'angle auquel la ligne de test croise le cercle. Lorsque la ligne d'essai croise le cercle, il y a 2 points d'intersection. Après cela, je teste l'angle pour savoir si les points d'intersection sont sur l'arc.

Mes résultats sont assez bons jusqu'à maintenant, sauf que lorsque le point de test arrive, ils ont exactement le même y qu'un vertex. Il sera compté pour les 2 segments adjacents. Pour un segment normal ce cas est évité par le si (p1.Y < testY != p2.Y < testY)

Je ne peux pas trouver une application similaire pour le polygone composé pour la partie de l'arc. Est-ce que quelqu'un a déjà dû faire quelque chose de similaire ou avoir quelque indice?

Answer 1

Avec cette ligne

p1.Y < testY != p2.Y < testY 

vous ne comptez que les segments qui approchent la ligne de requête à partir du bas (ou la traverser). Et c'est exactement ce que vous devez faire pour les arcs. Pour cela, il peut être souhaitable de diviser l'arc en parties monotones (par rapport à l'axe des ordonnées). Dans votre exemple, l'arc inférieur est déjà monotone. L'arc supérieur devrait être divisé en deux (le long d'une ligne verticale à travers son centre). Ensuite, vous avez minY et maxY pour chaque segment et vous pouvez appliquer la formule ci-dessus:

minY < testY != maxY < testY 

Sinon, vous pouvez vérifier si l'intersection est à la fin de l'arc (égale coordonnée y) et évaluer si l'arc se poursuit vers le bas basé sur l'angle et la direction de l'arc. Mais en fonction de la mise en œuvre, cela pourrait poser des problèmes de stabilité numérique. La première option (avec division en parties monotones) est probablement plus facile à implémenter. Et il généralise à d'autres primitifs.