Simonson, Lucanus J wrote:
Given my proposed operator syntax for so-called Boolean operations I could fold the arbitrary angle geometry provided by Berend's library into mine (or visa-vera.)
manhattan + manhattan => manhattan result type by way of manhattan algorithm manhattan + 45-degree => 45-degree result type by way of 45 degree algorithm manhattan/45-degree + arbitrary angle => arbitrary angle result by way of arbitrary angle algorithm
Phil wrote:
As I recall, with Barend's library if you ask for the intersection of two unit-squares (0,0,1,1) and (1,0,2,1) you'll get a line (1,0,1,1), since it considers all points on the perimeter of a polygon to be included in the polygon:
+-+-+ | | | +-+-+
Luke, what does your library do in this case? I mention this because, as well as the C++ language style issues which I'm pleased to see are being discussed by smarter people than me, there are no doubt very many
geometry-related design choices here. If your library were stand-alone, your choices wouldn't matter much; but if as you suggest it can integrate with other (future) libraries, then consistent choices
are needed.
I've been waiting for this to come up. It is the old open/closed semantics issue. In the specification for what I implemented the boundary is neither "in" or "out", but somewhere in between. My implementation is consistent with the behavior of the EDA vendor tools. My choices did matter, and in fact, I didn't get to choose, the choice was made decades ago. If performed as a Boolean operation on polygons that happened to be rectangles the intersection that produces a zero area polygon is a degeneracy and will not be output. Only positive area regions are output. However, there is also provided by my library a rich language on rectangle types, which includes intersection of two rectangles that will return the degenerate intersection as a line modeled as a rectangle with zero area. Let's say that instead of intersection it is the subtraction operation being performed (equivalent to (A & !B) on the same two rectangles as your example above. My library would leave A unchanged, would Barend's library clip the boundary off of A and back it away by some epsilon in service of the boundaries are "in" semantic? It may be that Barend only implements intersection and union, in which case this issue would never come up because without inverting operations the semantic is never problematic. You can generally model "in" semantics by adding an additional bit of precision to your (integer) coordinates (shifting coordinate values left by one) and inflating your polygons by one resulting in all odd coordinates. Shapes own the even coordinates near their boundaries and your example above would produce a non-zero intersection containing one column of even coordinates. We do things this way at the application level when we need to worry about the boundary condition. You could model "out" semantics by deflating by one instead. I can't image how much of a pain all this becomes when using floating point coordinates due to numerical error. Does Barend's library consider a boundary to be shared if it is within some epsilon? What about if it is within some epsilon of equal angle? It seems it would get awfully messy in a hurry. Even if I were to implement arbitrary angle geometry, I would do it on fixed point coordinates at the interfaces and probably use variable precision numerical types for robustness of the algorithms themselves. Given that people seem very concerned about compatibility with cgal it seems like we should be figuring out what it does in these cases. The boost license allows cgal to ship my code with their library if they choose. I think it makes a lot of sense to think about compatibility issues. Thanks, Luke