(x,y)
排列,点集 { (0,0), (1,5), (2,1), (2,10) }
,连接点1和点3不是得到最小角度的方法吗?(啊,我看你已经在问题上发表了这样的评论...)。 - Will Ness对点进行排序(或使用哈希映射)以找出是否存在任何水平线。
然后在双重平面上解决此问题。您只需要找到最左和最右的交点。使用二分搜索查找一对水平坐标,使得所有交点都在它们之间。(您可以通过从这些坐标继续进行二分搜索来快速找到近似结果)。
然后按照它们在双重平面上的切线对行进行排序。对于在此排序顺序中相邻的线对,找到最靠近水平坐标的交点。这不能保证在原始平面上有些线条几乎水平的最差情况下具有好复杂度。但在大多数情况下,时间复杂度将由排序确定:O(N log N) + O(二分搜索复杂度)。