#🔒 How to find out from an array of 2D vectors if they represent a square?
ashen cape
grizzled sierra
Drawings usually contain hundreds of vectors.
echo mirage
and the question is if there are four among them that would form a square, is that correct?
grizzled sierra
and the question is if there are four among them that would form a square, is th...
The square can be made from hundreds of vectors as it's drawn
echo mirage
oh ok, I thought as long as the user kept movin the mouse in the same direction, they kept building the same vector 🙂
what if you start by grouping them by direction?
mild geyser
I would try to fit a square to the set of points with a strict constraint on the residual and if the fitting fails, then say it's not a square
not sure what a more elegant solution would be, sorry
grizzled sierra
what if you start by grouping them by direction?
Could be helpful for sure
grizzled sierra
are they just drawing straight lines?
They can draw like on any drawing software, but once the user releases left mouse button the drawing is finished. It should be able to detect shapes that represent square enough
round patrol
They can draw like on any drawing software, but once the user releases left mous...
so are they drawing individual pixels? or are they drawing line segments
grizzled sierra
They're line segments that are stored as an array of 2D vectors
round patrol
i will say that this sounds pretty non-trivial
how often do you need to run your check?
i've written something similar on bitmap data, but it was somewhat slow, and you can probably leverage some optimisations given that you can diff between frames
grizzled sierra
The program checks what the drawing is after the user releases left mouse button, so only once.
round patrol
you could try out this solution that i implemented, but there might be something better:
step 1: separate the image into distinct colour regions (e.g. by implementing some flood fill algorithm)
step 2: for each colour region, calculate how 'square' it is, e.g. how close is the actual area of the region compared to the bounding box of the region
step 3: determine if the 'squareness' of the region matches a threshold that you define
it's not the fastest algorithm in the world, especially in python i imagine (i wrote my implementation in c++), and you might have some issues using it given you have vector data, but it could work
grizzled sierra
you could try out this solution that i implemented, but there might be something...
How about the earlier suggestion to group vectors based on their direction? Then the program could find these group's start and end point and compare their rotation and distance to the other groups. The program could already dismiss drawings that have more or less than 4 groups
round patrol
what does 'group them based on direction' mean?
grizzled sierra
what does 'group them based on direction' mean?
The program would check one by one if a vector is going into the same direction as the earlier ones. If the vector isn't then it forms a new group that the next vectors will belong to or form a new one. If the player draws a square then there should be 4 groups always.
This would also take into consideration distance based on the whole scale of the drawing so small mistakes won't affect the grouping
round patrol
yeah actually that definitely could work
you'll also have to verify that the four groups are correctly angled wrt each other
and that they enclose a region
but that's probably doable with a bit of thinking
grizzled sierra
Wouldn't it be enough to just get the middle point of each group and then compare these 4 vector's rotation to each other
Around 45 degrees to the next one and 0/180 degrees to the second vector
round patrol
you'll have to deal with checking both clockwise and anticlockwise direction but yeah i think that could work
and actually bc it's a square, if you do length checking you should get the region enclosing for free
grizzled sierra
Yeah doesn't sound too difficult after all. Thank you for your help
