Base for Affine Geometry models

Hi everybody !
This follows the previous discussion “Is Julia lazy” about models of vector spaces for educational purposes. Many propositions, suggestions have been made, all of them interesting, a lot of links too. I couldn’t check everything into detail but I will, little by little.
So, what I propose now is to continue with ‘Affine Geometry’ what I did with ‘Linear Algebra’.
The question of knowing if ‘affine geometry’ exists at all is pertinent . Some world famous mathematicians (Jean Dieudonné among them) state that it’s just a re-formulation of linear algebra and it doesn’t deserve any additional chapter in textbooks.
Well it’s the point of view of a ‘pure’ mathematician, I have a great respect for Mr Dieudonné person and work but …
Point is an abstraction more easily accessible than vector. Introductory plan and 3D geometry at school begins with points, continues with lines, etc… vectors are usually introduced by mean of couples of points. I’m not sure it’s the best way to introduce the usual physical space for children, much better than a plain ℝ³.
In any case I wrote a full chapter dedicated to affine geometry following linear algebra for French students and joined a lot of Python 3.4 objects to illustrate concepts of point, massive point, barycenters, varieties , hyperplanes, equindependence, and so on.
Now it’s my purpose to add the same in Julia language.
So I must have a good start.
I decided to show examples for the ℝⁿ spaces but to allow exact calculations with ℚⁿ and Fⁿ as well where F is a primary finite p-field;
Here’s my first attempt :

using LinearAlgebra
using GaloisFields
const F = @GaloisField 5  #F will be the primary 𝔽₅=ℤ/5ℤ field

#point sans masse
struct Point{T <: Number}
    C::Vector{T}
    Point{T}(V::Vector{T}) where {T}=new{T}(V)
end

gettype(P::Point{T}) where {T}= T
Base.show(io::IO, P::Point{T}) where {T} = print(io,P.C)
Base.:-(A::Point{T},B::Point{T}) where {T}= A.C-B.C
Base.:+(A::Point{T},V) where {T}=Point{T}(A.C+V)

const RP=Point{Float64}
RP(V::Vector{Int64})=Point{Float64}(Vector{Float64}(V))
const QP=Point{Rational{Int64}}
const FP=Point{F}
#fin de la section

#point pondéré
struct MassPoint{T <: Number}
    C::Vector{T}
    M::T
    MassPoint{T}(V::Vector{T},M::T) where {T}=new{T}(V,M)
end
const 
Base.show(io::IO, MP::MassPoint{T}) where {T} = print(io,MP.C," M=",MP.M)
const RMP=MassPoint{Float64}
RMP(P::RP,M)=MassPoint{Float64}(P.C,Float64(M))
const QMP=MassPoint{Rational{Int64}}
const FMP=MassPoint{F}
#fin de la section

#systèmes de points
struct PointsSystem{P}
    Pts::Vector{P}
    PointsSystem{P}(V::Vector{P}) where {P}=new{P}(V)
end

Base.show(io::IO, S::PointsSystem{P}) where {P} = print(io,S.Pts)
const PSR=PointsSystem{RP}
const PSQ=PointsSystem{QP}
const PSF=PointsSystem{FP}
#fin de la section 


#Systèmes de points pondérés
struct MassPointsSystem{P}
    MassPts::Vector{P}
    MassPointsSystem{P}(V::Vector{P}) where {P}=new{P}(V)
end
Base.show(io::IO, S::MassPointsSystem{P}) where {P} = print(io,S.MassPts)
const PMSR=MassPointsSystem{RMP}
const PMSQ=MassPointsSystem{QMP}
const PMSF=MassPointsSystem{FMP}
function barycentre(S::MassPointsSystem{P}) where P
    L1=[p.M for p in S.MassPts]
    L2=[p.C for p in S.MassPts]
    m=reduce(+,L1)
    s=inv(m)*(reduce(+,L2))
    return P(s,m)
end
#fin de la définition

#systèmes de vecteurs
struct VectorsSystem{T}
    Vectors::Vector{Vector{T}}
    VectorsSystem{T}(L::Vector{Vector{T}}) where {T}=new{T}(L)
end
Base.show(io::IO, S::VectorsSystem{T}) where {T} = print(io,S.Vectors)
gettype(S::VectorsSystem{T}) where {T}=T
function Base.size(S::VectorsSystem{T},n) where {T}
    if n==1
        return length(S.Vectors)
    elseif n==2
        return length(S.Vectors[1])
    else
        return 0
    end
end
function matrice(S::VectorsSystem{T}) where {T}
    s1=size(S,1)
    s2=size(S,2)
    M=zeros(gettype(S),s1,s2)
    for i in 1:s1, j in 1:s2
        M[i,j]=S.Vectors[i][j]
    end
    return M
end
rang(S::VectorsSystem{T}) where {T} = rank(matrice(S))
const VSR=VectorsSystem{Float64}
const VSQ=VectorsSystem{Rational{Int64}}
const VSF=VectorsSystem{F} 
VSR(V::Vector{Vector{Int64}})=VectorsSystem{Float64}(Vector{Vector{Float64}}(V))

and with another Jupyter Icell for testing :

#fonctions de test
function test_point()
    P1=RP([1,2,3])
    println(P1)
    println(gettype(P1))
    P2=QP([1//2,2,3])
    println(P2)
    P3=FP(F[4,5,6])
    println(P3)
    P4=RP([1.0,3,6])
    println(P1-P4)
    println(typeof(P1-P4))
    println(P1+[1,1,1])
end

function test_pointssystem()
    P1=RP([1,2,3])
    P2=RP([1.0,3,6])    
    S=[P1,P2]
    println(typeof(S))
    S1=PSR(S)
end

function test_masspoint()
    P1=QMP([1//2,3,1//3],2//1)
    println(P1)
    P2=RMP(RP([1.0,2,3]),3)
    println(P2)
    P3=FMP(F[4,5,6],F(3))
    println(P3)
end

function test_masspointssystem()
    P1=QMP([1//2,3,1//3],2//1)
    P2=QMP([1//3,3,5//2],3//1)
    S=[P1,P2]
    S1=PMSQ(S)
    println(S1)
    println(barycentre(S1))
end
#fn de la section

function test_vectorssystem()
    V1=[1,2,3]
    V2=[4,5,6]
    S=[V1,V2]
    VS=VSR(S)
    println(VS)
    println(gettype(VS))
    println(size(VS,1))
    println(size(VS,2))
    println(matrice(VS))
    println(rang(VS))
end

function main()
    test_point()
    test_pointssystem()
    test_masspoint()
    test_masspointssystem()
    test_vectorssystem()
end

main()

If you have some comments or suggestions for improvements, you’re welcome !

1 Like

Firstly, Your inner constructor is redundant. When you define a struct, a default constructor is automatically defined, and does the same thing as what you wrote here. All your inner constructors appear to be unnecessary.

Instead, you could create convenience constructors:

Point(v::Vector{T}) where {T} = Point{T}(v)

It’s possible that this outer constructor is also provided automatically, I don’t remember, so you should check.

I think you should probably extend eltype instead of creating a new gettype function.

1 Like

If you are interested in encoding dimensionality into your type, you can wrap a StaticArray instead of a Vector.

I will check this point a little later. But I know you enough now, to be sure in advance that you’re right.
About outer constructors I have a special question. Of course getting rid of all unnecessary things will make the code lighter.
But now it’s lunch time, and we have an almost sacred ritual here, specially on ‘Bastille-day’. I must join my family.

This affine stuff is way over my head, but I have been wishing for a library of geometric shapes that don’t have locations. In GeometryBasics.jl every object has a location in coordinate space. Is affine geometry the way to get what I’m looking for?

About inner constructors, you’re definitely right. i got rid of all of them and everything works like before.
My code begins to get used to a severe diet after your checking… :slight_smile:

I think you should probably extend eltype instead of creating a new gettype function.

Is there a special interest for this ? I don’t see. In any case it’s possible and quite simple.

If you are interested in encoding dimensionality into your type, you can wrap a StaticArray instead of a Vector .
You point out a real problem. I thought a lot about this. First by the possibility of adding a parametric value n , second by adding a member to all structure.
The benefit, of course, would be to prevent constructing systems of points or vectors with different dimensions, which is now possible. The sanction (punishment) for such behaviour arrives with the first computations, but the code would be more complicated… So is it worth ?
I’m not building a library I’m just making the base to construct examples to illustrate some theoretical lessons. I tried to make the minimum to solve all problems which I have in mind.
The process will always be the same :

  • From systems of points construct systems of vectors by differences.
  • From system of vectors build matrices
  • Use base computations of package LinearAlgebra (det, inv, rank, , etc… to solve problems.
    Everythng has been built in this direction. Of course in the case of finite Fp fields I should have to add two lines to overload abs and conv as suggested by Gunnar, I tested it works !

you can wrap a StaticArray instead of a Vector .

Can you explain a little this point, please ?
Now there is another point for which, maybe, you can help me :wink:
You noticed this outer constructor :

RP(V::Vector{Int64})=Point{Float64}(Vector{Float64}(V))

I was a little disappointed by the lack of initiative of Julia. I will come back to the point of laziness.
Given the type of data I want to build Julia waits for a Vector {Float64} argument. If I give [1,2,3] because I’m lazy to write [1.0,2.0,3.0] Julia creates a real scandal :angry:. I could expect an automatic conversion because every Int64 is convertible to Float64, but no ! Julia allows me to explicitly write only one of the coordinates in usual float form, but refuses all coordinates in integer form.
Is there something more elegant to force this behaviour (promotion rule ?) and how to write it. I tried a few thing from your previous examples, without any success.
The problem is even more complicated when we construct a mass point because all the coordinates and the mass as well should be from the same type and if you give float coordinates and integer mass Julia enters again a real nervous breakdown.
Thanks for reading.

You can do

julia> [1.,2.,3.]
3-element Vector{Float64}:
 1.0
 2.0
 3.0

or

julia> Float64[1,2,3]
3-element Vector{Float64}:
 1.0
 2.0
 3.0

I watched quickly the presentation.
It seems to me very poor.
I got used, and make an intensive use of very powerful graphic libraries written in Javascript like JSXGraph from University of Bayreuth.
I don’t know what you can really do with this. For curiosity I will check for a possible equivalent in Julia but in any case till now, for web development javascript cannot easily be replaced.

1 Like

Did you mean to reply to someone else? I don’t think I mentioned a presentation.

I use this feature in my outer constructor

Maybe misunderstanding I was speaking about the home page of GeometryBasics for which you give a link.

1 Like

JSXGraph looks cool, I don’t think Julia has anything quite like that currently. Luxor.jl and Makie can make nice visualizations though.

My question is whether affine geometry can be used to make a shape without specifying the location of the shape in a coordinate plane. For example, I want to do Circle() not Circle(center=(3,4), radius=5). Is an affine geometry package good for that?

OK I understand your question. Affine Geometry is simply ‘usual geometry’ when the field is real (Float64) and the dimension 2 or 3. Shapes likes circles, spheres, etc… are relevant to euclidean geometry. Strictly speaking ‘affine geometry’ doesn’t rest on any norm or distance.
Affine Geometry can be strange and contrary to intuition when the field is finite (discrete).
I don’t know any graphics library in any language showing figures independently of a coordinate system.
But, of course it’s possible to draw circles with random centre and random radius.

1 Like

Finally I decided to use genkuroki’s suggestion to replace GaloisFields by Nemo for the special case of Z/pZ residue fields. The price to pay to use their det, inv, rank, etc… was to convert ‘usual’ matrices in their own types (for example nmod_mat) but it was rather easy.
Of course I followed DNF suggestion to delete redundant default constructors making the code a little lighter.
Here’s the framework now :

using Nemo

const F = ResidueRing(ZZ, 5) #corps primaire ℤ/5ℤ


const NN = nmod
#point sans masse
struct Point{T}
    C::Vector{T}
end

gettype(P::Point{T}) where {T}= T
Base.show(io::IO, P::Point{T}) where {T} = print(io,P.C)
Base.:-(A::Point{T},B::Point{T}) where {T}= A.C-B.C
Base.:+(A::Point{T},V) where {T}=Point{T}(A.C+V)

const RP=Point{Float64}
RP(V::Vector{Int64})=Point{Float64}(Vector{Float64}(V))
const QP=Point{Rational{Int64}}
QP(V::Vector{Int64})=Point{Rational{Int64}}(Vector{Rational{Int64}}(V))
const FP=Point{NN}
FP(V::Vector{Int64})=Point{NN}(map(x->F(x),V))
#fin de la section

#systèmes de points
struct PointsSystem{P}
    Pts::Vector{P}
end

Base.show(io::IO, S::PointsSystem{P}) where {P} = print(io,S.Pts)
const PSR=PointsSystem{RP}
const PSQ=PointsSystem{QP}
PSQ
const PSF=PointsSystem{FP}
#fin de la section

#point pondéré
struct MassPoint{T}
    C::Vector{T}
    M::T
 end
Base.show(io::IO, MP::MassPoint{T}) where {T} = print(io,MP.C," M=",MP.M)
const RMP=MassPoint{Float64}
RMP(P::RP,M)=MassPoint{Float64}(P.C,Float64(M))
const QMP=MassPoint{Rational{Int64}}
QMP(P::QP,M)=MassPoint{Rational{Int64}}(P.C,Rational{Int64}(M))
const FMP=MassPoint{NN}
FMP(P::FP,M::NN)=MassPoint{NN}(P.C,M)
FMP(P::FP,M::Int64)=MassPoint{NN}(P.C,F(M))
FMP(V::Vector{Int64},M)=FMP(FP(V),M)
#fin de la section


#Systèmes de points pondérés
struct MassPointsSystem{P}
    MassPts::Vector{P}
end
Base.show(io::IO, S::MassPointsSystem{P}) where {P} = print(io,S.MassPts)
const PMSR=MassPointsSystem{RMP}
const PMSQ=MassPointsSystem{QMP}
const PMSF=MassPointsSystem{FMP}
#fin de la définition

#systèmes de vecteurs
struct VectorsSystem{T}
    Vectors::Vector{Vector{T}}
end
Base.show(io::IO, S::VectorsSystem{T}) where {T} = print(io,S.Vectors)
gettype(S::VectorsSystem{T}) where {T}=T
function Base.size(S::VectorsSystem{T},n) where {T}
    if n==1
        return length(S.Vectors)
    elseif n==2
        return length(S.Vectors[1])
    else
        return 0
    end
end

const VSR=VectorsSystem{Float64}
const VSQ=VectorsSystem{Rational{Int64}}
const VSF=VectorsSystem{NN}

function matrice(S::VectorsSystem{T}) where {T} #matrice associée à un système de vecteurs
    s1=size(S,1)
    s2=size(S,2)
    A = Array{T, 2}(undef, s1, s2)
    for i in 1:s1,j in 1:s2
        A[i,j]=S.Vectors[i][j]
    end
    if T!=NN
        return A
    else
        S=MatrixSpace(F,s1,s2)
        return S(A)
    end
end

rang(S::VectorsSystem{T}) where {T} = rank(matrice(S)) #rang d'un système de vecteurs'

# section objets aléatoires pour générer faclement des exemples
aleaRP(n)=RP([rand() for i in 1:n])

randrat()=rand(-5:5)//rand(1:5)
aleaQP(n)=QP([randrat() for i in 1:n])
aleaFP(n)=FP([F(rand(0:4)) for i in 1:n])

aleaptsystemR(n,p)=PSR([aleaRP(n) for  i in 1:p])
aleaptsystemQ(n,p)=PSQ([aleaQP(n) for  i in 1:p])
aleaptsystemF(n,p)=PSF([aleaFP(n) for  i in 1:p])

aleamassptR(n)=RMP(aleaRP(n),rand())
aleamassptQ(n)=QMP(aleaQP(n),randrat())
aleamassptF(n)=FMP(aleaFP(n),F(rand(0:4)))

aleasysmassptR(n,p)=PMSR([aleamassptR(n) for i in 1:p])
aleasysmassptQ(n,p)=PMSQ([aleamassptQ(n) for i in 1:p])
aleasysmassptF(n,p)=PMSF([aleamassptF(n) for i in 1:p])

aleavectorR(n)=[rand() for i in 1:n]
aleavectorQ(n)=[randrat() for i in 1:n]
aleavectorF(n)=[F(rand(0:4)) for i in 1:n]

aleavectsystemR(n,p)=VSR([aleavectorR(n) for i in 1:p])
aleavectsystemQ(n,p)=VSQ([aleavectorQ(n) for i in 1:p])
aleavectsystemF(n,p)=VSF([aleavectorF(n) for i in 1:p])
#fin section random

And here’s an examle (among others) of application, namely Graham’s conve hull for a cloud of plane points.

using Plots
include("BasesAffines.jl")

getpoints(n)=aleaptsystemR(2,n)
angle_between(P1::RP,P2::RP)=atan(P2.C[2]-P1.C[2],P2.C[1]-P1.C[1])
is_left_turn(P1::RP,P2::RP,P3::RP)=(P2.C[1]-P1.C[1])*(P3.C[2]-P1.C[2])-(P2.C[2]-P1.C[2])*(P3.C[1]-P1.C[1]) >=0
Base.isless(p1::RP,p2::RP)= p1.C[2]<p2.C[2] || p1.C[2]==p2.C[2] && p1.C[1]<p2.C[1]
pivot(S::PSR)=min(S.Pts...)

function convex_hull(S::PSR)
    points=S.Pts
    LDC=pivot(S) #left down corner of cloud
    isless(p1::RP,p2::RP) = angle_between(p1,LDC)<=angle_between(p2,LDC)
    sort!(points,lt=isless)
    hull=points[1:2]
    i=3
    while i<=length(points)
        point=points[i]
        while length(hull)>1 && ! is_left_turn(hull[end-1],hull[end],point)
            pop!(hull)
        end
        push!(hull,point)
        i+=1
    end
    push!(hull,points[1])
    return hull
end

S = getpoints(30)
H=convex_hull(S)
println(H)
Points = S.Pts
x = [p.C[1] for p in Points]
y = [p.C[2] for p in Points]
p1=plot(x, y, seriestype = :scatter, legend = false)

x = [p.C[1] for p in H]
y = [p.C[2] for p in H]
p2=plot!(x, y,  legend = false)
display(p1)
display(p2)

Great thanks to you both for your help.

Just say what you want: Float64[1, 2, 3].

This problem is fixed (I was lazy even to make explicit trans-typing) . BTW [1.0,2.0,3.0] is shorter than Float64[1, 2, 3] . My constructors do the job now.

[1.,2.,3.] is even shorter

:slight_smile:

My point was that if [1, 2, 3] is interpreted as an integer array, it is not Julia’s fault.
The language is not “lazy”, rather it refuses to second-guess the programmer.

1 Like

and [1.,2,3] even shorter

1 Like