How to get arbitrary shapes, defined by images with transparency, to snap to one another such that there is no seam between the two?

Question

I have an application where the user can drag their images (.pngs) around on a virtual table. The images are of shapes - mostly regular polygons, but some jigsaw pieces, tetris blocks, et cetera.

I want the shapes, as they are being dragged, to snap to one another like two jigsaw pieces might.(Like in MS Word "Snap to grid")

How might I accomplish this?

Constraints:

Speed: This will be either happening as the user drags the image, or at the point of dropping. Therefore the algorithm must be fast (realtime). Any number of images may be being dragged, and there may be any number of stationary images to snap to.

No further user input: There should be no requirement for the user to do anything beyond opening the image file, and drag the images.

Possibilities:

Use some sort of concave hull algorithm + simplifaction, then match edge lengths. The issue with this is that the user's edges can't be guaranteed to be that straight/well defined.

Use a laplace transform on the transparency component of the image (To edge-detect), then treat those regions as being positively and negatively charged, and use a physical simulation to find how they snap together. Limitation: Speed, tuning.

I am currently just assuming the images are one of the regular tessellations: Rectangle, triangle or hexagon, and working from there. But i'd prefer something which works with other shapes.

Answer 1

Each shape should have some reference points and a (possibly curved) line between them. If you need to snap two shapes then the easiest would be to match those reference points first, and if they match then you can match the lines between each two pair of points. Lines should be coded in such a way that you don't need some mathemathical processing to match them, just match the parameters of the lines.

Take tetris blocks. Each block has reference points on grid crossings, and each line is a straight line. A square shape would have 8 points and lines, and L shape would have 10 points/lines. First match reference points, and then match if same points on each shape have the lines between them (and take line orientation into regard).

Take jigsaw puzzles. Usually you have 4 points/lines, but lines are some arbitrary curves. You can actually use mathematical curves, but you can also have some jigsaw curve index for each curve. When you try to match two pieces first you match reference points, and then you match curves by simply comparing their indexes, in regard to both their line orientation and their index pairings.