问各位大佬几个数学问题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2658 天前的主题，其中的信息可能已经有所发展或是发生改变。

这两个问题是在写 https://github.com/pqpo/SmartCropper 的时候遇到的，厚脸皮的求个 start ！

已知四个点的坐标，如何确定这四个点分别为左上，右上，右下，左下。主观上很容易确定，四个顶点依次相连，然后判断一下是左倾还是右倾，根据倾斜程度以 45 度作为临界点确定。

接下来是判断是否为凸四边形，这个相对容易一些，确定出顶点位置之后，对角线相连，如果另外两个顶点分别位于对角线两侧，那么这个四边形就是凸四边形。

第 1 条附言 · 2017-08-07 18:32:42 +08:00

SmartCropper: https://github.com/pqpo/SmartCropper

对角线

四边形

顶点

确定

15 条回复 • 2017-08-07 20:55:05 +08:00

Chingim

2017-08-07 17:12:28 +08:00 via Android

这是问问题吗？

em84

2017-08-07 17:13:39 +08:00

你开始了

momocraft

2017-08-07 17:16:13 +08:00

如果这四个点是正方形 (0, 1) (1, 0) (2, 1) (1, 2) ，应该选哪个为左上?

jmc891205

2017-08-07 17:20:06 +08:00

我来做的话我就取纵坐标最大的两个点其中横坐标小的那个是左上大的那个是右上
左下右下类似

QAPTEAWH

2017-08-07 17:23:46 +08:00

扫描线？

好像先要证明“左上，右上，右下，左下”确实可被定义，可能只有凸四边形能定义这个？

yunkchen

2017-08-07 17:27:27 +08:00

谜底就在谜面里？

RLib

2017-08-07 17:55:54 +08:00

角点检测 goodFeaturesToTrack 或者多边形逼近 approxPolyDP，计算最小包围矩形 minAreaRect，得到一个 angle 和 4 个点，去比较下距离就得出了

RLib

2017-08-07 17:59:04 +08:00

答偏了撤回

pqpo

2017-08-07 18:28:25 +08:00

@momocraft 这个刚好是临界情况，实际代码中可以自行定义，比如（ 1,0 ）为左上

pqpo

2017-08-07 18:28:44 +08:00

@RLib 撤回无效

pqpo

2017-08-07 18:29:59 +08:00

@QAPTEAWH 使用 approxPolyDP 逼近出的多边形应该是凸四边形。所以还有一个已知条件就是凸四边形

am241

2017-08-07 18:34:48 +08:00 via Android

求各顶点和四边形重心连线的角度，做排序

pqpo

2017-08-07 18:41:43 +08:00

@RLib 是否可以这样，将 4 点作为 boundingRect 的输入计算外接矩形（非最小外接矩形），这样产生的矩形四个顶点应该是按顺序的，以确定左上为例，距离这个外接矩形左上顶点距离最近的即为左上。

willchen

2017-08-07 20:47:14 +08:00

如果是凸四边形，任意取一点和剩下的 3 点构成的三角形的线段的直线判断位置关系是否可行？

Cbdy

2017-08-07 20:55:05 +08:00

我说一个
作一个边法向量分别为(1,1)，(1,-1)的平行四边形作为该多边形的外接多边形，该多边形与平行四边形的交点即为所求点。。
试试看= =#