Comment déterminer si une série de points (ou de polygone) est dans une région rectangulaire?

Question

Je cherche des messages sur la détermination de la détermination du moment où un point réside dans un polygone ou non et que les réponses sont trop vagues, abstraites ou complexes pour moi. Je vais donc essayer de poser ma question spécifique à ce que je dois faire.

J'ai un ensemble de points décrivant une ligne non directe (parfois un polygone fermé). J'ai une région "Vue" rectangulaire. Je dois déterminer aussi efficacement que possible si l'un des segments de ligne (ou des bordures de polygone) traverse la région de vue.

Je ne peux pas simplement tester chaque point pour voir s'il se trouve dans la région de voir. Il est possible qu'un segment passe à travers la région sans aucun point réellement à l'intérieur de la région (c'est-à-dire que la ligne est dessinée à travers la région).

Voici un exemple de ce que je veux déterminer (le rouge signifie que la fonction doit renvoyer true pour l'ensemble des points, le bleu signifie qu'il devrait renvoyer faux, exemple utilise des lignes droites et des rectangles car je ne suis pas un artiste).

Une autre condition que je veux pouvoir rendre compte (bien que la méthode / la fonction peut être une solution séparée), est de déterminer non seulement si une frontière de polygone passe à travers la région rectangulaire, mais si la région est entièrement englobée par le polygone. La nuance ici est que dans la situation décrite pour la première fois ci-dessus, si je ne suis concerné que par le dessin des frontières, la méthode devrait renvoyer false. Mais dans la situation décrite ici, si j'ai besoin de remplir la région du polygone , j'ai besoin de la fonction pour retourner true. Je n'ai actuellement pas besoin de vous inquiéter de tester des polygones en forme de "Donut" (Dieu merci!).

Voici un exemple illustrant la nuance (le rectangle rouge ne dispose pas d'un seul sommet ou de segment de bordure traversant la région à l'écran, mais il doit toujours être considéré à l'écran):

pour le "n'importe quel segment de ligne ou bordure de polygone passent ou ment à l'écran?" Problème que je sais que je peux trouver une solution (bien que peut-être pas efficace). Même s'il est plus verbeux, les conditions me sont claires. Mais la seconde "est une région de polygone à l'écran?" le problème est un peu plus difficile. J'espère que quelqu'un pourrait avoir une bonne suggestion de faire cela. Et si une solution est facilement mise en œuvre sur l'autre, BOYAA.

Comme toujours, merci d'avance pour toute aide ou suggestion.

PS J'ai une fonction pour déterminer l'intersection de la ligne, mais il semble que la surkilleuse de l'utiliser pour comparer chaque segment à chaque côté de la région à l'écran car la région à l'écran est toujours une simple [0, 0, largeur , hauteur] rectangle. N'y a-t-il pas une sorte de coupe courte?

Answer 1

ps j'ai une fonction pour déterminer intersection de la ligne, mais cela semble être Overkill pour l'utiliser pour comparer chacun segment à chaque côté de l'écran à l'écran région parce que la région à l'écran est Toujours une plaine [0, 0, largeur, hauteur] rectangle.N'y a-t-il pas une sorte de Coupe courte?

Ce n'est pas une overkill, son néccessaire ici.Le seul type de raccourci que je peux penser est des valeurs de codes hards [0, 0, de la largeur, de la hauteur] dans cette fonction et de le simplifier un peu.

Answer 2

Ce que vous cherchez est nommé A Algorithme de détection de collision Une recherche Google vous mèneraà de nombreuses implémentations dans diverses langues ainsi que beaucoup de théorie

Il y a beaucoup de théorie géométrique derrière, du calcul du bissulecteur le plus simple aux triangulations de Delaunay contraintes et des diagrammes de Voronoi (qui ne sont que des exemples).Cela dépend de la forme de l'objet, du nombre de dimensions et de bien sûr le rapport entre l'exactitude nécessaire et le temps informatique fourni; -)

bonne lecture