search

WICG / layout-instability

A proposal for a Layout Instability specification
https://wicg.github.io/layout-instability/
Other
159 stars 27 forks source link

explicit calculation for impact fraction? #48

Closed fred-wang closed 4 years ago

fred-wang commented 4 years ago

I read the spec quickly but IIUC, the impact fraction involves calculating the area of a union of rectangles (each given by "points that lie within the bounds ... excluding any points that lie outside of the viewport."). It didn't seem obvious to me, but apparently it's a known problem https://en.wikipedia.org/wiki/Klee's_measure_problem ; maybe worth providing an explicit algorithm?

fred-wang commented 4 years ago

It didn't seem obvious to me

To me more accurate, naively I would have used something similar to https://en.wikipedia.org/wiki/Inclusion–exclusion_principle to take addition and differences of rectangular areas.

skobes-chromium commented 4 years ago

Yes the impact fraction is an instance of the Klee measure problem in two dimensions. Chromium uses a sweep line algorithm to compute it in O(n lg n) for n shifting elements.

I don't think the spec should mandate a specific algorithm - we should specify behavior, not implementation. But it may be helpful to include hints in a non-normative note.

fred-wang commented 4 years ago

I don't think the spec should mandate a specific algorithm - we should specify behavior, not implementation. But it may be helpful to include hints in a non-normative note.

Right, I stand corrected, I meant at least provide some hints.