[Bug]: Legend overlaps shaded area in fill_between with legend location "best"

[mauroo4]

Bug summary

When using the fill_between function in matplotlib with a legend and specifying the legend location as "best", the legend is not taking into account the shaded area and may overlap with it.

Code for reproduction

import matplotlib.pyplot as plt
import numpy as np

# Example data
x = np.linspace(0, 5, 100)
y1 = 0.5 * np.exp(x) - 1
y2 = 2 * np.exp(x) + 1

# Plotting shaded area
plt.fill_between(x, y1, y2, color='gray', alpha=0.5, label='Shaded Area')

# Set y-axis limit
plt.ylim(-10, 100)

# Adding legend with location "best"
plt.legend(loc='best')

# Show the plot
plt.show()

Actual outcome

Expected outcome

Additional information

No response

Operating system

Windows 11

Matplotlib Version

3.8.0

Matplotlib Backend

module://backend_interagg

Python version

Python 3.11.5

Jupyter version

No response

Installation

conda

[AaronCodesPython]

I would like to take on this issue

[AaronCodesPython]

The problem seems to be in the _auto_legend_data function in legend.py. fill_between does not add anything that is considered in the calculation of "badness"
badness = (sum(legendBox.count_contains(line.vertices) for line in lines) + legendBox.count_contains(offsets) + legendBox.count_overlaps(bboxes) + sum(line.intersects_bbox(legendBox, filled=False) for line in lines))
I will try to resolve this until next Saturday.

[oscargus]

FWIW, if you dig into this, there is also #23323 which appears to have a similar root cause. (Solving one of them is clearly enough to get a PR accepted, but it may be that one can quite easily solve both in one go.)

[ksunden]

Okay, so the result of fill_between is a PolyCollection object. this is technically included in the badness calculation, but only kind of... as what it is actually including is the offset of each element in the PolyCollection. This is the case because a (path)collection is returned by scatter, where the offsets are the center points that should be considered (and also for other kinds of collections, like pcolor, etc)

Perhaps it could be treated as patch and line are? (Though wonder a bit about the performance impact especially for e.g. scatter, this is already a bit of a bottleneck that carries a warning if it takes too long.