CODEWITHSUNDEEP
algorithm
Jens
Jens

Reputation: 145

Polygon congruence algorithm

Does anyone know an algorithm which checks for congruence between two sets of polygons? To be more specific, see the figure below. Triangle

I'm looking for a way to check whether a given set of colored triangles is congruent to another set, i.e. whether a given set (e.g. the blue triangles) via a number of translations, rotations or reflections can be superimposed on another set (e.g. the red triangles). In the example above, all 3 sets of triangles (blue, red and green) are congruent.

The actual triangle I'm working on is larger than this and has more sets.

I've googled and found this paper, but it concerns 3-D polygons and isn't directly (in my view) implementable.

Any constructive ideas or links would be welcome.

Edit

Just to clarify, each set of triangles must be treated as a whole connected figure, i.e. each triangle in the set is fixed in it's position relative to the other triangles in the set.

Also, I only need an algorithm which could determine whether one set of triangles is congruent to another set, but with a much larger triangle than the one above and with many more sets. Imagine a triangle with side length N and a total of N^2 smaller triangles, divided into N differently colored sets of N triangles.

Upvotes: 3

Views: 799

Answers (1)

mcdowella
mcdowella

Reputation: 19601

A combination of rotations and reflections can be represented by a rotation and at most one reflection, so you can ignore reflections if you run a rotation-only algorithm twice, once with the original figure and once with a reflected figure.

The centre of gravity of the triangles (or, easier, the centre of gravity of a figure which has mass only at the vertices of the triangles) is not affected by rotation, so I would start by computing the centre of gravity of each figure. Now represent the figure by a list giving the direction and distance of each point in the figure from its centre of gravity.

If the set of distances are different the figures cannot be rotations of each other, and I guess most non-congruencies will be spotted at this stage. For total cost N^2 you can consider rotating a vertex in one figure to each possible vertex of the other figure and then applying this calculated rotation to all of the other vertices and seeing if they match up. Possibly some version of https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation could be used to speed this up. It may help to represent directions by the angle between the directions to vertices after sorting them into order.

Upvotes: 3

Related Questions