0

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.

  • What prevents you from simply creating new classes to implement your optimized forms, and then using composition or inheritance to specialize your non-optimized forms? – Robert Harvey Jul 13 at 2:28
  • i dont think computers can do geometry. just floating point algebra – Ewan Jul 13 at 6:40
  • 3
    The second-highest answer to the question you found has probably the answer you are looking for. You simply run into the restriction that the programming language you are using does not provide a double-dispatch mechanism directly. – Doc Brown Jul 13 at 8:16
  • It might help to learn OOP in different languages before continuing. Many of the statements in your question are untrue for programming languages different from Java and C# (unless you're only thinking of supporting the 2). Also, if you pretend that anyone else besides you will use this model, understand that they will be looking for something; in C++ it will be speed, in Python it will be ease of use, in Java probably over-engineering? If this is only for a thesis forgotten forever, go crazy on design. If you expect people to eventually adopt it, go for simplicity and ease of understanding. – DanyAlejandro Jul 13 at 20:29
  • 2
    @DanyAlejandro The question doesn't mention Java at all, so it's a bit off topic, but I would like to call bs on C++ being 7 times faster on anything you do. I did actually write a polynomial calculation library in Java and you would be surprised (I was) what optimizations the JIT is able to do, including SIMD instructions. Also, things like the GraalVM will do runtime optimizations based on profiling, something a static compiler can only dream of. – Robert Bräutigam Jul 14 at 12:32
1

You should download the AutoCAD ObjectARX/.NET API and documentation. The documentation is not on web pages, but is available only in the download, alas. Look at how they implemented the Database and Geometry libraries. Database covers entities like lines, arcs, polylines, blocks, etc. that get stored in a drawing. Geometry is more of an algebra library to calculate 3D lengths, intersections, vectors, etc. If I remember correctly, the Geometry dll will work without having AutoCAD installed since it is all just structures and classes for floating point math, but the Database dll requires an actual installation of AutoCAD to run (Protip: BricsCAD is way cheaper and is ARX-compatible.)

I do not know if you want to follow their design strictly since both the C++ and the managed version rely heavily on base class inheritance with little use of composition from abstract base classes/interfaces. Many people today favor composition over inheritance. It will at least show you how one design team chose to handle it in 1994-1997 when they rewrote the C style ADS library to become the C++ library ObjectARX. The .NET version is really just a thin wrapper over the ARX library with IDisposables replacing RAII, so you should be able to grasp the basic design principles from whichever library you are more familiar with reading.

They do not provide curved-space formulas like I think you are describing (non-Euclidean geometry), but one could use their framework of separating of entity from calculation to hold your differential equations and their supporting data structures in one library for the math, and the specific entities being implemented in a separate library that uses the math library objects to request specific answers to relevant operations.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.