Hi Brandon,
Hi Barend,
Hi Brandon and Barend, If two is company, is three a community? I suggested to Brandon off list that we ought to merge. I also conceded that the algorithms he provides are a better starting point than mine in terms of what a boost geometry library ought to provide. The primary thing preventing us from working together and sharing algorithms is the lack of an agreed upon standard for abstracting geometry data types from the algorithms that work on them. We all agree that it should be done, we even largely agree on how in a general sense. If we could pick one specific syntax and pattern, or combine ideas to arrive at one we all agree on, then we could port our algorithms and their interfaces into that form. Ideally, we should be able to compare our algorithms side by side in the same library to chose which one becomes the one that is published as the boost algorithm. Barend has a line intersection algorithm. I have boolean operations on manhattan, 45-degree and now arbitrary angle polgyons. Replacing my line intersection algorithm with the one coming from Barend or Brandon's library might speed up my boolean operations. My scanline that does boolean operations is generic and provides several other algorithms such as connectivity extraction and property merge operations, but may not be as fast as Brandon's for simple Booleans. Ideally, I'd like to find out the answers to these questions with a minimum of effort. I think the algorithms themselves are less important than their interfaces, and as Brandon said, the whole meat of the problem is how to parameterize the coordinate data type in a way that actually works for complex numerical data types and is still usable. Brandon pointed out:
Also, there are some other issues with respect to using custom number types which may not use math function like std::sqrt or the trig functions which may require specialization of math_function traits for the coordinate type. I had to do this in order to use mpq_class (rational exact type in GMP) so that I could get distances between two points :-). (In the end its going >to require defining a generic Taylor series expansion for all the trig + sqrt functions that support number types as template parameters.)
These issues clearly need to be sorted out. I just integrated mpz_class into my integer geometry oriented algorithms because I need upwards of 90 bits of integer precision to store intermediate values of complex algebraic expressions. I had to wrap it to provide the casting operator to integer so that I could parameterize the high precision data type in my code without directly depending on GPL'd gmp header files. For me the problem of how to bridge the conceptual gap between floating point and integer geometry is an open question. Even multi-precision rational data type geometry does not really satisfy my needs because a robust linescan in rational coordinates may lead to new intersections and many degeneracies being introduced when snapping back to integer coordinates at the output. I don't need an epsilon or comparison policy argument to deal with integer coordinates, so I don't have these in my library. Clearly, I should need it if comparing Euclidean distances, and I could benefit from incorporating it. I'd like to see a boost library that works well with floating point, rational/lazy-exact and integer coordinates of geometry that I can contribute to/use. This could mean that the line segment intersection algorithm requires a snapping policy in addition to a comparison policy. It might even mean separate integer and floating point implementations of some algorithms where convolving the complexities of the one with those of the other is simply not worth the trouble. I think we should focus on how we can get from where we are today--talking about my geometry library, your geometry library and his geometry library-- to the point where we need to be; talking about the boost geometry library and the community of developers who are contributing to it. Luke