获取最少数量的点来创建相同的多边形
Get minimal amount of points to create the same polygon
我想做的事情：
我想从将创建相同多边形的多边形中获取最少量的点：
例如，如果我有这个多边形：
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0,4), (4,4)
它将创建一个位置为0, 0、宽度为4、高度为4的多边形。
如果我将此多边形输入到假设算法中，它将 return:
(0, 0), (4, 0), (0, 4), (4, 4)
我为什么要做：
我正在创建一个游戏，游戏有动画，每个动画都有自己的图像和多边形（图像的边界），我已经有了动画的图像，但我没有当然，我可以自己创建多边形，但是手动为 100 多张图像创建多边形会很累，更不用说 adding/modifying 动画了。
我试过的：
我的想法是这样的：
逐个像素扫描图像，检查像素是否为空白，如果不是，将其添加到列表中，完成后使用某种算法获得最少的点创建相同的多边形。
我做了一些研究，我认为 LLTS（广场万岁）算法是我需要的，所以我在 C# 中使用 cansik's implementation 编写了这段代码：
private readonly Bitmap _image;
private Point[] _result;
private void Calculate()
{
List<Vector2D> points = new List<Vector2D>();
for (int x = 0; x < _image.Width; x++)
{
for (int y = 0; y < _image.Height; y++)
{
// Check if the pixel is blank
if (_image.GetPixel(x, y).ToArgb() != 16777215)
{
// If the pixel isn't blank, add it to the list
points.Add(new Vector2D(x, y));
}
}
}
Vector2D[] resultInVectors = GeoAlgos.MonotoneChainConvexHull(points.ToArray());
_result = new Point[resultInVectors.Length];
for (int i = 0; i < resultInVectors.Length; i++)
{
_result[i] = new Point((int)resultInVectors[i].X, (int)resultInVectors[i].Y);
}
}
我添加了绘画代码：
private void Form_Paint(object sender, PaintEventArgs e)
{
e.Graphics.DrawPolygon(Pens.Black, _result);
e.Graphics.DrawImage(_image, new Point(100, 0));
}
最后，我 运行 这个程序，这就是我得到的：
这不是我想要的，至少可以说，我希望它是这样的：
有什么想法吗？
编辑 - 最终解决了它
我使用了 Wowa's answer to Trevor Elliott's question，然后，我通过使用我创建的这个函数最小化了结果中的点数：
private static List<Point> MinimizePoints(List<Point> points)
{
if (points.Count < 3)
{
return points;
}
List<Point> minimumPoints = new List<Point>(points);
for (int i = minimumPoints.Count - 1; i > 2; i -= 3)
{
List<Point> currentPoints = minimumPoints.GetRange(i - 3, 3);
try
{
if ((currentPoints[2].X - currentPoints[0].X) / (currentPoints[1].X - currentPoints[0].X) ==
(currentPoints[2].Y - currentPoints[0].Y) / (currentPoints[1].Y - currentPoints[0].Y))
{
minimumPoints.Remove(minimumPoints[i + 1]);
}
}
catch (DivideByZeroException)
{
// Ignore
}
}
return minimumPoints;
}
我用了Oliver Charlesworth's answer to Prashant C's question.
第二次编辑 - 更优化的解决方案
我没有使用我自己的 meh 算法来减少点数，而是使用了 Ramer–Douglas–Peucker 算法并将 ε（公差）设置为 0。这是我使用的实现：
private static class DouglasPeuckerReduction
{
public static Point[] ReducePoints(Point[] existingPolygon)
{
if (existingPolygon == null || existingPolygon.Length < 3)
return existingPolygon;
int firstPoint = 0;
int lastPoint = existingPolygon.Length - 1;
List<int> pointIndexsToKeep = new List<int>();
//Add the first and last index to the keepers
pointIndexsToKeep.Add(firstPoint);
pointIndexsToKeep.Add(lastPoint);
//The first and the last point cannot be the same
while (existingPolygon[firstPoint].Equals(existingPolygon[lastPoint]))
{
lastPoint--;
}
ReducePoints(existingPolygon, firstPoint, lastPoint,
0, ref pointIndexsToKeep);
pointIndexsToKeep.Sort();
return pointIndexsToKeep.Select(index => existingPolygon[index]).ToArray();
}
/// <summary>
/// Douglases the peucker reduction.
/// </summary>
/// <param name="points">The points.</param>
/// <param name="firstPoint">The first point.</param>
/// <param name="lastPoint">The last point.</param>
/// <param name="tolerance">The tolerance.</param>
/// <param name="pointIndexesToKeep">The point index to keep.</param>
private static void ReducePoints(IReadOnlyList<Point> points, int firstPoint, int lastPoint, double tolerance,
ref List<int> pointIndexesToKeep)
{
double maxDistance = 0;
int indexFarthest = 0;
for (int index = firstPoint; index < lastPoint; index++)
{
double distance = PerpendicularDistance
(points[firstPoint], points[lastPoint], points[index]);
if (distance > maxDistance)
{
maxDistance = distance;
indexFarthest = index;
}
}
if (maxDistance > tolerance && indexFarthest != 0)
{
//Add the largest point that exceeds the tolerance
pointIndexesToKeep.Add(indexFarthest);
ReducePoints(points, firstPoint,
indexFarthest, tolerance, ref pointIndexesToKeep);
ReducePoints(points, indexFarthest,
lastPoint, tolerance, ref pointIndexesToKeep);
}
}
/// <summary>
/// The distance of a point from a line made from point1 and point2.
/// </summary>
/// <param name="pt1">The PT1.</param>
/// <param name="pt2">The PT2.</param>
/// <param name="p">The p.</param>
/// <returns></returns>
private static double PerpendicularDistance
(Point Point1, Point Point2, Point Point)
{
//Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)| *Area of triangle
//Base = v((x1-x2)²+(x1-x2)²) *Base of Triangle*
//Area = .5*Base*H *Solve for height
//Height = Area/.5/Base
double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X *
Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X *
Point2.Y - Point1.X * Point.Y));
double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
Math.Pow(Point1.Y - Point2.Y, 2));
double height = area / bottom * 2;
return height;
}
}
我认为@ShashwatKumar 的回答误解了你的问题？如果不是，那就是我误会了！
我读你的 post 的方式，你正在寻找你的图形的多边形轮廓。这称为跟踪二值图像contour/outline，其第一步，
正如@EugeneKomisarenko 在评论中所说，是 "edge detection" （但随后
是进一步的步骤）。
搜索这些短语的变体会影响许多算法，例如：
图片来自this link.
而且你不想去寻找真正最小的兔子洞：
“Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?”
因为这是众所周知的棘手问题（从技术上讲，NP 难）。
我想做的事情：
我想从将创建相同多边形的多边形中获取最少量的点：
例如，如果我有这个多边形：
(0, 0), (1, 0), (2, 0), (3, 0), (4, 0), (0,4), (4,4)
它将创建一个位置为0, 0、宽度为4、高度为4的多边形。
如果我将此多边形输入到假设算法中，它将 return:
(0, 0), (4, 0), (0, 4), (4, 4)
我为什么要做：
我正在创建一个游戏，游戏有动画，每个动画都有自己的图像和多边形（图像的边界），我已经有了动画的图像，但我没有当然，我可以自己创建多边形，但是手动为 100 多张图像创建多边形会很累，更不用说 adding/modifying 动画了。
我试过的：
我的想法是这样的：
逐个像素扫描图像，检查像素是否为空白，如果不是，将其添加到列表中，完成后使用某种算法获得最少的点创建相同的多边形。
我做了一些研究，我认为 LLTS（广场万岁）算法是我需要的，所以我在 C# 中使用 cansik's implementation 编写了这段代码：
private readonly Bitmap _image;
private Point[] _result;
private void Calculate()
{
List<Vector2D> points = new List<Vector2D>();
for (int x = 0; x < _image.Width; x++)
{
for (int y = 0; y < _image.Height; y++)
{
// Check if the pixel is blank
if (_image.GetPixel(x, y).ToArgb() != 16777215)
{
// If the pixel isn't blank, add it to the list
points.Add(new Vector2D(x, y));
}
}
}
Vector2D[] resultInVectors = GeoAlgos.MonotoneChainConvexHull(points.ToArray());
_result = new Point[resultInVectors.Length];
for (int i = 0; i < resultInVectors.Length; i++)
{
_result[i] = new Point((int)resultInVectors[i].X, (int)resultInVectors[i].Y);
}
}
我添加了绘画代码：
private void Form_Paint(object sender, PaintEventArgs e)
{
e.Graphics.DrawPolygon(Pens.Black, _result);
e.Graphics.DrawImage(_image, new Point(100, 0));
}
最后，我 运行 这个程序，这就是我得到的：
这不是我想要的，至少可以说，我希望它是这样的：
有什么想法吗？
编辑 - 最终解决了它
我使用了 Wowa's answer to Trevor Elliott's question，然后，我通过使用我创建的这个函数最小化了结果中的点数：
private static List<Point> MinimizePoints(List<Point> points)
{
if (points.Count < 3)
{
return points;
}
List<Point> minimumPoints = new List<Point>(points);
for (int i = minimumPoints.Count - 1; i > 2; i -= 3)
{
List<Point> currentPoints = minimumPoints.GetRange(i - 3, 3);
try
{
if ((currentPoints[2].X - currentPoints[0].X) / (currentPoints[1].X - currentPoints[0].X) ==
(currentPoints[2].Y - currentPoints[0].Y) / (currentPoints[1].Y - currentPoints[0].Y))
{
minimumPoints.Remove(minimumPoints[i + 1]);
}
}
catch (DivideByZeroException)
{
// Ignore
}
}
return minimumPoints;
}
我用了Oliver Charlesworth's answer to Prashant C's question.
第二次编辑 - 更优化的解决方案
我没有使用我自己的 meh 算法来减少点数，而是使用了 Ramer–Douglas–Peucker 算法并将 ε（公差）设置为 0。这是我使用的实现：
private static class DouglasPeuckerReduction
{
public static Point[] ReducePoints(Point[] existingPolygon)
{
if (existingPolygon == null || existingPolygon.Length < 3)
return existingPolygon;
int firstPoint = 0;
int lastPoint = existingPolygon.Length - 1;
List<int> pointIndexsToKeep = new List<int>();
//Add the first and last index to the keepers
pointIndexsToKeep.Add(firstPoint);
pointIndexsToKeep.Add(lastPoint);
//The first and the last point cannot be the same
while (existingPolygon[firstPoint].Equals(existingPolygon[lastPoint]))
{
lastPoint--;
}
ReducePoints(existingPolygon, firstPoint, lastPoint,
0, ref pointIndexsToKeep);
pointIndexsToKeep.Sort();
return pointIndexsToKeep.Select(index => existingPolygon[index]).ToArray();
}
/// <summary>
/// Douglases the peucker reduction.
/// </summary>
/// <param name="points">The points.</param>
/// <param name="firstPoint">The first point.</param>
/// <param name="lastPoint">The last point.</param>
/// <param name="tolerance">The tolerance.</param>
/// <param name="pointIndexesToKeep">The point index to keep.</param>
private static void ReducePoints(IReadOnlyList<Point> points, int firstPoint, int lastPoint, double tolerance,
ref List<int> pointIndexesToKeep)
{
double maxDistance = 0;
int indexFarthest = 0;
for (int index = firstPoint; index < lastPoint; index++)
{
double distance = PerpendicularDistance
(points[firstPoint], points[lastPoint], points[index]);
if (distance > maxDistance)
{
maxDistance = distance;
indexFarthest = index;
}
}
if (maxDistance > tolerance && indexFarthest != 0)
{
//Add the largest point that exceeds the tolerance
pointIndexesToKeep.Add(indexFarthest);
ReducePoints(points, firstPoint,
indexFarthest, tolerance, ref pointIndexesToKeep);
ReducePoints(points, indexFarthest,
lastPoint, tolerance, ref pointIndexesToKeep);
}
}
/// <summary>
/// The distance of a point from a line made from point1 and point2.
/// </summary>
/// <param name="pt1">The PT1.</param>
/// <param name="pt2">The PT2.</param>
/// <param name="p">The p.</param>
/// <returns></returns>
private static double PerpendicularDistance
(Point Point1, Point Point2, Point Point)
{
//Area = |(1/2)(x1y2 + x2y3 + x3y1 - x2y1 - x3y2 - x1y3)| *Area of triangle
//Base = v((x1-x2)²+(x1-x2)²) *Base of Triangle*
//Area = .5*Base*H *Solve for height
//Height = Area/.5/Base
double area = Math.Abs(.5 * (Point1.X * Point2.Y + Point2.X *
Point.Y + Point.X * Point1.Y - Point2.X * Point1.Y - Point.X *
Point2.Y - Point1.X * Point.Y));
double bottom = Math.Sqrt(Math.Pow(Point1.X - Point2.X, 2) +
Math.Pow(Point1.Y - Point2.Y, 2));
double height = area / bottom * 2;
return height;
}
}
我认为@ShashwatKumar 的回答误解了你的问题？如果不是，那就是我误会了！
我读你的 post 的方式，你正在寻找你的图形的多边形轮廓。这称为跟踪二值图像contour/outline，其第一步， 正如@EugeneKomisarenko 在评论中所说，是 "edge detection" （但随后 是进一步的步骤）。 搜索这些短语的变体会影响许多算法，例如：
图片来自this link.
而且你不想去寻找真正最小的兔子洞： “Given a set of 2D vertices, how to create a minimum-area polygon which contains all the given vertices?” 因为这是众所周知的棘手问题（从技术上讲，NP 难）。