Soit P un simple, mais pas nécessairement convexe, polygone et q un point arbitraire pas nécessairement P.Comment trouver un rayon qui croise un polygone au minimum?
Concevoir un algorithme efficace pour trouver un segment de ligne provenant de q qui coupe le nombre minimum d'arêtes de P
Si q est votre point dans l'espace de 2D, nous pouvons écrire q(x,y). On sait qu'un polyèdre a les arêtes (E), les sommets (V) et les faces (F) dont tous ces termes sont liés à la formule V - E + F = 2 du théorème d'Euler mais le problème s'avère plus facile puisqu'il s'agit d'un polygone . Donc la plaine est de trouver un bord et de calculer le vecteur de direction du point q(x,y) au centre du bord, en faisant cela (et si le polygone est convexe), nous sommes sûrs que ce segment de ligne passera seulement par un bord de P.
le calcul aura besoin d'un peu d'algèbre linéaire, mais il est pas si difficile, par exemple:
1 - trouver la distance d'une ligne à un point (afin que nous puissions trouver le bord le plus proche à utiliser dans ce problème):
2 - En outre, une bonne idée serait de trouver le point sur cette ligne qui est le plus proche de (x0,y0) a des coordonnées:
Lorsque l'équation de la ligne est ax + by + c = 0 et le (x0,y0) est un point arbitraire pas nécessairement dans P.
Donc, maintenant nous pouvons trouver le point k(x,y) sur la ligne tha t est le plus proche du point initial q(x0,y0), en faisant |q-k| = d. Où d est la distance que nous venons de calculer. Après que vous avez déjà tout ce que vous devez trouver un segment de ligne provenant de q qui coupe le nombre minimum d'arêtes de P.
Quelques endroits où vous pouvez étudier et trouver plus sur ce sujet:
@NiklasB. "mais pas nécessairement convexe", c'est ce qu'il a dit, donc ça peut être convexe, et dans ce cas particulier, ma solution sera utile. –
penser à faire cela sur une carte, de sorte que vous pouvez penser comme directions Nord, Sud, Est, Ouest et paliers. Si vous avez un rayon allant de q vers l'infini dans une direction particulière, le fait qu'il coupe une ligne entre les points A et B dépend uniquement du relèvement du rayon et des relèvements de q à A et B: si le relèvement du rayon se situe dans la plage de portée de q à A et le relèvement de q à B, en prenant cela dans la direction de la ligne, puis le rayon coupera la ligne.
Vous pouvez donc réduire cela à un problème plus simple. Imagine que tous les points sont dans un cercle autour de q, et les lignes sont des arcs de ce cercle. Maintenant, vous devez trouver un point sur ce cercle qui est chevauché par le nombre minimum d'arcs.Vous rendrez également la vie beaucoup plus facile si vous divisez chaque arc qui s'étend sur 0 degré en deux à 0, en coupant par exemple. un arc de 320 degrés autour de 40 degrés en un de 320 degrés à 360 degrés = 0, et un de 0 degrés à 40 degrés.
Les bons points candidats pour cela sont des points juste dans le sens des aiguilles d'une montre de chaque point du cercle. Maintenant, ordonnez chaque arc de sorte qu'il soit d'un angle faible à un angle élevé, triez les arcs par angle faible, et travaillez à travers eux dans l'ordre, en incrémentant un compteur lorsque vous voyez le début d'un arc, et décrémentant quand vous voyez le la fin d'un arc (vous n'avez pas à vous soucier des arcs qui recouvrent 0 = 360 degrés parce que vous venez de vous assurer qu'il n'y en a pas). Le point que vous voulez trouver est celui associé à la plus petite valeur du compteur.
En prenant q comme origine des coordonnées, calculez les arguments polaires des sommets. Ceci est fait en temps linéaire.
Ensuite, chaque arête s'étend sur un intervalle d'angles. Pour gérer le bouclage, vous pouvez diviser les intervalles qui traversent la bordure à 360 °.
Vous avez inversé le problème dans une instance où les intervalles 1D se chevauchent. Ceci est facilement résolu en O(N Log(N)) temps.
Sure 'min (ligne_segment) = Ligne (q, q)'. Je suppose que vous ne nous avez pas dit toutes les exigences. – RBarryYoung
ressemble à une question de devoirs – nomistic
bien, problème intéressant, mais personne ici aime les questions du genre c'est le problème, donc faire quelque chose. – Paul