I am trying to design an object-oriented library to handle geometric calculations. However, I am trying to exaggerate on being "tightly" object-oriented and applying relevant "best practices". I know that there is no reason to be dogmatic about patterns, I am just trying to squeeze out every bit of possibility that I have not found out any different way for what I am about to ask.
Consider trying to design a path, composed of segments. I consider having a common interface for segments, which offers a method to calculate points of intersection with another segment. In short, the tentative signature of such a method might look like:
abstract class Segment
{
...
Point[] Intersection(Segment other);
...
}
However, when implementing such a method, it might be necessary to check what actual implementation lies behind the "other" Segment. This can be done through run-time type checks, given that the language supports it, otherwise, I have to use some kind of enum to differentiate between segments and, potentially, cast the object to call corresponding methods. In any case, I cannot "extract" some common interface for this kind of design.
I have considered "forcingly" establishing a base-assumption that all path segments boil down to sequences of points, and unify the algorithmic intersection process as being always a line-to-line intersection between all sub-segments, but this will rob the design of a very significant (in my opinion) optimization possibility. Considering the ubiquity and "temporal density" of geometry-based operations the library will be built to support, it is very important, in terms of performance, to take advantage of special shapes having "closed forms" to calculate intersections between them (such as a circular arc with a line), instead of testing a multitude of small line-segment pairs to identify intersection points.
Apart from that, if I make the simplifying assumption of paths consisting of path sequences, I will have to make another relatively pervasive (for such a library) design choice, that of point density, to trace, for example, the various segment types. This would be, in my opinion, a reasonably architecturally-relevant parameter when considering an end result of drawing, e.g. on-screen, in order to achieve a given level of smoothness, for example. However, I feel this is, conceptually" an unsuitable abstraction for the geometric operations between pure geometric abstractions. A circle is not a series of line segments and should not need 5,10 or 100 coordinate pairs to be represented. It is just a center and a radius.
My question is, is there any other way to be object-oriented when dealing with base classes for geometry entities, or the "usual" way of doing things is with an enumeration and implementations checking segment type and exploiting specific geometric relations to potentially optimize the procedures?
The reason I am giving so much thought on this is that I might find myself having to implement special segment types, such as, for example, parametric curves, in the future, or simply allow extension of the API outside of the API itself. If I use the enum-based, type-checked everything-with-everything intersection tests (and do so also for other spatial operations between segments besides intersection), "outsider" extensions of the API will have to "register" themselves in the segment-types enumeration, which would necessitate either changing and rebuilding the original API, or providing a mechanism for external registrations. Or simply make a true global capture of all possible segment geometric forms to account for everything.
To make it simple, assume that I implement this only with segments, and then I add a new implementation of a circular arc. I can "teach" the circular arc how to intersect itself with straight line segments (by checking the segment type for "line", for example), but I can not "teach" the line segment how to intersect itself with arcs without going back to change the original library.
I understand that there are methods or techniques to provide all this flexibility (I could make segments register special "injected" intersection methods for specific identifiers, which would be determined by the external API extension objects, so that lines will first check whether the object they intersect with is such a "special" type, or simply make intersection methods virtual, so that the developer trying to extend my API will be able to manually "teach" all existing segment implementations how to intersect themselves with my original objects). All I am asking is, is there any other elegant way to tackle this situation?
The top-voted answer to this question suggests excluding the method entirely and delegating it to a different class. This does sound somewhat counter-intuitive, given that segments do know their geometries. However, segments do not know other segments' geometries, so it appears to be a reasonable design decision to "outsource" the intersection method, one that still necessitates knowing the segment type at run-time, however. Since I am trying to represent segments as interfaces "ignorant" of the underlying type (as in "I want to support the use of the segment interface as being ignorant of the underlying implementation"). Apart from that, I would not resort to empty marker interfaces to differentiate between classes. An external "intersector"-like class would look interesting, though I would avoid making it static, in order to allow for extensions and potential changes of strategy (different implementations, optimizing for speed, employing snapping, etc).
UPDATE: Based on questions from some of the comments, I updated the question.
First of all, I am not considering compiler optimizations at all. I am considering optimizing the conceptual model, the programming language is not entirely relevant to the question, which is why I did not make a specific reference (it only becomes relevant based on whether it offers a multiple-dispatch mechanism built-in, but not in terms of possible low-level optimizations, this is not yet a concern).
-Question (from comments): Can segments be always described by a formula? If yes couldn't the peculiarities be pushed from the type-system to actual code?
-Answer: A very good question. I understand what is meant by a formula, if this is the case, intersections will always be a matter of solving a system of equations, no matter what the segment type is. Unfortunately, this is not possible for the domain because of a very important consideration that I have deliberately not mentioned, as I was trying to focus on the object-oriented design aspect of the problem. This is NOT planar geometry. Points, segments (and polygons) are defined on a surface of nonzero curvature. Despite simplification assumptions, equation solutions not only have no closed form, but intersections between straight line segments (enter geodesics) are orders of magnitude more complex and far from having a closed form and are usually solved iteratively. I am using the term circular arc here as an alias for the geometric space of a subset of all points equidistant to a given point.
So, in terms of underlying formulas, the answer is, typically, "yes", but the formulas are differential equations, at best, if not combinations thereof, for any given segment. Vertical segments technically could, but are practically not expected to exist based on the domain I am called to support, so these will be handled as corner cases. I did not want to mention those details because my question was, practically, (now that I re-read it) "when I have two objects, of which I only know the base type, what do I have to do to overload on both types in the typical object-oriented manner of using virtual methods, is there something elegant other than enum-based or direct type checking (given that the used language supports these constructs, of course)"? After some more searching, I see that I will probably have to tackle this problem by implementing a multiple-dispatch mechanism, which DocBrown has also hinted to in one of the comments.
Now, given the question above, technically, segment types could always be described by a common underlying "poly-line" form, where they are always composed of many small straight sub-segments. This will mean that, in order to represent an arc, I will have to use an arc-segment, traced using a number of straight sub-segments, say L. To intersect a straight segment with an arc-segment based on such a representation, all arc sub-segments must be intersected with the single sub-segment of the straight segment. I am trying to avoid this because there is no need to replace 1 line-circle intersection test with N line-line intersection tests. If I have a connected path composed of K straight segments and N arc segments (a relatively typical use case will have K = 5-10 and N = 4-5), any intersection between this path and another path will have to test for at least K + N*L line-line intersections, effectively exploding time complexity. Considering the almost equal time complexity of calculating a line-line intersection and a line-circle intersection (ok, a line-circle intersection consists of a couple more operations, but is not L times more computationally intensive to justify replacing with L straight sub-segments, at least not for any reasonable value of L, which would be definitely > 3, and this being rather lenient). Besides, a circular arc is not a series of sub-segments conceptually, despite all the shortcomings that come with this consideration.
To make matters worse, I will need to also implement "projection" of points onto the connected paths. Based on the geometric considerations, projection onto a circular arc is not expected to be much more complex than onto a straight line segment. If I consider (K + N*L) segments for a connected path, computational time to project a point on each and every one of them really explodes, compared to (K + N) projections if I just overloaded the perpendicular projection method based on the segment type, instead of generalizing with sub-segments for every segment type. Thankfully, projection of a point onto a segment only requires single-dispatch and can be overloaded from an abstract method in a base class or simply implement a method in the contract.
I hope this clears up a few things regarding the questions in the comments and I also apologize for the lengthiness of the post.
