Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009

Subject: Re: [boost] Formal Review: Boost.Polygon starts today August 24, 2009
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-08-29 20:53:07

Simonson, Lucanus J wrote:
> I would expect (A & B) |
> (C - D) to be slower if executed as one sweep over all the edges in
> A, B, C and D than as three since we can expect A&B and C-D to reduce
> the data volume that goes into the OR operation.  Also the peak
> memory required for sweeping all of them at once is greater than as
> separate passes for each op.  One final consideration is that it is
> fairly rare for people to form multi-op expressions of simple
> booleans in a single line (such that expression templates could kick
> in), so even if there were a performance win we would be optimizing
> for the uncommon case.  There is plenty left to do to make a single
> op run faster, I have a list, actually.                    

I forgot to mention, I'm already doing an important optimization for multi-op booleans.

A boolean is broken into three stages: sorting the input edges, sweepline to perform the boolean and sweepline to form output polygons.  The sweepline that performs the booleans outputs edges in exactly the same format and order that it needs at its input.  When multiple booleans are chained there is no need to form polygons for intermediate results and then sort them again.  In the multi-op expression above this eliminates a number of unneeded steps.  Instead of:

Sort(A)
Sort(B)
Sweep(A&B)
FormPolygons(A&B)
Sort(C)
Sort(D)
Sweep(C-D)
FormPolygons(C-D)
Sort(A&B Polygons)
Sort(C-D Polygons)
Sweep((A&B)|(C-D))
FormPolygons((A&B)|(C-D))

I do

Sort(A)
Sort(B)
Sweep(A&B)
Sort(C)
Sort(D)
Sweep(C-D)
Sweep((A&B)|(C-D))
FormPolygons((A&B)|(C-D))

For the manhattan case each of the three steps is roughly the same runtime, so this would be roughtly a 1.5X speedup in the example.  For general polygons the sweep that performs the booleans will dominate, and the optimization is relatively less important.  Still in order to understand the performance implications of a single pass n-input op we have to compare it to what I'm currently doing.

Regards,
Luke