Re: Rewrite Skyline code (issue 547980044 by address@hidden)

[dak]

On 2020/04/19 22:35:39, dak wrote:
> On 2020/04/19 21:43:26, hanwenn wrote:
> > (this still needs some work, but the speedup might be worth an early
look)
> 
> * Buildings store Y coordinate of the left edge, rather than the
>   intercept at x==0.0.  This avoid excessive rounding problems when X
>   is large, and lets us compute building.height_at(x[LEFT]) cheaply.
> 
> Since intercept computation order depends on the execution of the
merge
> algorithm and we use floating point arithmetic rather than fixed
point, this
> would make results a lot less reproducible.
> 
> I understand the sentiment and thought about it as well, but it would
only work
> if the _original_ coordinates were retained even after intersection
and
> additional intersections still worked based on the original
coordinates, making
> the merge order (mostly) irrelevant with regard to error propagation.

Actually, one way to keep this pretty order independent would be just
not to intersect until the final pass and use the preceding passes just
for throwing out those line segments that are completely shadowed by
others.  This should not keep all that much more data but would have to
deal with a larger current working set where max/min relations are
checked.  I have no clear view on the expected performance impact.

https://codereview.appspot.com/547980044/