How to identify the surrounding rectangle
algorithm, graph-algorithm, image-recognition
Solution
My suggestion is do the follow two steps:
- Find the convex hull of the points
- Find a minimum bounding box of a convex polygon can be solved in O(n), following by this algorithm
Edited: Okay actually the above 2 steps is not enough to be a correct and accepted answer.
Before these 2 steps, you have to preprocess the set of point first.
- Check if any 3 or more points are collinear, remove those points except the two end points.
- After step 1, you should now get a set of points that have no 3 or more points are collinear.
check the size of set : if it has only 1 point or 2 points left, you have to special handle them (for 1 point you may just find any minimal box to contain it by your own method; for 2 points maybe make them become the bounding box's diagonal?)
If the resulting set has >= 3 points left, then just follow my original 2 steps: convex hull + rotating calipers
cheers.
Problem
How to identify the approximate surrounding rectangle of the given dots? Expected output: as shown by the upper part of the below image. Input: the lower part.