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-25 13:45:06

Jeffrey Hellrung wrote:
> I read through the boostcon paper and it all looked very interesting,
> but was disappointed to find that coordinates must be of integral
>   type. Can you comment on the rationale for this limitation?  

Firt, in my application area (VLSI CAD) coordinates are always integer.  Second, conversion from floating point to integer and back does lose some precision, but a scaling factor can be applied to minimize the lost precision within the limits of the integer data type.  Use of a larger integer type can further reduce the loss of precision.  Third, the robust floating point version of the same algorithm is somewhat more complicated.  Floating point numbers are approximations and elaborate techniques are required to implement robust floating point geometry.  I can understand the desire for a floating point version of the algorithm, but I'm not convinced there is a practical need given that the integer algorithm can produce results with minimal loss of precision.

> Also, I have a question (or multiple...) concerning the line-sweeping
> algorithm, which I don't fully understand.  To begin with, I don't
> fully understand what you mean by the "derivative of a polygon",
> despite 
> several paragraphs devoted to this.  I understand this is a novel
> concept you've invented, so I don't expect to find anything useful in
> the references.  It seems you're implicitly using a 2-dimensional as
> well as a 1-dimensional representation of a polygon...?  Section 5.1
> begins by viewing the polygon as a characteristic function of the
>   plane. That's reasonable.  And it is indeed a "mathematical
> function of two variables".  What's a jump in derivation to me is
> going from the "usual" partial derivatives of these characteristic
> functions (which amounts to 
> a vectorized-delta distribution on the boundary of the
> polygon...right?) 
> to these vertex-support quantities.  What's adding to my confusion is
> that "magnitudes" of the impulses that compose the derivative may be
> +1 
> or -1, indicating that an impulse with magnitude +1 is different from
> an impulse in the opposite direction of magnitude -1.  So I'm not
> really 
> sure why you pick the specific arrow directions and signs in Figure 3.
> Would it be possible to explain this in more detail, or provide
> another reference?

The key thing you need to understand is that the magnitude of the impuse at each vertex quantity in the derivitize is directed normal to the plane in the z axis.  The z axis is the dimension which describes how many overlapping polygons there are.  If we view the polygon on a plataeu with height of one in z then superimposing two such polygons would produce a height of two in z where they overlap.  The magnitude is +1 or -1 because the derivitive of a step function is +1 (impuse function) at the rising edge and -1 (inpuse function) at the falling edge.

I am in the process of submitting a paper to the CAD Journal that provides a better explanation.  I will copy the relevant portion of the text to this email.

"
In our problem formulation we model a polygon as a mathematical function of two variables x and y such that for all x/y points inside the polygon the function returns one, and for all points outside the polygon the function returns zero.  This view of a polygon is useful because it allows us to reason about the problem mathematically.
If we consider a mathematical function of two variables, we can apply the partial derivative with respect to each of those variables, which provides the points at which the function value changes and the directions and magnitudes in which it is changing.  Because our geometry is piece-wise linear this reduces the two dimensional definition of the polygon function to a collection of zero dimensional quantities at its vertices that are directed impulses with magnitude of positive or negative one.   This concept is more easily understood and explained by reducing it to one dimension.  A one-dimensional view of our mathematical definition of a polygon reduces it to intervals on the number line where the polygon function returns one.  When viewed in one dimension, the cross section of a polygon function is the linear combination of unit step functions located at the positions where edges of the polygon intersect our cutline.  The derivative of a unit step function is a unit impulse function.  If we differentiate a linear combination of unit step functions we get a linear combination of unit impulse functions.  Integration restores the original intervals where the polygon is defined.  Differentiating multiple polygons along the same cutline, superimposing their derivative impulse functions and integrating results in a function that describes the intervals with counts of the number of overlapping polygons defined.  This is how we integrate with respect y along our sweepline.  We extend this same idea to two dimensions by defining the derivative with respect to both x and y as a linear combination of directed impulse functions.  Each of these unit vector quantities is located at a polygon vertex, is directed parallel to a polygon edge and points in the direction that scanning (integration) will proceed.   Derivative impulse quantities have a value of positive one if entering a leading edge of a polygon or leaving a trailing edge of a polygon and a value of negative one if entering a trailing edge of a polygon or leaving a leading edge of a polygon.  This definition makes all sweepline events mathematically equivalent allowing them to be handled in a uniform manner during subsequent processing during integration.  A graphical representation of the derivative of a polygon is shown in Figure 2.
Integrating our directed unit impulse derivative quantities with respect to x and y allows us to reconstruct the two-dimensional polygon function from these zero dimensional derivative quantities.  A graphical representation of such integration to reconstruct a polygon is shown if Figure 3.  This integration with respect to x and y in mathematical terms is accomplished programmatically by sweeping from left to right and from bottom to top along the sweep-line and accumulating partial sums.  Because the polygons are piecewise linear this summation is discreet rather than continuous and is therefore a computationally simple Riemann-Stieltjes integral.  What this mathematical model for calculus of polygons allows us to do is superimpose multiple overlapping polygons by decomposing them into vertex objects that carry data about direction and magnitude of change along the edges that project out of those vertices.  Because these vertices are zero-dimensional quantities they can be superimposed simply by placing them together in a collection, trivially sorting them in the order they are to be scanned by x, then by y, then by their direction and summing any that have the same point and direction in common.  When scanned, their magnitudes are accumulated (integrated) onto intervals of the sweep-line data structure.  Because the data is sorted by direction in the input sequence as well as on the sweepline, an interval on the sweepline may describe the difference in directed angle of two vector quantities that have the same point in common at that position of the sweepline.  This provides the sweepline data structure the ability to fully describe the number of polygons intersecting the sweepline even if that intersection takes place at only a single point.  The sweep-line data structure should ideally be a binary tree that provides amortized log(n) lookup, insertion and removal of these sums, keyed by the lower bound of the interval (which of course constantly changes as the sweep-line moves.)  Each such interval on the sweep-line data structure stores the count of the number of polygons the sweep-line is currently intersecting along that interval.  Notably, the definition allows counts to be negative.  A union operation is performed by retaining all edges for which the count above is greater than zero and the count below is less than or equal to zero or visa-versa.  Vertical edges are a special case because they are parallel to our sweep-line but are easily handled by summing them from bottom to top (integrating with respect to y) as we progress along the sweep-line.  The implementation of the sweepline requires that comparison between elements of the tree depend upon the y value for the current x location of the sweepline and ties be broken by the directed angles of the elements.  At each sweepline stop (unique x) the state of the sweepline is initially backward looking, describing the counts of polygons that intersect the sweepline or touch it from the left prior to the processing of sweepline events at that x location.  Because of this, the sorting order of directed angles of segments intersecting the sweepline when they are compared must be reversed to process the sweepline at the new x location.  Processing all sweepline event points from the input (including vertically directed events) as well as intersection points removes all line segments that terminate at that x location while summing input derivative quantities into the counts stored on the sweepline.  After changing the sorting order criteria for directed angles of in the sweepline to forward and inserting edges that begin at that x location the sweepline is left in a forward looking state describing the counts of polygons that intersect the sweepline or touch it from the right.  In this way the algorithm is explicit in describing the number of polygons that intersect the sweepline, including complete topology information, at all points.
"

Figure 2 and 3 are the same as figures discussed in the explanation in the boostcon paper.

My appologies for the length of the reply.

Thanks for your question,
Luke