I'm currently working on alignment software and realised that my mathematics is letting me down, hence I was hoping I could get some suggestions of formulas and methods with which to solve my problem:
I've got several quadrilaterals being automatically detected, and contour polygons made up of a variable number of single points with XY coordinates being drawn around them (see the figure here). These coordinates can be exported which yields an xml file of points listed in a clockwise fashion, but starting with a seemingly randomly chosen first point.
I would like to align these quadrilaterals, i.e. give them the same size, shape and rotation. For this I will most likely end up using an affine transform, for which I require the coordinates of the corner points.
Extracting the corner from these points seems to be more of a challenge than I had thought at first. The corners are quite rounded and there can be ones where there is no clear single point, as seen here
I'm hoping you might have some suggestions to how to best approach this? Currently, I'm considering the following procedure:
- Select a number of points that are in sequence (~test 10 points every 50 points) and draw a line (possible quadrilateral side) between the two farthest ones
- Check if all these points are located in a (more or less) straight line, using distance of a point to line formula described here
- Repeat if needed until all 4 quadrilateral sides are found
- Find the intersections of the sides and use these as corners
Since the corners are rounded, this method would leave a bit of black void around them after the affine transform. However that is still an acceptable result, as the main concern is aligning the inner contents of these quadrilaterals.
Another method I'm thinking of is:
- For each point, create a fictional triangle between it and a point a point downstream, and one point upstream. If these make more or less a right angle it'd be safe to say it's a corner.
However, this presents an issue with the rounded corners as the angles the corners make with their neighbours are often around 120 degrees or even higher. I've considered comparing every point with neighbours more than 10 points up and downstream, filtering out the angles above 91° to remove false positives. However, some of these corners are wider and thus not detected in this way. I'm seeing this method work if when I obtain a group of corners closer to eachother than they should be, I could estimate the most likely actual corner point by looking at the relative angle or position to the other possible corners.
Any suggestions would be nice, as I'm currently desperate for second opinions on these thoughts.