如何识别周围的矩形

Question

如何识别给定点的近似周围矩形？

预期输出：如下图所示。

输入：下部。

Answer 1

我的建议是做遵循两个步骤：

1. 找到点
2. 找到一个凸多边形的最小边界框可以在O（N）来解决的convex hull，这个algorithm以下

编辑：好的，其实上述2个步骤是不足以成为一个正确和接受的答案。

在这两个步骤之前，您必须先对该组点进行预处理。

1. 检查是否有3个或更多点共线，除去两个端点以外的点。
2. 第1步之后，你现在应该得到一组没有3点或多点共线的点。

检查集合的大小：如果它只剩下1点或2点，你必须特别处理它们（对于1点，你可以找到任何最小的方框来包含它自己的方法; 2点也许使他们成为边框的对角线）

如果结果集已经离开> = 3分，那么只要按照我原来的2个步骤：凸包+旋转卡钳

欢呼。

Answer 2

看起来这是一个minimzation problem with constraints。

你需要找到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) 

请注意，您可以更改目标函数以匹配其他最小化标准，如最小面积。