Geometry package (was: Re: [julia-dev] A generic point type in Base?)

[Kevin Squire]

The discussion of a generic geometry package of caught my eye when it was discussed, as it would be useful to projects I'm working on.  It seems there was a consensus that such a package should exist, but not a consensus on how it should look.

I'd like to summarize and push the discussion forward a little more, hopefully toward such a package.

First, in addition to a few definitions in graphics.jl and @twadleigh's packages 

  https://github.com/twadleigh/Meshes.jl
  https://github.com/twadleigh/ImmutableArrays.jl

a search on github led to 

  https://github.com/mroughan/Geometry2D.jl

which is unregistered, but seems to provide a very nice set of 2D geometric primitives.  I'd encourage people to take a look at that package and see if that is close to what others had in mind (and I'll point @mroughan to this discussion).  

Ideally, I think it would be nice to start with the Geometry2D package and extend it to 3D and 4D (does anyone need 1D points, or more than 4D?).

Are there other basic packages that should be considered?

=================

Second, regarding Points:

1) immutable or mutable types for points? Both?

2) for immutable, based on ImmutableArrays?

3) for mutable, parameterize based on size (and back by an array)?

I'm inclined toward Points backed by ImmutableArrays, but are there valid uses for mutable points?

=================

Third, how should different coordinate systems be handled?

1) parameterize the point type by the coordinate system

2) handle different coordinate systems in separate packages, with common definitions in (a) base package(s)

Coordinate systems to consider:

* Cartesian

* Spherical

* Geographic

* Homogeneous (* I need this *)

* ...others?

=================

Peder mentioned boost, which seems to have a well thought out system.  It is however, slightly complicated.  In Julia terms, boost geometry points are parameterized by 1) dimension, 2) type, and 3) coordinate system, with mechanisms expanding this to other geometric constructs.

On one hand, this is nice and self contained.  On another hand, if I'm working in a particular coordinate system, I may not always care about other coordinate systems, and so the extra parameterizations might be annoyances (or just plain scary), and I won't want to use the system.

So another question is whether and/or how to cater to both the casual Point user in Cartesian space who doesn't want complicated types, and, well, someone who needs more complicated types.

==================

As I indicated above, I'm not proposing to build the whole library at once, or even to answer all of these questions--just asking thoughts/opinions to move this idea forward.

Cheers, 

   Kevin

On Mon, Jun 16, 2014 at 8:41 AM, Steve Kelly <kd2...@gmail.com> wrote:

In my MeshSlicer package I've been using ImmutableArrays (Vector2 and
Vector3) for this purpose. It works very well and has the appropriate
operations defined. Meshes.jl is also a good reference for using
ImmutableArrays with geometric algorithm.

https://github.com/twadleigh/Meshes.jl
https://github.com/twadleigh/ImmutableArrays.jl

On Mon, Jun 16, 2014 at 9:06 AM, Peder Axensten <pe...@axensten.se> wrote:
> I think the main thing is that the point class is generic enough, so that it
> will be able to accomodate the needs of more specialized libraries. Access
> functions to read and set individual coordinates by index should certainly
> be included. Could this be in Base?
>
> For cartesian points (and only them!), I think probably absolute value,
> euclidean distance (and maybe other distances), dot-product, addition, and
> subtraction would be uncontroversial, as well as multiplication and division
> by scalars. Maybe this should be in library Cartesian?
>
> For spherical, ellipsoidal, and other points, it would probably be better to
> implement them in specific libraries?
>
> In Boost, the coordinate system of a point is only a template argument. So
> it is there as a "tag" if you want to overload functions according to this,
> but occupies no memory. Being very interested in Julia, but not yet an
> active developer, I don't know how to best "tag" this here. But I'm sure it
> is doable.
>
> Hälsar Peder
>
> 16 jun 2014 kl. 12:11 skrev Ivar Nesje <iva...@gmail.com>:
>
> I think a common Point type for use in different Julia libraries would make
> sense. The problem is how to decide what to include and what not to include.
> It would feel weird if Base provided a Point type with no methods defined,
> so that packages would start to overload conflicting versions of the common
> operators. Do you think Base should provide a complete set of auxiliary
> functions (abs, distance, coordinate system transformations, etc.)?
>
> I don't think this belongs in Base, but it would be great if we had a
> barebones package that could serve as a foundation for other packages to
> share types and the simple operations on the objects. If such a package got
> traction and proved useful, it could be included in the set of default
> packages that will be installed by default.
>
> Ivar
>
> kl. 11:16:06 UTC+2 mandag 16. juni 2014 skrev Peder Axensten følgende:
>>
>> I work with several libraries handling points and other geometrical
>> objects in C++. The multitude of point types is a hurdle.
>>
>> I would suggest to take a good look at the geometry library in Boost (of
>> C++ fame) for in-deprh concepts of geometric objects.
>>
>> You want to specify the coordinate type, but probably also the dimension
>> of the point. Maybe also the coordinate system of the point (cartesian being
>> the default).
>>
>> When you have a generic point type, you can write access functions such as
>> getZ and setZ (that only works on cartesian points with dimension 3 or
>> higher) or getLatitude (for spherical points of dimension 2 or higher).
>>
>> Building on points it is natural to implement boxes other objects with
>> volume and funtions for how they relate (like inside, overlapping, touching
>> etc.).
>>
>> Hälsar Peder
>>
>> 16 jun 2014 kl. 10:13 skrev Tomas Lycken <tomas....@gmail.com>:
>>
>> There’s a multitude of problems defined on a continuous 2D domain, where
>> it makes sense do define a type
>>
>> immutable Point{T<:Number}
>>     x::T
>>     y::T
>> end
>>
>> It’s common, yet simple, enough to be the example on parametric types in
>> the manual. Yet I can’t find any type like this in Base.
>>
>> Of course, since the implementation is trivial it’s easy to just carry one
>> with the project, but I think it would make sense to include such a type in
>> Base so that all packages can use the same 2D point type, thereby making it
>> much easier to communicate these points between applications.
>>
>> Is there a reason this has been excluded, or is it just that no-one has
>> tried to include it yet? What are the opinions on including such a type? Are
>> there others, that might provide similar benefits?
>>
>> // Tomas

[Tony Kelman]

I would love to see real computational geometry capabilities in Julia, and I would absolutely need high dimensional spaces for working with multiparametric linear programming, polyhedral set operations, projections and convex hulls, etc. Anything that's restricted to <4D is close to useless to me, though my use cases are more obscure than most. Some algorithms only work in low dimensions and many of the obvious graphics and rendering type tasks only need 2-4, but try not to rule out N-D if a more general API is possible from the beginning.

[Kevin Squire]

Thanks Tony--that's why I asked if anyone needed more than 4D points. :-)

Cheers,

   Kevin

[Ivar Nesje]

Last time this was discussed, nobody seemed to have looked at base/graphics.jl. How would this relate to that?

[Kevin Squire]

It would probably borrow many or most of the basic definitions, but at a minimum extend them to more dimensions. 

And then likely add a number of other things, some of which would be relevant to graphics, some not. 

See the forementioned Graphics2D.jl for done ideas. 

Cheers,

   Kevin 

[Mauro]

> Ideally, I think it would be nice to start with the Geometry2D package and
> extend it to 3D and 4D (does anyone need 1D points, or more than 4D?).

I think 1D should be included too: for instance, I may want to start a
project by solving an equation in 1D and then move on to higher
dimensions. Hmm, maybe this even applies to 0D.

> Second, regarding Points:
>
> 1) immutable or mutable types for points? Both?
> 2) for immutable, based on ImmutableArrays?
> 3) for mutable, parameterize based on size (and back by an array)?
>
> I'm inclined toward Points backed by ImmutableArrays, but are there valid
> uses for mutable points?

Is it possible to make the Points type such that an array of them is as
performant as an array of just their coordinates? I think that this
would be the case when using individual fields for each coordinate. But
is it also the case when using an ImmutableArray as storage, or does
that result in an array of pointers?

> =================
>
> Third, how should different coordinate systems be handled?
>
> 1) parameterize the point type by the coordinate system
> 2) handle different coordinate systems in separate packages, with common
> definitions in (a) base package(s)
>
> Coordinate systems to consider:
>
> * Cartesian
> * Spherical
> * Geographic
> * Homogeneous (* I need this *)
> * ...others?

Probably coordinate systems should be separate packages, as that is
quite a complicated issue. But it could/should still feature as a type
parameter.

Concerning geographic coordinates, here is a wrapper to GDAL:
https://github.com/wkearn/GDAL.jl

One part of GDAL does geographic coordinate transformations:
http://www.gdal.org/osr_tutorial.html

> =================
>
> Peder mentioned boost, which seems to have a well thought out system. It
> is however, slightly complicated. In Julia terms, boost geometry points
> are parameterized by 1) dimension, 2) type, and 3) coordinate system, with
> mechanisms expanding this to other geometric constructs.
>
> On one hand, this is nice and self contained. On another hand, if I'm
> working in a particular coordinate system, I may not always care about
> other coordinate systems, and so the extra parameterizations might be
> annoyances (or just plain scary), and I won't want to use the system.
>
> So another question is whether and/or how to cater to both the casual Point
> user in Cartesian space who doesn't want complicated types, and, well,
> someone who needs more complicated types.

Shouldn't it be possible to hide this complexity in case of Cartesian
coordinates with suitable typealiases and show functions?

[Steve Kelly]

Kevin,

Would you be interested in setting up a JuliaGeometry organization on github?

Best,
Steve

[Kevin Squire]

(Continuing that conversation in the other thread....)

[Kevin Squire]

See also Matt Rougan's responses to these ideas here. (He's the owner of Geometry2D.jl)

Kevin

[Tracy Wadleigh]

I'd be happy to transfer ownership of ImmutableArrays and Meshes to a geometry group. Keep me in the loop if there is still momentum to see this through.