Reducing set of cartesian coordinates due to symmetry

New to Julia
1

My Question:
I have written a Julia function that does this reduction (see below). It works.

However, I have a feeling, that this being Julia, that there is an easier, cleverer, or more efficient method to reduce this set based on symmetry.

Background:
Coordinates on a cartesian plane may exhibit several symmetries to each other: y-axis symmetry, x-axis symmetry, origin symmetry, symmetry over y=x, and symmetry over y=-x.

The problem is: given a set of coordinates, reduce the set by taking out any point that is symmetric to another point.

If a point has coordinates (r,c), then the set of symmetric points is (r,-c), (-r,c), (c,r), (-c,r), (-r,-c), (c,-r), (-c,r)

Example:
The set of points (3,2), (2,3), (3, 4), (4,3)

First center the points around (0,0) by subtracting (3,3) from each point

resulting set: (0,-1), (-1, 0), (0, 1), (1,0)

This set has maximum symmetry – each point is symmetric to some other point.

The correct result is then any of the points from the set.

My function will return (0,1) – or (3,4) before centering.

Overview of Function:
It uses scoreboarding to mark points that are determined to be symmetric with any other point, then reduces the set to those points that weren’t identified to be symmetric to any other point.

In the above example, the scoreboard ends up with these values:

Dict{point, Int64} with 4 entries:
  point(0, 1)  => 0
  point(1, 0)  => 1
  point(-1, 0) => 1
  point(0, -1) => 1

The points with values 0 are chosen; in this case, point(0,1). When the offsets are added back, it becomes point(3,4)

The Function:

struct point
    r::Int32
    c::Int32
end

function symreduce(ys::Set,offsetr::Integer,offsetc::Integer)

    if length(ys) > 1

        # transform points by subtracting offset from r,c
        coord_set = Set([])
        for pt in ys
            newpt = Set([point(pt.r-offsetr,pt.c-offsetc)])
            union!(coord_set,newpt)
        end

        ptc = collect(coord_set)

        sym_score = Dict{point,Int32}()
        for pt in ptc
            sym_score[pt]=0
        end 

        for i in 1:length(ptc)
            r = ptc[i].r
            c = ptc[i].c 
            check_pt = Set([point(r,c)])
            sym_set = Set([point(r,-c),point(-r,c),point(c,r),point(-c,-r),point(-r,-c),point(c,-r),point(-c,r)])
            for j in i+1:length(ptc)
                test_pt = Set([ptc[j]])
                if length(union(test_pt,sym_set))==length(sym_set)
                    sym_score[ptc[j]] = 1
                end
            end
        end
        
        final_set = findall(x->x==0,sym_score)

    else
        return(ys)
    end 
    
    # add offset back to final set
    return_set = Set([])
    for pt in final_set
        newpt = Set([point(pt.r+offsetr,pt.c+offsetc)])
        union!(return_set,newpt)
    end

    return(return_set)

end

Examples of using the function:

julia> my_set1 = Set([point(3,2),point(2,3), point(4,3), point(3,4)])
Set{point} with 4 elements:
  point(3, 2)
  point(2, 3)
  point(3, 4)
  point(4, 3)

julia> symreduce(my_set1,3,3)
Set{Any} with 1 element:
  point(3, 4)

julia> my_set2 = Set([point(7,9), point(9,9), point(11,13), point(10,13), point(11,13), point(12,12)])
Set{point} with 5 elements:
  point(12, 12)
  point(11, 13)
  point(10, 13)
  point(9, 9)
  point(7, 9)

julia> symreduce(my_set2,8,7)
Set{Any} with 4 elements:
  point(12, 12)
  point(11, 13)
  point(10, 13)
  point(7, 9)
2

First of all, you could use StaticArrays to make your struct into a vector like object. (By the way, in Julia it would be more common to use capitalised names for types, i.e. Point instead of point.)
Then you could define a way how to uniquely identify each point to an equivalent point.

using StaticArrays

struct point <: FieldVector{2, Int32}
    r::Int32
    c::Int32
end

function unique_rep(p)
    r, c = p.r, p.c 
    return point(min( (r,c), (r,-c), (-r,c), (c,r), 
                      (-c,r), (-r,-c), (c,-r), (-c,r)))
end


function symreduce(ys, offset = point(0,0))
    unique_pts = []

    for pt in ys 
        unique_pt = unique_rep(pt - offset) + offset
        push!(unique_pts, unique_pt) 
    end

    return Set(unique_pts)
end

my_pts1 = [point(3,2),point(2,3), point(4,3), point(3,4)]
symreduce(my_pts1, point(3,3)) # == point(2, 3)
3

From a type-stability point of view, the symreduce function is better written as

julia> function symreduce2(ys, offset = point(0,0))
           unique_pts = map(ys) do pt 
                unique_rep(pt - offset) + offset
           end

           return Set(unique_pts)
       end
symreduce2 (generic function with 2 methods)

julia> symreduce(my_pts1, point(3,3))
Set{Any} with 1 element:
  Int32[2, 3]

julia> symreduce2(my_pts1, point(3,3))
Set{point} with 1 element:
  Int32[2, 3]
1 Like
4

Thank you both for your answers. I learned something from each!

5

There’s an inbuilt CartesianIndex type for storing cartesian (integer) coordinates, which you can use here as well.

const CI = CartesianIndex # just an alias to make the type name shorter

function unique_rep(p)
  r, c = Tuple(p)
  r, c = min(r, -r), min(c, -c)
  return CI(min((r, c), (c, r)))
end

function symreduce(ys, offset = CI(0,0))
  unique_pts = Set{CI}()

  for pt in ys 
    unique_pt = unique_rep(pt - offset) + offset
    push!(unique_pts, unique_pt) 
  end

  return unique_pts
end

function main()
  my_pts1 = [CI(3,2),CI(2,3), CI(4,3), CI(3,4)]
  symreduce(my_pts1, CI(3,3)) # == CI(2, 3)
end
2 Likes
6

That is super nice :slightly_smiling_face: so short and elegant!

1 Like