给定一组有序的 2D 像素位置（相邻或相邻对角线），它们形成一条没有重复的完整路径，如何确定周长为该组像素的多边形的最大线性尺寸？（其中 GLD 是集合中任何一对点的最大线性距离）
对于我的目的，显而易见的 O(n^2) 解决方案对于数千点的数字可能不够快。是否有良好的启发式或查找方法可以使时间复杂度更接近 O(n) 或 O(log(n))？
Jared Updike
问问题
5680 次
5 回答
18
一种简单的方法是首先找到点的凸包，这可以通过多种方式在 O(n log n) 时间内完成。[我喜欢格雷厄姆扫描（见动画），但增量算法也很流行，其他算法也很流行，虽然有些需要更多时间。]
然后你可以通过从凸包上的任意两个点（比如 x 和 y）开始，顺时针移动 y 直到它离 x 最远，然后移动 x，再次移动 y 等，找到最远的对（直径）。你可以证明整个事情只需要 O(n) 时间（摊销）。所以它总共是 O(n log n)+O(n)=O(n log n)，如果你使用礼物包装作为凸包算法，可能是 O(nh)。正如你提到的，这个想法被称为旋转卡尺。
这是David Eppstein（计算几何研究员；另请参阅他的Python 算法和数据结构以供将来参考）的代码。
所有这些都不是很难编码（最多应该是一百行；在上面的 Python 代码中少于 50 行），但在你这样做之前——你应该首先考虑你是否真的需要它。如果如您所说，您只有“数千个点”，那么在任何合理的编程语言中，简单的 O(n^2) 算法（比较所有对）将在不到一秒的时间内运行。即使有一百万点，也不应该超过一个小时。:-)
您应该选择最简单的有效算法。
于 2008-11-26T22:40:23.770 回答
2
在本页面：
它表明您可以在 O(n) 中确定凸多边形的最大直径。我只需要先将我的点集变成一个凸多边形（可能使用格雷厄姆扫描）。
这是我在计算凸包时遇到的一些 C# 代码：
于 2008-11-26T20:16:13.373 回答
2
我将 Python 代码移植到 C#。它似乎工作。
using System;
using System.Collections.Generic;
using System.Drawing;
// Based on code here:
// http://code.activestate.com/recipes/117225/
// Jared Updike ported it to C# 3 December 2008
public class Convexhull
{
// given a polygon formed by pts, return the subset of those points
// that form the convex hull of the polygon
// for integer Point structs, not float/PointF
public static Point[] ConvexHull(Point[] pts)
{
PointF[] mpts = FromPoints(pts);
PointF[] result = ConvexHull(mpts);
int n = result.Length;
Point[] ret = new Point[n];
for (int i = 0; i < n; i++)
ret[i] = new Point((int)result[i].X, (int)result[i].Y);
return ret;
}
// given a polygon formed by pts, return the subset of those points
// that form the convex hull of the polygon
public static PointF[] ConvexHull(PointF[] pts)
{
PointF[][] l_u = ConvexHull_LU(pts);
PointF[] lower = l_u[0];
PointF[] upper = l_u[1];
// Join the lower and upper hull
int nl = lower.Length;
int nu = upper.Length;
PointF[] result = new PointF[nl + nu];
for (int i = 0; i < nl; i++)
result[i] = lower[i];
for (int i = 0; i < nu; i++)
result[i + nl] = upper[i];
return result;
}
// returns the two points that form the diameter of the polygon formed by points pts
// takes and returns integer Point structs, not PointF
public static Point[] Diameter(Point[] pts)
{
PointF[] fpts = FromPoints(pts);
PointF[] maxPair = Diameter(fpts);
return new Point[] { new Point((int)maxPair[0].X, (int)maxPair[0].Y), new Point((int)maxPair[1].X, (int)maxPair[1].Y) };
}
// returns the two points that form the diameter of the polygon formed by points pts
public static PointF[] Diameter(PointF[] pts)
{
IEnumerable<Pair> pairs = RotatingCalipers(pts);
double max2 = Double.NegativeInfinity;
Pair maxPair = null;
foreach (Pair pair in pairs)
{
PointF p = pair.a;
PointF q = pair.b;
double dx = p.X - q.X;
double dy = p.Y - q.Y;
double dist2 = dx * dx + dy * dy;
if (dist2 > max2)
{
maxPair = pair;
max2 = dist2;
}
}
// return Math.Sqrt(max2);
return new PointF[] { maxPair.a, maxPair.b };
}
private static PointF[] FromPoints(Point[] pts)
{
int n = pts.Length;
PointF[] mpts = new PointF[n];
for (int i = 0; i < n; i++)
mpts[i] = new PointF(pts[i].X, pts[i].Y);
return mpts;
}
private static double Orientation(PointF p, PointF q, PointF r)
{
return (q.Y - p.Y) * (r.X - p.X) - (q.X - p.X) * (r.Y - p.Y);
}
private static void Pop<T>(List<T> l)
{
int n = l.Count;
l.RemoveAt(n - 1);
}
private static T At<T>(List<T> l, int index)
{
int n = l.Count;
if (index < 0)
return l[n + index];
return l[index];
}
private static PointF[][] ConvexHull_LU(PointF[] arr_pts)
{
List<PointF> u = new List<PointF>();
List<PointF> l = new List<PointF>();
List<PointF> pts = new List<PointF>(arr_pts.Length);
pts.AddRange(arr_pts);
pts.Sort(Compare);
foreach (PointF p in pts)
{
while (u.Count > 1 && Orientation(At(u, -2), At(u, -1), p) <= 0) Pop(u);
while (l.Count > 1 && Orientation(At(l, -2), At(l, -1), p) >= 0) Pop(l);
u.Add(p);
l.Add(p);
}
return new PointF[][] { l.ToArray(), u.ToArray() };
}
private class Pair
{
public PointF a, b;
public Pair(PointF a, PointF b)
{
this.a = a;
this.b = b;
}
}
private static IEnumerable<Pair> RotatingCalipers(PointF[] pts)
{
PointF[][] l_u = ConvexHull_LU(pts);
PointF[] lower = l_u[0];
PointF[] upper = l_u[1];
int i = 0;
int j = lower.Length - 1;
while (i < upper.Length - 1 || j > 0)
{
yield return new Pair(upper[i], lower[j]);
if (i == upper.Length - 1) j--;
else if (j == 0) i += 1;
else if ((upper[i + 1].Y - upper[i].Y) * (lower[j].X - lower[j - 1].X) >
(lower[j].Y - lower[j - 1].Y) * (upper[i + 1].X - upper[i].X))
i++;
else
j--;
}
}
private static int Compare(PointF a, PointF b)
{
if (a.X < b.X)
{
return -1;
}
else if (a.X == b.X)
{
if (a.Y < b.Y)
return -1;
else if (a.Y == b.Y)
return 0;
}
return 1;
}
}
于 2008-12-03T20:20:24.287 回答
0
你可以画一个比多边形大的圆并慢慢缩小它，检查你是否与任何点相交。那么你的直径就是你要找的数字。不确定这是否是一个好方法，它听起来介于 O(n) 和 O(n^2) 之间
于 2008-11-26T20:21:44.173 回答
0
我的现成解决方案是尝试二进制分区方法，您在中间画一条线 somwwhere 并检查所有点与该线中间的距离。这将为您提供 2 个大概非常远的点。然后检查这两者的距离并重复上述距离检查。重复这个过程一段时间。
我的直觉说这是一个 n log n 启发式，会让你非常接近。
于 2008-11-26T20:25:02.357 回答