As pointed out by Tom, this could end up being an expensive query, though from my anecdotal evidence from trying this on a rather large database (granted, only a handful of post types), I think you could write a decently sufficient query.
If you’re using caching to store the categories, that could also alleviate some of the potential performance issues.
Here’s the query I used for testing (but with my own post types):
SELECT DISTINCT
tt.taxonomy
FROM
wp_term_taxonomy tt
JOIN
wp_term_relationships tr ON( tr.term_taxonomy_id = tt.term_taxonomy_id )
WHERE
tr.object_id IN ( SELECT ID FROM wp_posts WHERE post_type IN ( 'list', 'of', 'normal', 'post', 'types' ) );
Converting this to something more portable for WordPress:
<?php
global $wpdb;
$post_types = [ 'list', 'of', 'normal', 'post', 'types' ];
$placeholders = array_fill( 0, count( $post_types ), '%s' );
$sql = <<<SQL
SELECT
tt.taxonomy
FROM
{$wpdb->term_taxonomy} tt
JOIN
{$wpdb->term_relationships} tr ON( tr.term_taxonomy_id = tt.term_taxonomy_id )
WHERE
tr.object_id IN ( SELECT ID FROM {$wpdb->posts} WHERE post_type IN ( {$placeholders} ) );
SQL;
$query = $wpdb->prepare( $sql, $post_types );
$results = $wpdb->get_col( $query );