I have a graph of vertices and connected edges as shown in the image below.
I have a function that iterates from every single vertex and finds closed loops in order to find all polygons in the graph.
Here is an example of my graph which has found all the polygons in the graph:
Now if i add a new segment (seen in red)
What i currently do is basically wipe my array of all polygons found, and find all polygons again.
But this is clearly not needed because not all polygons are going to need to be updated here.
How can I optimise my function so I can avoid checking the entire graph again?
Its obvious P2 doesn't exist anymore, its been cut into two new polygons. And P3 and P4 only needs an edge inserted into its array of edges. And P1 is unchanged.
I only want to check the minimum amount of vertices that will find all the new polygons and changes to pre-existing ones. But I am not sure which vertices have to be rechecked besides the two new ones added on each end of the red edge added to the graph.