How to determine the surrounding rectangle

Question

How to determine the approximate surrounding rectangle of these points?

Expected Result: as shown at the top of the image below.

Entrance: lower part.

Answer 1

My suggestion is as follows:

• Find the convex case of points
• Find the minimum bounding rectangle of a convex polygon can be solved in O (n), following this algorithm

Edited . In fact, the above 2 steps are not enough to be the correct and accepted answer.

.

• , , , .
• 1 , 3 , .

: 1 2 , ( 1 , ; ?)

>= 3 , 2 : +

.

Answer 2

, .

4 :

l1: a1x + b1y + c1 = 0
l2: a1x + b1y + c2 = 0
l3: a2x + b2y + c3 = 0
l4: a2x + b2y + c4 = 0

, 8 : a1,a2,b1,b2,c1,c2,c3,c4

:

Sum(distance(li,point_j) | i from [1,4], j - over all points)

:

l1 dot l3 = 0  [ensuring rectangle - cosine=0->angle between lines=90]
for each point j:
a1xj + b1yj + c1 >=0 ['above' l1]
a1xj + b1yj + c2 <= 0 ['below' l2]
(similarly for l3,l4)

. , , .