如何获得“更薄”图表为我的坐标系？ [英] How can I get "thinner" graph for my coordinate system?

问题描述

跟进

：

注意： / p>

• 我将需要删除坐标




• 需要添加坐标




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

我唯一可以想到的是使用最短路径算法，例如

  using System; 
使用System.Collections.Generic; 
使用System.Diagnostics; 
使用System.Drawing; 
使用System.Linq; 
使用System.Threading.Tasks; 
使用System.Windows.Forms; 
 
命名空间WindowsFormsApplication1 
 {
 class ExampleProgram：Form 
 {
 const int GridWidth = 24; 
 const int GridHeight = 15; 
 
列表<点> m_points = new List< Point>（）; 
列表<点> m_trail = new List< Point>（）; 
 
 [STAThread] 
 static void Main（）
 {
 Application.EnableVisualStyles（）; 
 Application.SetCompatibleTextRenderingDefault（false）; 
 Application.Run（new ExampleProgram（））; 
} 
 
 ExampleProgram（）
 {
 //简单的小工具添加一堆点
 AddPoints（
 0， 1，3，1，4，1，5，2，4，2，5，2，6，3，4，3，5，4，5，4，6，5，5，6，5， $ b 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） ; 
 
 //非常基本的形式逻辑
 ClientSize = new System.Drawing.Size（GridWidth * 20，GridHeight * 20）; 
 DoubleBuffered = true; 
 Paint + = ExampleProgram_Paint; 
 
 //向表单添加一个新点（注释掉）
 // MouseUp + = ExampleProgram_MouseUp_AddPoint; 
 
 //绘制我们找到的路径
 MouseUp + = ExampleProgram_MouseUp_AddTrail; 
 
 //从
 // TODO中选择一个起始点，开始查找路径：作为一个excersize，为了让读者决定如何从程序中选择
 //起始点
 m_trail.Add（new Point（0，4））; 
 
} 
 
 IEnumerable< Point>边界（点pt）
 {
 //返回所有点与边界边界
 
 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）
 {
产量返回新点（pt.X + 1，pt.Y-1）; 
} 
 yield返回新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）
 {
 //帮助添加一堆点（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）
 {
 //计算轨迹
 while（true）
 {
 //找到下一个点的最佳点
 int bestCount = 0; 
 Point best = new Point（）; 
 
 //在当前终点，测试它周围的所有点
 foreach（var pt in Border（m_trail [m_trail.Count  -  1]））
 {
 //对于每一点，看看这个点接近多少点
 int count = 0; 
 if（m_points.Contains（pt）&！m_trail.Contains（pt））
 {
 foreach（Border（pt）中的var test）
 {
 if（m_points.Contains（test））
 {
 if（m_trail.Contains（test））
 {
 //这是原始云中的一点，和当前
 //跟踪，所以给它一个负重
 count--; 
} 
 else 
 {
 //我们还没有访问过这一点，所以给它一个正的权重
 count ++; 
} 
} 
} 
} 
 
如果（count> bestCount）
 {
 //这一点看起来更好比我们发现的任何东西，所以
 //这是迄今为止最好的一个
 bestCount = count; 
 best = pt; 
} 
} 
 
 if（bestCount< = 0）
 {
 //我们没有找到任何东西，或者我们找到了是坏的，所以
 //突破了循环，我们完成
 break; 
} 
 
 m_trail.Add（best）; 
} 
 
 Invalidate（）; 
} 
 
 void ExampleProgram_MouseUp_AddPoint（object sender，MouseEventArgs e）
 {
 //只需添加点，并将其转储出来
 int x =（ int）Math.Round（（（（double）eX） -  10.0）/ 20.0,0）; 
 int y =（int）Math.Round（（（（double）e.Y） -  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）
 {
 //简单绘图，只需绘制一个网格，点
 e。 Graphics.Clear（Color.White）; （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）; 
} 
} 
} 
} 
  

Following up with this, I have a bunch of coordinates and I draw them on a bitmap image as a coordinate system. Now, I would like to get rid of all the noise, and filter coordinates to give a "clearer" or "cleaner" path and "less" or "better" data to work on. To explain more, I will need to expose my awesome painting skills as follows:

Current:

Desired:

Notice:

• I will need to delete coordinates

• I might need to add coordinates

• I might need to ignore shortest neighbor in some cases

The only thing I can think of, is to use a shortest path algorithm such as A* and Dijkstra. And populate data in some sort of data structure to contain neighbors and costs for every node and then to execute the algorithm. I don't want to start something that might be wrong or waste. I would love to see a pseudo code if possible on how could I solve such a problem?

P.S I am currently on Wpf C# but I am open to use C# or C++ for any task. Thanks

解决方案

What you're after is a path finding application. There are several ways to approach this, but one of the simpler ways is to:

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

Here's some C# code that does just that, it generates a simple list based on your cloud:

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<Point> m_points = new List<Point>();
        List<Point> m_trail = new List<Point>();

        [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<Point> 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)e.X) - 10.0) / 20.0, 0);
            int y = (int)Math.Round((((double)e.Y) - 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);
            }
        }
    }
}

这篇关于如何获得“更薄”图表为我的坐标系？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！