Autoscaling has fundamental problems · Issue #7413 · matplotlib/matplotlib · GitHub

#6915 brings to light two problems with autoscaling:

It looks very inefficient: every plotting method in _axes adds an artist to the axes and then calls autoscale_view, occasionally with arguments. autoscale_view then does a complete autoscaling operation, going through all of the artists that have been added up to that point. Logically, it seems like the autoscaling should be done only before a draw operation, not every time an artist is added.
Beyond the apparent inefficiency, it doesn't work right for collections. add_collection calls self.update_datalim(collection.get_datalim(self.transData)) to get dataLim. This uses the present transData to calculate the size in data units of objects that have sizes and/or positions that may be specified in screen or axes units. Then the subsequent call to autoscale_view uses those positions to modify the view limits. But this changes transData so that the intended result cannot be achieved--when drawn, the sizes and locations in data units will not be what they were calculated to be when the view limits were set. The mismatch will grow as additional artists are added, each one potentially changing the data limits and the view limits. Usually we get away with this with no one noticing, but not always. plt.yscale('log') after plt.scatter() behaves unpredictably in this example. #6915 shows that subsequently changing the scale of an axis, e.g. linear to log, can wreck the plot.

The first could be fixed by adding (yet more) state to the Axes in the from of a 'autoscale_the_nexttime_you_draw` flag? I suspect that the 'autoscale in plot method' makes sense from the POV of interactive use where almost every command is followed by a draw anyway.

The second sounds like we need to clear a cache when ever we change the scale (and maybe the view limits?).

No, I think the second is a much more fundamental problem--more along the lines of "you can't get there from here". A constraint engine might be needed to get it right. I need to spend more time thinking about it to be sure, though.

Shouldn't the autoscaling "simply" be done at draw time (if autoscaling is on at that time, of course)? (In interactive mode, each command is followed by a draw, so it's just the same.) At that time, you know what your scale is, so you can

map each artist to axes coordinates -- including, say, collections whose offset is in data coordinates but whose own shape is effectively in axes coordinates.
find the limits and apply the margins (note that we also thus drop the need to hacks such as minpos (cf BUG: fix autoscale_view with log scale and margins #7410) and can properly support e.g. logit scale (Logit scale #3753 (comment))).

I think this should solve all the issues? (Not that it'd be that easy to implement such a large refactor.)

Yes, that's part of my point: draw time seems like the right time, so the strategy would be to accumulate all necessary information along the way, and then use all of it at once. I think this still requires an algorithm change, though; I'm not sure that the present update_datalim is doing the right thing, given that it is using the existing transData to calculate sizes in data coordinates, which are then used to modify the dataLim and transData, at which point the sizes in data coordinates are no longer what they were assumed to be. It seems like either an explicit inverse calculation or an iterative approach is needed. But I might be confused.

No, my strategy is to not accumulate any information along the way. You simply wait until draw time when the correct transData is known, and do all the calculations at that point (this is assuming of course that the limits have not been explicitly set).

You will then need an explicit inverse when converting the limits-including-margins back to data space, but that's not a problem as scales are explicitly invertible.

I think you are misunderstanding what I am saying, and the nature of the problem. It is a nonlinear minimization problem. Mathematically, it cannot be solved with a simple single-pass algorithm like the present one. I don't have time to write this out in more detail right now, but we can return to it.

OK, I'll wait for your writeup then.

Here is an attempt to show the structure of the problem for a single axis. It is a hybrid of math and code notation.

We have N data locations, x[i], in data coordinates.
At each location there is a marker of radius S[i], in 0-1 axes coordinates.
We want to have margins, M0 on the left and M1 on the right; for example, they might both be 0.05, meaning we want the plotted symbols to extend from 0.05 to 0.95 in axes coordinates.
There is a transform function, f, mapping data coordinates to axes coordinates. It is a function of x0, the data coordinate at the left side of the axis, and x1, the data coordinate at the right side of the axis. Then the location of the center of the symbol in axes coordinates is X[i] = f(x[i], x0, x1).
The problem is to find the values of the two parameters,x0, x1 that satisfy the two conditions of the desired end result:
- min(X[i] - S[i]) == M0
- max(X[i] + S[i]) == 1 - M1
or, more explicitly:
- min(f(x[i], x0, x1) - S[i]) == M0
- max(f(x[i], x0, x1) + S[i]) == 1 - M1

This problem needs to be solved simultaneously for all N plot elements involved in the autoscaling. I think that the only way to do it is iteratively. In the special case where allS[i] == 0, the problem is easier because both sides can be inverse-transformed (x[i] = F(X[i], x0, x1)), so the transform is only applied to the right hand side (scalars), and the left-hand side can be evaluated to a scalar. Then the conditions collapse to two equations in two unknowns, and iteration is not required. Alternatively, we note that because the transform has an inverse, the extreme values of x[i] occur at the same two indices as the extreme values of X[i], again collapsing the min/max conditions down to two equations in two unknowns.

I think the solution to this problem for now is to stop trying to be so ambitious. Let's disable the present non-functional attempt to solve the optimization, and instead rely on the simple mechanism of specified margins to reduce the incidence of cases where autoscaling fails to include all parts of all symbols.

I am 👍 on doing margins completely in dataspace and accepting clipped symbols.

How much of this logic can we push down into the scales / is pushed into the scales? If we could delegate all of the margin computation there it would greatly reduce how badly we have to special case for log / symlog / etc and would let third-party scales (attn @phobson ) deal with margins (up to just ignoring them) in a way that makes the most sense for that scale.

I don't think the situation is that bad.

Indeed, the transform f is not arbitrary; unless I am mistaken, it is always of the form X[i] = (g(x[i]) - g(x0)) / (g(x1) - g(x0)) where g does not depend on the bounds (e.g. g(x) = log(x) for log scale).

Thus, let us write y[i] = g(x[i]), m = g(x0), t = 1 / (g(x1) - g(x0)). As we know the inverse of g, our problem is equivalent to finding m and t so that

min (t * (y[i] - m) - S[i]) = M0 (1)
max (t * (y[i] - m) + S[i]) = 1 - M1 (2)

Note that the t * m term is the same everywhere, so we can get rid of it by subtracting the equations, and first solve the equation in t,
(max (t * y[i] + S[i])) - (min (t * y[i] - S[i])) = 1 - M1 - M2 (3)
(we can later retrieve m by plugging in t in (1).

To be honest, I had missed the fact that different elements could have different S; in my mind, equation (3) simplified further to
max (t * y[i]) - min (t * y[i]) = 1 - M1 - M2
which can immediately be solved simply by finding the lowest and highest ys.

If we want to keep things simple, as suggested by @tacaswell, I would rather set S to be the largest of all sizes; this will ensure that symbols are never clipped, and will compute the margins correctly in the common case where all symbols have the same size.

Let's come back to the general case of eq. (3). The expression on the right, seen as a function of t, is a piecewise linear function; the max and the min terms both have at most N - 1 "break points"; their difference has at most 2 (N - 1) break points; if we can find these break points (with the knowledge of which affine functions is extremal on each interval), we can then solve the linear system on each interval and finally find the solution.

A quick googling suggests that these break points can be found in O(N log N) by a variant of merge sort (Handbook of combinatorial optimization, Du & Pardalos, p455) (this looks like it should be a "classical" optimization problem anyways).

Implementing any version of this, whether with variable S or with a maximal S, requires a single calculation done at draw time with all x and S (many of which may be zero) stored. (Yes, it can be broken up into two parts, one for the cases of non-zero S and another for the trivial case of zero S, but this doesn't change the need to at least gather all of the non-zero S cases for processing in one go.)
The "use the maximum S" strategy would give reasonable results in most uses of scatter, but would fail if the user included a large patch (via Patch or a Collection) in a data location not near the data limits.
Anything along these lines is much too complicated to try to get into v2.x. For 2.0 we need to either accept the present flawed algorithms, or back out their usage--everywhere, or perhaps only in some instances.
Even for later versions, we need to think in terms of cost/benefit, risk/reward, for introducing fancier algorithms. It's worth considering in the larger context of major refactoring, unification of scales and norms, use of a layout engine, etc. But it might be relatively low priority, and it might be in incremental improvement that should come after several others.
For now, all of this is a distraction from what we desperately need to do: release a "good enough" 2.0, and then some real improvements in a 2.1, again in a 2.2, etc.

I agree with pushing out a "good enough" release. What about setting S = min(S)? This would, again, cover the case where all the markers have the same size (which is likely by far the most common case), with "relatively" little complexity.

That still requires introducing a new algorithm and strategy for handling the autoscaling, pushing it to the draw stage. (Probably this should be done anyway, but it's not an immediate priority.) And much of the point of scatter is to handle cases where size is variable. Same with quiver. Variable size is a common case, and it is the reason the present flawed approach was taken.

I think the complete marker is supposed to be part of the data limits. However, get_datalim only seems to work if you draw the figure first. That is, the following works fine better, due to the figure being drawn before obtaining the data limits

import matplotlib.pyplot as plt

fig, ax = plt.subplots()

sc = ax.scatter([0, 1], [0, 1], s=8000)

fig.canvas.draw()
ax.update_datalim(sc.get_datalim(ax.transData))
ax.autoscale()

plt.show()

However, even in this case the marker is only shown completely due to the margins adding some extra space.

Right, and if you keep calling it, xlim keeps changing, converging on a solution if there is a solution...

import matplotlib.pyplot as plt

fig, ax = plt.subplots()

sc = ax.scatter([0, 1], [0, 1], s=8000)

xmin = []
for i in range(20):
    fig.canvas.draw()
    ax.update_datalim(sc.get_datalim(ax.transData))
    ax.autoscale()
    print(ax.get_xlim())
    xmin += [ax.get_xlim()[0]]

(-0.2151878284989904, 1.2151878284989903)
(-0.24703510991539251, 1.247035109915392)
(-0.2558090743822613, 1.255809074382261)
(-0.2582263121822271, 1.2582263121822272)
(-0.2588922641134946, 1.258892264113495)
(-0.25907573467429973, 1.2590757346742996)
(-0.25912628103523305, 1.259126281035233)
(-0.259140206618675, 1.2591402066186748)
(-0.25914404313371997, 1.2591440431337202)

If there is no solution (s=400000) the limits never converge...

(-1.8256753925786404, 2.825675392578641)
(-4.619776234706715, 5.619776234706715)
(-10.109973046555703, 11.109973046555705)
(-20.89779450896202, 21.89779450896202)
(-42.095047702798034, 43.09504770279803)
(-83.74604689011363, 84.74604689011363)
...
(-8.246981079288803e+28, 8.246981079288803e+28)
(-1.620469402758045e+29, 1.620469402758045e+29)
(-3.184099805769735e+29, 3.184099805769735e+29)

This is slowly getting worked upon (#13593 and #13642 will be in 3.2 and are already likely to break everyone's code :p); I'm sure more will happen in the 3.3 timeframe. Remilestoning.

We've done substantial work adjacent to this, in particular #13593 and #13642, mentioned above. I'm going to close here, and if we feel there are still actionable issues, we should make a clean issue report with reproducible examples of the problems.

Autoscaling has fundamental problems · Issue #7413 · matplotlib/matplotlib · GitHub

Repository navigation

Autoscaling has fundamental problems #7413

20 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Autoscaling has fundamental problems · Issue #7413 · matplotlib/matplotlib · GitHub

Repository navigation

Autoscaling has fundamental problems #7413

Description

Activity

tacaswell commented on Nov 8, 2016

efiring commented on Nov 8, 2016

anntzer commented on Nov 8, 2016

efiring commented on Nov 8, 2016

anntzer commented on Nov 8, 2016

efiring commented on Nov 8, 2016

anntzer commented on Nov 8, 2016

efiring commented on Nov 12, 2016

tacaswell commented on Nov 12, 2016

anntzer commented on Nov 12, 2016

efiring commented on Nov 12, 2016

anntzer commented on Nov 12, 2016

efiring commented on Nov 12, 2016

20 remaining items

ImportanceOfBeingErnest commented on Mar 9, 2019

jklymak commented on Mar 10, 2019

anntzer commented on Aug 6, 2019

jklymak commented on May 8, 2021

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions