Dynamically prepend or append a path element to content urls? Is there a way I can easily prepend a dynamic element to the beginning of content urls?

For example, I have a /photos-galleries Panel/Page which includes a View showing a bunch of photo galleries. I also have /videos which similarly shows Videos. Both of these items exist in my main nav menu.

If I let the user browse to /cats/photo-galleries then my View uses a contextual filter so it will only show photo galleries tagged with cats. That's fine and I have that working.

Let's say one of those photo galleries has the content url /photo-gallery/kittens-1

If the user clicks on that link and goes to /photo-gallery/kittens-1... then my problem is that the main menu with the /videos link no longer has the cats "filter" on it. I want that filter type to follow the user along.

So, I'd like to rewrite the links to the content generated by the View so that I can change /photo-gallery/kittens-1 to /cats/photo-gallery/kittens-1 that way when the user clicks on that piece of content, I'll still be able to know that I'm filtering my site content according to cats. 

Does that make sense? Any suggestions on how I can rewrite those urls, based on the current page url, being generated by the view?

Or if it is easier, I can append the cats filter tag to the end of the urls and make it /photo-gallery/kittens-1/cats. That would be fine also.

I'm not asking about how to filter the content in the view, I'm asking about rewriting the url of content items generated by that view so that it maintains the same /cats filter.
The hooks that can actually change the links used from Drupal are hook_url_inbound_alter() and hook_url_outbound_alter().
I have never used them to alter a link basing on the URL of the currently viewed page, but in the case of hook_url_outbound_alter() that should not be difficult, as it would require to use arg(); in hook_url_inbound_alter(), it would be more difficult, since you would need to be able to understand in which cases you happened a string to the URL. If the added part comes from a vocabulary of taxonomy terms, that would be probably easier, hoping that the taxonomy terms don't cause any conflict with enabled modules.

Appending the term at the end of the URL would avoid conflicts. It would also be easier to understand when a URL has been modified from your module.