0

I'm looking for a way to match a list of 2D coordinates (which are in drawing order) to a shape from a list of shapes, or to find if it doesn't match any shape.

I've had a look at this, but I'm not too sure how exactly I'd relate that to things like straight/bent lines.

One idea I've thought of is to determine all the corners of each shape from the list (in order), and then check if the points from the list of coordinates that are found to be corners match one of these shapes (in the same order), using something like this. This might be a bit too strict for what I want to do however, as I want there to be a decent amount of leeway in the detection.

I'm also not sure what exactly I should use to pull corners (or lines etc.) from the list of coordinates - would it be worth turning it into an image or should I just try to detect things straight from the coordinate list?

For example, a possible input could be: Possible Input

And some shapes to match could be: Shape 1 or Shape 2 or enter image description here

And in this case, it would match the L shape.

For context, the reason I'm doing this is for a game where you have to draw symbols in the air to cast a spell.

Joe
  • 69
  • 4
  • 1
    Is the list in drawing order or a random collection of points? If you look for "corners" only you'd be able to match many different shapes. Unless your rough "L" is in the correct drawing order it could match a series of zigzag lines just as well. The problem is not detailed and specific enough to give an answer, which makes it off-topic unless you can provide much more information and constraints. – Jim Garrison Jan 09 '22 at 00:40
  • The list is in drawing order. For context, the reason I'm doing this is for a game where you have to draw symbols in the air to cast a spell, so the list is stored in the order that the player draws the symbol. I'm not too sure how to give more information - apart from the list of 2D coordinates, I don't really have anything else as I'm not too sure how to proceed from there. – Joe Jan 09 '22 at 01:31
  • 2
    maybe look into the special "handwriting" that was on the palm pilots (PDAs, before there were smartphones). some shape recognition involves encoding the strokes as a sequence of direction values, and then performing "sequence alignment". -- this is a research question. do literature review. there's gotta be plenty of research on this. you just have to start somewhere and then chase references and back-references. – Christoph Rackwitz Jan 09 '22 at 01:43
  • 1
    @Joe, there are several ways to detect patterns, some time ago I did a small adaptation to make basic patterns "teachable" without any fancy math: https://stackoverflow.com/a/19071980/1435741 – Renat Gilmanov Jan 09 '22 at 19:04
  • unfortunately I don't have the time for a detailed reponse, but hopefulyl this comment can be an optional direction. one hacky workaround I can think off is using a bit of OpenCV: dilate the points so they join/connect. Once they connect use `findContours` and use [contour features](https://docs.opencv.org/4.x/dd/d49/tutorial_py_contour_features.html) to compute extent, solidity and other derrived contour features to discern between the L/-/O shapes – George Profenza Jan 11 '22 at 13:22

1 Answers1

1

If there aren't too many distinct shapes, here is what I woud try:

  • turn the curves to a (length, angle) representation; the length can be estimated as the sums of segment lengths, and the angle as the direction of the segments;

  • to be able to compare two representations, normalize the total length to unit (this will make the comparison size-independent), and sample at regular distances; said differently, obtain a vector of N angles at points equally spaced along the curve;

  • now to recognize a curve, compute the sum of absolute differences with similar vectors obtained from reference model, and keep the smallest sum.

enter image description here

There is no need for strict accuracy.

Note that this representation is not rotation-invariant, on purpose. It is also sensitive to the drawing order (from one endpoint to the other, or conversely), this can be unwanted. Finally, beware of the closed paths (circles), that people might start anywhere.