# Reducing set of cartesian coordinates due to symmetry

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)
``````

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)
``````

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

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

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

That is super nice so short and elegant!

1 Like