# How to build a data-structure for a moving points

Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is that path?

totalV = all points including source, moving points ,fixed destination point, obstacle points. ObsE= {Edges of obstacles}

What have I come up with? At $$t = 0$$, I have used a regular Visibilty Graph function (i.e VG(totalV,obsE)) which has given me $$E_v$$ (i.e $$E_v$$ is the set of edges from $$v_i$$ to $$v_j$$,[$$v_i$$ & $$v_j$$ $$\in$$ totalV] if and only if they are visible to each other. After getting the $$E_v$$ I am using the ShortestPath $$fun^c$$.If Source --> Destination path exists it will give me the path.

At $$t= 1$$ , points have been moved from it's previous position following the trajectory(which is given).Now how could I find the path from S--> D wrt the previous frame.

• I don't understand what you mean by "at what time source can get a path to destination". You can always get from the source to the destination no matter where the source is (assuming the source is not inside the obstacle). What is your actual question? The points $S,A,B$ seem irrelevant -- they are not mentioned in the problem statement, so I'm not sure why they are listed.
– D.W.
Jan 17 at 16:12
• @D.W. No I can't always get from the source to the destination. It may happen at a certain point of time that no points are visible to destination . and Obstacle is solid one not hollow. Jan 17 at 17:03
• That doesn't make any sense to me, it seems like you can always follow a path that detours around the obstacle.
– D.W.
Jan 17 at 17:21
• "it seems like you can always follow a path that detours around the obstacle."- How it seems? Jan 17 at 17:31
• Please state the actual question in the title. It helps people find the questions they're looking for. Jan 18 at 9:31