heuristics

I needed a way to draw very small quadrilaterals around rows of cells, that may only be a cell or two thick, perhaps less. And it needed to be extremely precise (within micrometers perhaps). I knew the 4 points of the borders, but to get the right surrounding polygon, I had to adjust to the corners of the 4 borderline cells. The image there demonstrates the essential problem. The 4 dots are my four points. I found that I could divide these points into quadrants. If a point is in quadrant I, use corner I, if point in quad II use corner 2 of that cell, etc. This heuristic is easy for the 4 corner cells. But it is generalizable to n-sided polygon if you simply solve the two XY lines, through the center of gravity, that divide the system of points into a minimum distance btwn all points. For every point that is quad I, etc etc etc. In our case there are just 4 points and the problem is just to decide which gets adjusted to which corner.

That is where the triangles you see in the image come into effect. I spent many days sketching this out to arrive at this heuristic. I had virtually limitless amount of data to test it with. I could never get the problem down to something that is solvable in reasonable time. (the complete way to mark everything without this polygon approach takes exponential time - this quick heuristic approach adds a trivial computation time to our other processes we're doing on this data).

The problem became that very often two cells of the "quadrilateral" were identical, so it was then kinda hopeless to figure out how to shift each one so that a bounding polygon is made that contains exactly the right extents of the single row or triangle within that row. If you think about it and visualize the problem, it sounds rather simple. But just visualizing it can be difficult. I was very surprised because this seems like such a banal thing. Any child could draw the correct bounding polygon, but to express it in an algorithm was not so easy. The idea of solving the two lines which form axes btwn the minimum distance through the center of gravity btwn all 4 points was a good first step. But I found that solving this equation required some calculus with multiple variables and I had to turn back. It's probably really easy with some linear algebra because it reminds me of a coordinate system rotation - but it's definitely out of my league to solve that problem in the few days I had. Anyhow, the simplistic realworld constraint of only 4 bounding points led to a different approach. I found that rathter than finding the exact minimum axes, I just took the average x and the average y. Then, if you simply calculate the angles btwn the immediately adjacent points to the average x and average y, you can then choose a quadrant to assign each corner point. The angle will either be greater than or less than 45°, because it is constrained by the average.

I know this just comes across as handwaving, and I guess a lot of it is! since I was scared of solving the calculus system equations of the axes through the center of gravity, which form the minimum distance between all 4 points (as sketched in the image at the top). My english writeup of this is not very easy to follow, but lord, the takeaway story is that sometimes it just pays to be inventive. And holy dogs! my approach works! And it's as trivial as averaging numbers and performing a few angle calculations. No iterations necessary.