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/
