[prev in list] [next in list] [prev in thread] [next in thread] 

List:       jakarta-commons-dev
Subject:    Re: [geometry] Points and Vectors Proposal
From:       Gilles <gilles () harfang ! homelinux ! org>
Date:       2018-04-30 12:03:04
Message-ID: cce3ec53bc365f3edbe14b58ba2be67c () scarlet ! be
[Download RAW message or body]

Hello.

On Sun, 29 Apr 2018 02:40:54 +0000, Matt Juntunen wrote:
> Hi Gilles,
> 
> The generic Vector class is actually not used much but the generic
> Point class is used throughout the core partitioning code and in the
> high-level enclosing ball code. If we used a class like
> 
> class Vector2D implements Vector, Cartesian2D, Polar2D { ... }
> 
> We'd still need to cast internally on the Vector methods since they
> accept the generic Vector type (eg, add(Vector<S> v)).

Do you mean that the code uses "instanceof" to check which
subclass of Vector is being passed?

> A slightly different approach on the polar vs Cartesian thing would
> be to use the same exact "spatial value" class to represent them 
> both.
> This makes sense conceptually since they're both just different
> representations of the same underlying spatial value.

Does the codebase contain functionality that is purely
"geometric" (no assumption on the underlying coordinate system)
or is it a basic assumption that Cartesian coordinates are needed
for anything useful.

In the former case, it is not good to assume either Cartesian or
polar coordinates or even both, since other coordinate system are
possible.

If, say, the scope of this component is limited (to what?) and
explicitly requires a Cartesian coordinate system, then (and only
then, I guess), can the design be based on this assumption.

> The main
> interface might then look something like this (note that I'm playing
> with the names a bit to see what fits best):
> 
> // Describes a value associated with a specific type of mathematical 
> space.
> // For an n-dimensional space, this will typically take the form of
> an n-tuple, but no restrictions
> // are placed on the representation at this level.
> interface Spatial {
> int getDimension();
> boolean isNaN();
> boolean isInfinite();
> }
> 
> // Point interface. This adds point semantics to an otherwise 
> mathematically
> // meaningless Spatial value.
> interface Point<S extends Spatial> {
> S getValue();
> double distance(Point<S> p);
> // ...
> }
> 
> // Vector interface. This adds vector semantics to an otherwise
> mathematically
> // meaningless Spatial value.
> interface Vector<S extends Spatial> {
> S getValue();
> Vector<S> add(Vector<S> v);
> // ...
> }
> 
> // Represents a value in Euclidean two-dimensional space.
> class Euclidean2D implements Spatial {
> // Store coordinates internally in Cartesian form but expose
> // methods for getting and constructing the values in other
> representations,
> // specifically polar.
> protected final double x;
> protected final double y;
> 
> // Cartesian accessors
> double getX();
> double getY();
> 
> // Polar accessors
> double getR();
> double getTheta();
> 
> // ...
> }

Unless there is a good reason (how to subclass should be
explained in the Javadoc), "protected" fields and methods
must be avoided.

As hinted above, we first have to decide whether specific
coordinate systems are a basic tenet of the component's
functionalities, or an implementation detail.

> class Vector2D extends Euclidean2D implements Vector<Euclidean2D> {
> Euclidean2D getValue() {
> return this;
> }
> 
> Vector2D add(Vector<Euclidean2D> v) {
> Euclidean2D val = v.getValue(); // no cast needed; we know
> what types of values we're working with
> 
> // perform operations in Cartesian coordinates; callers can
> get the polar coordinate values
> // from the result if they want
> return new Vector2D(x + val.getX(), y + val.getY());
> }
> }

I'm wary of
   Vector2D add(Vector<Euclidean2D> v)
where it should rather be
   Vector2D add(Vector2D v)

I'd imagine that an application developer will want to use
simple workflows:
  * create a vector (e.g. calling either a "Cartesian" or a
    "polar" factory method),
  * pass it to coordinate-system independent algorithms (it's
    up to those algorithm to make the necessary conversion if
    they are implemented in term of a specific system),
  * retrieve the result and be able to convert it to his system
    of choice.

How about something along the following lines?

public interface Vector2D {
   Vector2D add(Vector2D other);

   // etc.
}

public class Vector2DFactory {
   public static Cartesian2D toCartesian(Cartesian2D v) {
     return v;
   }
   public static Cartesian2D toCartesian(Polar2D v) { ... }

   // etc.
}

public class Cartesian2D implements Vector2D {
   private final double x;
   private final double y;

   public Cartesian2D add(Cartesian2D other) {
     return new Cartesian2D(x + other.x, y + other.y);
   }

   @Override
   public Vector2D add(Vector2D other) {
     return add(Vector2DFactory.toCartesian(other));
   }
}

public class Polar2D {
   private final double r;
   private final double theta;

   // etc.
}

Regards,
Gilles

> 
> 
> 
> ________________________________
> From: Gilles <gilles@harfang.homelinux.org>
> Sent: Saturday, April 28, 2018 7:28 AM
> To: dev@commons.apache.org
> Subject: Re: [geometry] Points and Vectors Proposal
> 
> Hi.
> 
> On Thu, 26 Apr 2018 21:19:08 +0000, Matt Juntunen wrote:
> > Hi,
> > 
> > I think one of the main issues here is that implementations of Point
> > and Vector need to have access to coordinate values in order to do
> > work, but the generic interfaces don't make that information
> > accessible. We end up having to constantly cast from inputs like
> > Vector<Euclidean2D> to Cartesian2D in the implementation classes.
> 
> That is annoying indeed.
> 
> > This
> > is true in the current code as well as in my updated branch. This
> > makes it difficult to allow for other coordinate systems. So, what
> > would you say to an interface structure like this:
> > 
> > interface Coordinates {
> > int getDimensions();
> > }
> > 
> > interface Spatial<C extends Coordinates> {
> > C getCoordinates();
> > }
> > 
> > interface Vector<C extends Coordinates> extends Spatial<C> {
> > Vector<C> add(Vector<C> v);
> > // ... other methods
> > }
> > 
> > interface Point<C extends Coordinates> extends Spatial<C> {
> > Vector<C> subtract(Point<C> p);
> > // ... other methods
> > }
> > 
> > class Euclidean2D implements Coordinates {
> > double getX();
> > double getY();
> > }
> 
> The name of the above class should be "Cartesian2D".
> 
> > class Vector2D extends Euclidean2D implements Vector<Euclidean2D>
> > Vector2D add(Vector<Euclidean2D> v) {
> > Euclidean2D c = v.getCoordinates();
> > return new Vector2D(x + c.getX(), y + c.getY());
> > }
> > 
> > Euclidean2D getCoordinates() {
> > return this;
> > }
> > // ...
> > }
> 
> The problem with the above is that it forces a coordinate
> system on a class that represents the concept of vector
> (which is coordinate-"agnostic").
> If/when we want to introduce polar coordinates we'd need
> something like
> class Vector2D implements Vector<Cartesian2D>, Vector<Polar2D>
> which won't compile.
> 
> A straightforward way would be to include coordinate
> accessors for all common systems:
> 
> interface Coordinates {
> int getDimensions();
> }
> interface Cartesian2D extends Coordinates {
> double getX();
> double getY();
> }
> interface Polar2D extends Coordinates {
> double getR();
> double getTheta();
> }
> class Vector2D implements Cartesian2D, Polar2D { ... }
> 
> What is the actual use of the "Vector" interface in the code?
> Are there generic algorithms (I mean those that don't need
> to "cast" to do some useful work, i.e. work at the "geometrical"
> level rather than the "coordinate" level)?
> If so, we'd have
> class Vector2D implements Vector, Cartesian2D, Polar2D { ... }
> 
> Regards,
> Gilles
> 
> > This is using your idea of having the coordinates be available
> > through an accessor method in order to avoid the need to cast types
> > and make assumptions about the coordinate system. Also, note that 
> > I'm
> > not even using the Space interface here. The only method that seems
> > to
> > be used in that class is getDimensions() and that can easily be
> > placed
> > in the Coordinates interface.
> > 
> > -Matt
> > 
> > ________________________________
> > From: Gilles <gilles@harfang.homelinux.org>
> > Sent: Tuesday, April 24, 2018 7:55 AM
> > To: dev@commons.apache.org
> > Subject: Re: [geometry] Points and Vectors Proposal
> > 
> > Hi.
> > 
> > [Note: there is a problem with the quoted part in your
> > message.]
> > 
> > On Tue, 24 Apr 2018 01:31:43 +0000, Matt Juntunen wrote:
> > > Hi Gilles,
> > > 
> > > The hierarchy would be wrong from a conceptual POV: A vector can be
> > > described by Cartesian coordinates, but it should be possible to
> > > introduce new coordinate systems (polar in 2D, spherical in 3D) ...
> > 
> > > This approach doesn't limit the coordinate system at all. We can
> > > still make implementations of Point<EuclideanXD> and
> > > Vector<EuclideanXD> based on other coordinate systems. I think 
> > > it'll
> > > actually be easier in this structure, since the details of the
> > > system
> > > are explicitly defined in a single base class. For example, to
> > > create
> > > polar vectors and points, we would create a PolarCoordinate2D base
> > > class and PolarPoint2D and PolarVector2D subclasses.
> > 
> > What you propose (in the branch) is:
> > public class Point3D extends Cartesian3D
> > 
> > Then if we'd implement spherical coordinates, we'd have (similarly):
> > public class Point3D extends Spherical3D
> > 
> > Obviously, that will not work; so I may be missing what you
> > are trying to achieve...
> > 
> > > ...algorithms that use vectors would/should still work
> > > (transparently
> > > doing the appropriate conversions if necessary).
> > 
> > > This is a general issue with the current code, separate from the
> > > changes I'm proposing here. I'm not introducing a new issue.
> > 
> > What is the general issue?  That the code assumes Cartesian
> > coordinates?
> > My understanding is that your proposal exposes an "implementation
> > detail" (a set choice of the coordinate system).
> > 
> > > I understand (and agree with) the performance goal, but let's
> > > be careful to not define an API that does not correspond to
> > > the underlying concepts.
> > 
> > > Agreed. One vote in favor of having these utility methods is that I
> > > used some of them while transitioning the other geometry classes 
> > > for
> > > my proof-of-concept. For example,
> > > o.a.c.geometry.euclidean.threed.Plane uses the
> > > Vector3D.dotProduct(Cartesian3D, Cartesian3D) method to compute the
> > > origin offset directly from the origin point and plane normal.
> > 
> > I think that two issues are compounded here; one is the static
> > "utility" functions (whether they are more performant then
> > "pure" OO methods should be demonstrated, with benchmarks),
> > the other is the OO hierarchy, which should make sense from a
> > subject domain (i.e. geometry) POV.  Here I was again referring
> > to the fact that e.g. a vector in Euclidean 3D-space is equally
> > well represented by
> > (x, y, z)
> > or
> > (r, theta, phi)
> > or
> > (r, theta, z)
> > or
> > ...
> > 
> > Perhaps a "Cartesian3D" instance should be returned by an
> > accessor, rather than be the parent (?).
> > 
> > > What will happen when we introduce
> > > Spherical3D(r, theta, phi)
> > > alongside
> > > Cartesian3D(x, y, z)
> > > ?
> > > They should be able to get along just fine. They would each have
> > > subclasses that perform point and vector operations using their
> > > respective coordinate systems. The only issue would be trying to 
> > > mix
> > > them, which as I mentioned above, is an existing issue with the
> > > current code base. However, I think having the coordinate systems
> > > encapsulated in base classes is a good first step in solving this.
> > 
> > [See above.]
> > 
> > > If "Cartesian3D" _implements_ "Point3D" and "Vector3D", it
> > > would still work (i.e. refactor so that "Point3D" becomes
> > > an interface and does not assume that the coordinates are
> > > Cartesian).
> > 
> > > I'm not quite sure what you're picturing for the Point3D interface
> > > here. Even so, if Cartesian3D implemented both interfaces, the
> > > compiler wouldn't be any help in catching simple programming 
> > > errors.
> > 
> > IMO, a design is not primarily aimed at detecting programming
> > errors but should help the user avoid them. ;-)
> > 
> > Regards,
> > Gilles
> > 
> > > 
> > > Thanks,
> > > Matt
> > > ________________________________
> > > From: Gilles <gilles@harfang.homelinux.org>
> > > Sent: Monday, April 23, 2018 4:32 AM
> > > To: dev@commons.apache.org
> > > Subject: Re: [geometry] Points and Vectors Proposal
> > > 
> > > Hi.
> > > 
> > > On Mon, 23 Apr 2018 05:36:09 +0000, Matt Juntunen wrote:
> > > > Hi all,
> > > > 
> > > > I'd like to propose an update to the Euclidean Point/Vector 
> > > > classes
> > > > in the geometry project. We currently have a single CartesianXD
> > > > class
> > > > per dimension (eg, Cartesian2D) that implements both the Point and
> > > > Vector interfaces. This is similar to the previous commons-math
> > > > version where we had VectorXD classes that were also both Points
> > > > and
> > > > Vectors. The change to the current version was through discussion
> > > > on
> > > > MATH-1284 (https://issues.apache.org/jira/browse/MATH-1284). My
> > > > proposal is to flip the current inheritance hierarchy so that the
> > > > CartesianXD classes become the base classes for separate PointXD
> > > > and
> > > > VectorXD classes.
> > > 
> > > The hierarchy would be wrong from a conceptual POV: A vector can be
> > > described by Cartesian coordinates, but it should be possible to
> > > introduce new coordinate systems (polar in 2D, spherical in 3D) and
> > > algorithms that use vectors would/should still work (transparently
> > > doing the appropriate conversions if necessary).
> > > 
> > > > PointXD classes only implement the Point interface
> > > > and VectorXD classes only implement Vector. The Cartesian base
> > > > classes
> > > > contain the actual x, y, z coordinate values along with a few 
> > > > other
> > > > common methods (such as getSpace()). For performance and
> > > > convenience,
> > > > we can create static methods in the VectorXD classes that accept
> > > > the
> > > > Cartesian base class instances, so that users can perform common
> > > > vector operations using either type. For example, if you have a
> > > > giant
> > > > list of Points, these static methods would allow you to compute 
> > > > dot
> > > > products without needing to convert the Point instances to Vectors
> > > > first.
> > > 
> > > I understand (and agree with) the performance goal, but let's
> > > be careful to not define an API that does not correspond to
> > > the underlying concepts.
> > > 
> > > What will happen when we introduce
> > > Spherical3D(r, theta, phi)
> > > alongside
> > > Cartesian3D(x, y, z)
> > > ?
> > > 
> > > > I've partially implemented this in a branch so you can get a 
> > > > better
> > > > idea of what I'm picturing:
> > > > https://github.com/darkma773r/commons-geometry/tree/point-vector.
> > > > The
> > > > commons-geometry-core and commons-geometry-euclidean sub-modules
> > > > contain the changes.
> > > > 
> > > > 
> > > > 
> > > > 
> > > > [https://avatars1.githubusercontent.com/u/3809623?s=400&v=4]<https://github.com/darkma773r/commons-geometry/tree/point-vector>
> > > >  
> > > > 
> > > > 
> > > > 
> > > > 
> > > > darkma773r/commons-geometry<https://github.com/darkma773r/commons-geometry/tree/point-vector>
> > > >  commons-geometry - Apache Commons Geometry
> > > > github.com
> > > > 
> > > > 
> > > > 
> > > > The main benefit I see from this approach is code clarity. The
> > > > intent
> > > > of the code seems much clearer to me when the names of the types
> > > > exactly match what they represent mathematically. For example, one
> > > > of
> > > > the constructors for the Plane class currently looks like this:
> > > > 
> > > > public Plane(final Cartesian3D p, final Cartesian3D normal, final
> > > > double tolerance)
> > > > 
> > > > With my proposed changes, it would look like this:
> > > > 
> > > > public Plane(final Point3D p, final Vector3D normal, final double
> > > > tolerance)
> > > > 
> > > > The code is easier to read and the compiler will also help prevent
> > > > algorithm errors.
> > > 
> > > That API is better indeed.
> > > 
> > > If "Cartesian3D" _implements_ "Point3D" and "Vector3D", it
> > > would still work (i.e. refactor so that "Point3D" becomes
> > > an interface and does not assume that the coordinates are
> > > Cartesian).
> > > 
> > > Best regards,
> > > Gilles
> > > 
> > > > 
> > > > Thoughts?
> > > > 
> > > > Regards,
> > > > Matt Juntunen


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org


[prev in list] [next in list] [prev in thread] [next in thread]