给定一组有序的2D像素位置（相邻或相邻对角线），形成了一个完整的路径，没有重复的点。如何确定其周长是该像素集合的多边形的最大线性维度？（其中GLD是集合中任意两个点之间的最大线性距离）
对于我的目的，显而易见的O(n^2)解决方案可能不够快，针对数千个点的图形。是否有良好的启发式方法或查找方法，能将时间复杂度降至O(n)或O(log(n))？
5个回答
18
一种简单的方法是首先找到点的凸包，这可以用许多方法在O(n log n)时间内完成。[我喜欢Graham scan（见animation），但incremental算法也很流行，还有others，尽管有些需要more time。]
然后，通过从凸包上任选两个点（如x和y）开始，顺时针移动y直到它离x最远，然后移动x，再移动y等等，来找到最远的一对（即直径）。你可以证明整个过程只需要O(n)时间（摊销）。所以总共是O(n log n)+O(n)=O(n log n)，如果你使用gift-wrapping作为你的凸包算法，则可能是O(nh)。这个想法被称为rotating calipers，正如你所提到的。
然后，通过从凸包上任选两个点（如x和y）开始，顺时针移动y直到它离x最远，然后移动x，再移动y等等，来找到最远的一对（即直径）。你可以证明整个过程只需要O(n)时间（摊销）。所以总共是O(n log n)+O(n)=O(n log n)，如果你使用gift-wrapping作为你的凸包算法，则可能是O(nh)。这个想法被称为rotating calipers，正如你所提到的。
这里是计算几何研究者David Eppstein编写的代码（也可以参考他的Python算法和数据结构）。
所有这些都不难编码（最多应该只有一百行；在上面的Python代码中少于50行），但在你开始编码之前，你首先应该考虑是否真的需要它。如果像你说的那样，你只有“数千个点”，那么平凡的O(n^2)算法（比较所有对）将在任何合理的编程语言中在不到一秒钟内运行。即使有一百万个点，也不应该超过一小时。:-)
你应该选择最简单的有效算法。
- ShreevatsaR
2
在这个页面上：
它展示了如何在O(n)时间内确定凸多边形的最大直径。我只需要先将我的点集转换为凸多边形（可能使用Graham扫描）。
以下是我找到的一些用于计算凸包的C#代码：
- Jared Updike
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;
}
}
- Jared Updike
0
你可以画一个比多边形更大的圆，然后慢慢缩小它，检查是否已经相交。这样你的直径就是你要找的数字。
不确定这是否是一种好方法，听起来介于O（n）和O（n ^ 2）之间。
- Karl
2
你会把中心放在哪里？可能靠近质心，但我敢打赌，在某些情况下，该圆的中心对于是否找到正确的GLD有重要影响。 - Jared Updike
2这个概念上有缺陷——等边三角形的外接圆直径是它的边长的sqrt(3)倍，等于GLD。 - Jimmy
0
我的即兴解决方案是尝试二分法，其中您在中间某处画一条线，并检查所有点与该线中心的距离。这将为您提供两个可能非常遥远的点。然后检查这两个点之间的距离，并重复上述距离检查。重复此过程一段时间。
我的直觉告诉我，这是一个n log n启发式算法，可以让你接近答案。
- Paul Nathan
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接