Comment déterminer quand deux points mobiles deviennent visibles l'un par rapport à l'autre?

Question

Supposons que j'ai deux points, Point1 et Point2. À un moment donné, ces points peuvent être à des positions différentes - ils ne sont pas nécessairement statiques. Point1 est situé à une certaine position à l'instant t, et sa position est définie par les fonctions continues x1 (t) et y1 (t) donnant les coordonnées x et y à l'instant t. Ces fonctions ne sont pas différentiables, elles sont construites par morceaux à partir de segments de ligne.

Point2 est le même, avec x2 (t) et y2 (t), chaque fonction ayant les mêmes propriétés.

Les obstacles qui pourraient empêcher la visibilité sont des polygones simples (et immobiles).

Comment puis-je trouver les points de délimitation pour la visibilité? En d'autres termes, il existe deux types de limites: les points deviennent visibles et deviennent invisibles. Pour une frontière i visible, il existe quelques ε> 0, tels que pour tout nombre réel a, a ∈ (i-ε, i), Point1 et Point2 ne sont pas visibles (ie le segment de droite qui relie (x1(a), y1(a)) à (x2(a), y2(x)) traverse certains obstacles).

Pour b ∈ (i, i + ε) ils sont visibles.

Et c'est l'inverse pour devenir invisible.

Mais puis-je trouver une telle limite précise, et si oui, comment?

Answer 1

Il est facile de check if two lines intersect. Utilisez-le pour vérifier l'intersection de la ligne (p1, p2) et de chaque arête de polygone. Si vous avez une intersection, la ligne (p1, p2) est obstruée par un obstacle.

Si vous avez besoin d'un intervalle de temps (où p1 et p2 ne sont pas en ligne de mire), vous pouvez effectuer la vérification ci-dessus pour différentes valeurs de t (de préférence avec des différences relativement faibles) et entre un "visible-t" et un "invisible-t" vous pourriez faire une recherche binaire jusqu'à ce que vous atteigniez un seuil assez petit, comme eps.

Answer 2

Les changements de visibilité ne peuvent se produire que lorsqu'un sommet d'obstacle se trouve sur le segment de ligne Point1-Point2. Donc, calculer les temps de toutes ces collisions de vertex. (Intuitivement, cela devrait être un test relativement simple puisque les points de terminaison se déplacent linéairement, mais je vais devoir passer à travers pour vérifier, je vais essayer plus tard et revenir.)

Vous avez maintenant un ensemble fini de temps de collision. Pour chacun d'entre eux, vérifiez si le segment intersecte d'autres bords d'obstacles. Si c'est le cas, ce bord gouverne la visibilité et l'heure n'est pas une limite de visibilité. Si ce n'est pas le cas, vous pouvez vérifier la visibilité à (t- & epsilon;) et (t + & epsilon;) pour déterminer la nature du changement.

Vous devez disposer d'une stratégie sur certains cas de bords, par exemple lorsque le sommet est sur la ligne de connexion pour un tronçon continu. Je pense que tout cela se résume probablement à la question de savoir si les points (et les bords vus sur la fin) sont opaques.

Mise à jour

Le processus d'identification des collisions de sommet est en effet assez simple, il implique simplement la résolution d'une équation du second degré un peu fastidieux en t.Vous devez le faire pour chaque sommet pour chaque segment de mouvement par morceaux, donc je suppose que le coût sera O (n * m) pour n sommets et m périodes. (Si les périodes des fonctions de position ne sont pas synchronisées, vous devez les subdiviser pour qu'elles le deviennent.)

Considérer une seule période de temps, et l'échelle t doit être comprise dans la plage [0,1]. Chaque fonction de position est linéaire en t, donc définissez x1(t) = x10 + x1m * t (c'est-à-dire, x10 est la valeur de départ et x1m est le gradient), et de même pour y1(t), x2(t) et y2(t). Pour un sommet V = (vx, vy), le temps (le cas échéant) à laquelle V est situé sur le segment de droite reliant les points est donnée par l'équation At^2 + Bt + C = 0, où:

A = x1m * y2m - x2m * y1m 
B = vx * (y1m - y2m) + vy * (x2m - x1m) 
    + x10 * y2m - x20 * y1m 
    + y20 * x1m - y10 * x2m 
C = vx * (y10 - y20) + vy * (x20 - x10) 
    + x10 * y20 + x20 * y10 

(ou quelque chose Compte tenu de la probabilité d'erreurs de transcription. à l'arrière de l'enveloppe, je suggère fortement fonctionner par vous-même avant la mise en œuvre!)

Si cela a une vraie solution dans l'intervalle [0,1], votre oncle Bob. Si elle se réduit à 0 = 0 ou quelque chose, alors le point est sur la ligne tout le temps, auquel cas vous devez considérer votre politique.

Answer 3

Ok, j'ai une image plus claire du problème maintenant, et inspiré par la suggestion @walkytalky, voici une réponse plus ellaborate.

Vous avez mentionné que p1 et p2 voyagent le long de segments de ligne droite. Je ne sais pas si ces segments sont alignés d'une manière telle que p1 et p2 démarrent toujours de nouveaux segments en même temps. Cependant, vous pouvez toujours découper un segment de ligne en deux segments de ligne (avec la même pente) de sorte que p1 et p2 démarrent toujours de nouveaux segments de ligne en même temps.

Supposons p1 se déplace le long ligne A-B et p2 voyages (en même temps) le long de C-D en tant que paramètre t va de 0 à 1. (Autrement dit, au moment t=0.5, p1 est au milieu de A-B et en p2 le milieu de C-D.)

En laissant Ax et Ay désignent les coordonnées x et y du point A (et de même pour B, C et D) nous pouvons exprimer p1 et 01.230.en fonction de t de la façon suivante:

p1(t) = (Ax + t*(Bx - Ax), Ay + t(By - Ay)) 
p2(t) = (Cx + t*(Dx - Cx), Cy + t(Dy - Cy)) 

(. Par exemple, lorsque t=0, Ax + t*(Bx - Ax) est évaluée à Ax, et quand il évalue à t=1Bx)

Pour trouver « un Vertex- est-passe par entre-p1-et-p2" -temps nous procédez comme suit:

pour chaque sommet obstacle v=(Vx, Vy) nous devons trouver un t afin que p1(t), p2(t) et v sont alignés les uns avec les autres.

Cela peut être fait en résolvant les équations suivantes (deux équations et deux inconnues, t et k):

Vx=p1(t).x + k*(p2(t).x - p1(t).x) 
Vy=p1(t).y + k*(p2(t).y - p1(t).y)` 

Si k est compris entre 0 et 1, le sommet du polygone v est en fait entre la ligne (étendue) A-B et la ligne (étendue) C-D. Si t est également compris entre 0 et 1, le sommet v est effectivement passé par la ligne p1-p2 pendant le temps que les points parcourent ces segments (puisque lorsque t est, disons, 1.3, les points seront déjà sur de nouveaux segments).

Une fois que tous les temps "a-vertex-passe-par-entre-p1-et-p2" ont été calculés, il est facile de déterminer le reste. (C'est-à-dire, déterminer si c'est un "devenir-en-vue", "devenir-hors de vue" ou "aucun" type de dépassement):

Pour toutes les paires t0 et t1 temps de passage, vous vérifiez si la ligne p1((t1-t0)/2)-p2((t1-t0)/2) est libre d'intersections avec un bord de polygone. S'il est libre d'intersections, les points seront en visibilité directe sur toute la période (t0-t1), sinon ils seront hors de vue pendant toute la période (puisque aucun autre sommet n'est passé durant cette période).