找到最佳矩形

Question

Point[] pathPoints=new Point[n];
怎么样从这些点中找到出一个包含这些点的矩形 ,矩形可能有角度
有算法

Answer 1

前题要有高数基础知识。
方法如下：
1:计算n个点中任何一个点与其它n-1个点之间真线距离，并求出距离最长的两点。（这两点之间的长度就是这个矩形的“长”或“宽”，这里就作“长”吧）。-----得出矩形的“长”了。
2:以在1中出的两点作直线L。
3:在除去1中两点外的n-2个点中，计算这些点有多少在这条直线上。假设有m个。
4：在剩余的n-2-x个点中分析出两部分S1和S2，他们分别位于直线L的左边或右边。（也可以是上面或下面）。
5：计算S1中所有点到直线L的绝对距离中最大的，记为m1。
6：计算S2中所有点到直线L的绝对距离中最大的，记为m2。
7：m1+m2的值则为这个矩形的“宽”。