Get post terms with hierarchical relationships

I’m having a hard time getting a set of selected terms in a custom taxonomy presented in a specific way.

I have a hierarchical taxonomy ‘places’ and a post with the tagged terms:

England (x)
  - London (x)
     - Venue1 (x)
France (x)
  - Paris (x)
     - Venue2
Germany
  - Berlin (x)
     - Venue3 (x)

I need to print out:

myPostTitle : Venue1 (London - England)
              Paris (France)
              Venue3 (Berlin)

My problem is, that I can’t find a function that will return the tagged terms, in a manner that reflects the hierarchical relationships. I need to be able to determine:

• Which terms are the actual ‘venues’ (the ‘lowest’ tagged child in each of the hierarchies)
• What parents and grandparents of those ‘last children’ to include.

I’m outside the loop, and would prefer not to run setup_postdata(). I have the post ID.