Advanced search form with filters for custom taxonomies and custom fields?

I’d like to build an advanced search form for a specific custom post type, having filters for that custom type’s custom fields and custom taxonomies AND for another custom post type’s properties (fields and taxonomies) that is linked (with a relationship type custom field) to the first custom post type.
To be more clear I also made a scheme/mock-up of the data structure and the desire outcome.

I have recently started off with WP’s custom post types, fields and taxonomies, I love it so far but to make the best of it I’d like to be able to search it properly. Do I need to do it manually (if so, how?), is there a plugin that addresses this?

PS. If it matters, I’m using Advanced Custom Fields and Custom Post Type UI
PS2. Not sure if this is a How-To or Wp-Advanced worthy thread.