如何为我的坐标系获得“更薄”的图形？

接下来，我有一堆坐标，我将它们作为坐标系统绘制在位图图像上。 现在，我想摆脱所有的噪音，并过滤坐标，以提供“更清晰”或“更清洁”的路径和“更少”或“更好”的数据。 为了解释更多，我需要展示我的精彩 绘画技巧，如下所示：

当前：

期望：

注意：

• 我需要删除坐标

• 我可能需要添加坐标

• 在某些情况下，我可能需要忽略最短邻居

我唯一能想到的是使用最短路径算法，如A *和Dijkstra 。 并在某种数据结构中填充数据以包含每个节点的邻居和成本，然后执行该算法。 我不想开始一些可能错误或浪费的事情。 如果可能的话，我很想看到伪代码如何解决这样的问题 ？

PS我目前正在使用Wpf C＃，但我愿意使用C＃或C ++来完成任何任务。 谢谢

Answer 1

您所追求的是路径查找应用程序。 有几种方法可以解决这个问题，但其中一种更简单的方法是：

Pick a starting point, add to list While True: For each border_pt bordering last point on list: Count number of points bordering border_pt If count > best_count: Mark border_pt as best if border_pt is empty: break Add border_pt to list 

以下是一些C＃代码，它会根据您的云生成一个简单的列表：

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Drawing; using System.Linq; using System.Threading.Tasks; using System.Windows.Forms; namespace WindowsFormsApplication1 { class ExampleProgram : Form { const int GridWidth = 24; const int GridHeight = 15; List m_points = new List(); List m_trail = new List(); [STAThread] static void Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new ExampleProgram()); } ExampleProgram() { // Simple little tool to add a bunch of points AddPoints( 0, 4, 1, 3, 1, 4, 1, 5, 2, 4, 2, 5, 2, 6, 3, 4, 3, 5, 4, 5, 4, 6, 5, 5, 6, 5, 6, 4, 5, 4, 7, 4, 7, 3, 8, 3, 8, 4, 8, 5, 8, 6, 9, 6, 9, 5, 9, 4, 9, 3, 10, 2, 10, 3, 10, 4, 10, 5, 10, 6, 11, 5, 11, 4, 11, 3, 11, 2, 12, 4, 12, 5, 13, 5, 13, 6, 13, 8, 14, 8, 14, 7, 14, 6, 15, 7, 15, 8, 15, 9, 14, 9, 14, 10, 13, 10, 12, 10, 11, 10, 13, 11, 14, 11, 15, 11, 15, 12, 16, 12, 17, 12, 18, 12, 19, 12, 18, 11, 17, 11, 17, 10, 18, 10, 19, 10, 19, 9, 19, 8, 20, 8, 21, 8, 18, 7, 19, 7, 20, 7, 21, 7, 21, 6, 22, 6, 23, 6, 21, 5, 20, 5, 19, 5, 19, 4, 18, 4, 17, 4, 20, 3, 21, 3, 22, 3, 20, 2, 19, 2, 18, 2, 19, 1, 20, 1, 21, 1, 19, 0, 18, 0, 10, 0, 4, 1); // Very basic form logic ClientSize = new System.Drawing.Size(GridWidth * 20, GridHeight * 20); DoubleBuffered = true; Paint += ExampleProgram_Paint; // Add a new point to the form (commented out) // MouseUp += ExampleProgram_MouseUp_AddPoint; // Draw the trail we find MouseUp += ExampleProgram_MouseUp_AddTrail; // Pick a starting point to start finding the trail from // TODO: Left as an excersize for the reader to decide how to pick // the starting point programatically m_trail.Add(new Point(0, 4)); } IEnumerable Border(Point pt) { // Return all points that border a give point if (pt.X > 0) { if (pt.Y > 0) { yield return new Point(pt.X - 1, pt.Y - 1); } yield return new Point(pt.X - 1, pt.Y); if (pt.Y < GridHeight - 1) { yield return new Point(pt.X - 1, pt.Y + 1); } } if (pt.Y > 0) { yield return new Point(pt.X, pt.Y - 1); } if (pt.Y < GridHeight - 1) { yield return new Point(pt.X, pt.Y + 1); } if (pt.X < GridWidth - 1) { if (pt.Y > 0) { yield return new Point(pt.X + 1, pt.Y - 1); } yield return new Point(pt.X + 1, pt.Y); if (pt.Y < GridHeight - 1) { yield return new Point(pt.X + 1, pt.Y + 1); } } } void AddPoints(params int[] points) { // Helper to add a bunch of points to our list of points for (int i = 0; i < points.Length; i += 2) { m_points.Add(new Point(points[i], points[i + 1])); } } void ExampleProgram_MouseUp_AddTrail(object sender, MouseEventArgs e) { // Calculate the trail while (true) { // Find the best point for the next point int bestCount = 0; Point best = new Point(); // At the current end point, test all the points around it foreach (var pt in Border(m_trail[m_trail.Count - 1])) { // And for each point, see how many points this point borders int count = 0; if (m_points.Contains(pt) && !m_trail.Contains(pt)) { foreach (var test in Border(pt)) { if (m_points.Contains(test)) { if (m_trail.Contains(test)) { // This is a point both in the original cloud, and the current // trail, so give it a negative weight count--; } else { // We haven't visited this point, so give it a positive weight count++; } } } } if (count > bestCount) { // This point looks better than anything we've found, so // it's the best one so far bestCount = count; best = pt; } } if (bestCount <= 0) { // We either didn't find anything, or what we did find was bad, so // break out of the loop, we're done break; } m_trail.Add(best); } Invalidate(); } void ExampleProgram_MouseUp_AddPoint(object sender, MouseEventArgs e) { // Just add the point, and dump it out int x = (int)Math.Round((((double)eX) - 10.0) / 20.0, 0); int y = (int)Math.Round((((double)eY) - 10.0) / 20.0, 0); m_points.Add(new Point(x, y)); Debug.WriteLine("m_points.Add(new Point(" + x + ", " + y + "));"); Invalidate(); } void ExampleProgram_Paint(object sender, PaintEventArgs e) { // Simple drawing, just draw a grid, and the points e.Graphics.Clear(Color.White); for (int x = 0; x < GridWidth; x++) { e.Graphics.DrawLine(Pens.Black, x * 20 + 10, 0, x * 20 + 10, ClientSize.Height); } for (int y = 0; y < GridHeight; y++) { e.Graphics.DrawLine(Pens.Black, 0, y * 20 + 10, ClientSize.Width, y * 20 + 10); } foreach (var pt in m_points) { e.Graphics.FillEllipse(Brushes.Black, (pt.X * 20 + 10) - 5, (pt.Y * 20 + 10) - 5, 10, 10); } foreach (var pt in m_trail) { e.Graphics.FillEllipse(Brushes.Red, (pt.X * 20 + 10) - 6, (pt.Y * 20 + 10) - 6, 12, 12); } } } } 

Answer 2

您正在寻找一种称为细化或骨架 化的操作，可能会进行一些后处理以删除小组件。 有不同的算法可以提供不同的属性。 例如郭和霍尔以及张和孙的 。

Answer 3

您可能需要考虑将坐标视为二进制图像，并将一些形态学技术应用于图像。

细化可能会给你带来很好的效果，但是这样的处理对于在各种情况下都能很好地工作来说可能很棘手。