How to trace the path of moving points?

48 Views Asked by At

Problem statement :- There is a moving source($s$) and other moving points ($p_{1}.... p_{n}$). There are fixed obstacles and a fixed destination point($d$). In each time stamp I have to query "Is source($s$) visible to destination($d$)"and (and have to find the shortest path. Now I can call the Visibilty Graph function in each time stamp, but that will cost $O(nlogn)$. Instead of these I have thought to apply kinetic data structure.. But the challenge I am facing here is to build the certificates.


I had read in my high school physics about Vector Field. There I had studied usage of divergence,curl. I am thinking here to use the concept of divergence.

My objective will be to find this

$\nabla{v_{i}}$, where $v_{i}$ is the velocity of all the moving particles. I will divide the entire vector space into rectangles and calculate divergence at $t$ = $0$ for each rectagles like this (here it is given as circle although)


We know $\nabla{(vector field)}$ returns a scaler field. After applying $\nabla$ over all the moving points ($p_{i} ... p_{n}$ including source velocity($s_{v}$), we will get scaler values corresponding to each rectangles. From that we will get to know which points have changed their position from the initial stage and it's flow of direction.

Am I thinking correctly? or I am in a wrong direction?