主页 / 问题 / 1553481
Accepted
Mark Mindrin
Asked:2023-11-28 02:13:48 +0000 UTC2023-11-28 02:13:48 +0000 UTC

我无法基于随机给定点构建多边形 C# Windows 窗体

  • 772

我想根据给定的点构造一个多边形。为此，我执行格雷厄姆算法的第 1 点和第 2 点。接下来，我计划执行步骤 3，看看执行步骤 3 后点数组是否不同，因为如果是这样，那么我可以说最初多边形不是凸的。也就是说，我需要从位于随机坐标的随机数量的顶点构建一个多边形，然后判断构建的多边形是否是凸的。我受到这篇文章的启发：https://habr.com/ru/articles/144921/，但是，多边形尚未构建（我尚未开始第3步）。

我尝试了不同的方法，但最终选择了格雷厄姆的算法。显然，插入排序在其中无法正常工作，因为多边形的边有时会相交。

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows.Forms;

namespace TrueLab4_habrEdition
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }
        Graphics g;
        private void Form1_Paint(object sender, PaintEventArgs e)
        {
            g = CreateGraphics();
            Random random = new Random();
            int z = random.Next(6, 8);
            Point[] points = new Point[z];
            int[,] pointsS = new int[z, 2];
            Point[] newPoints = new Point[z];
            int[] P = new int[z];

            // генерация точек
            for (int i = 0; i < z; i++)
            {
                int x = random.Next(50, 100);
                int y = random.Next(70, 170);
                points[i] = new Point(x, y);
            }

            // заполнение массива индексов точек
            for (int i = 0; i < z; i++)
            {
                P[i] = i;
            }

            // копирование массива points в pointsS
            for (int i = 0; i < z; i++)
            {
                pointsS[i, 0] = points[i].X;
                pointsS[i, 1] = points[i].Y;
            }

            grahamscan(pointsS, P);

            int j = 0;
            for (int i = 0; i < P.Length; i++)
            { 
                int x = pointsS[P[i], 0];
                int y = pointsS[P[i], 1];
                newPoints[j++] = new Point(x, y);
                Console.WriteLine(P[i]);
            }
            show2d(pointsS);
            Pen pen = new Pen(Color.Red, 1);
            g.DrawPolygon(pen, newPoints);
        }
        void grahamscan(int[,] pointsS, int[]P)
        {
            for (int i = 1; i < pointsS.GetLength(0); i++) 
            {
                if (pointsS[P[i], 0] < pointsS[0, 0])
                {
                    (P[i], P[0]) = (P[0], P[i]);
                }
            }
            for (int i = 2; i < pointsS.GetLength(0); i++)
            {
                int j = i;
                int[] a = { pointsS[P[0], 0], pointsS[P[0], 1] };
                int[] b = { pointsS[P[j-1], 0], pointsS[P[j-1], 1] };
                int[] c = { pointsS[P[j], 0], pointsS[P[j], 1] };
                while (j > 1 && rotate(a, b, c) < 0)
                {
                    (P[j], P[j-1]) = (P[j-1], P[j]);
                    j -= 1;
                }
            }
        }
        double rotate(int[] A, int[] B, int[] C)
        {
            return (B[0] - A[0]) * (C[1] - B[1]) - (B[1] - A[1]) * (C[0] - B[0]);
        }

        void show2d(int[,] p)
        {
            for (int i = 0; i < p.GetLength(0); i++)
            {
                for (int j = 0; j < p.GetLength(1); j++)
                {
                    Console.Write(p[i, j] + "\t");
                }
                Console.WriteLine();
            }
        }
    }
}

在此输入图像描述

c#

1 个回答

  1. Best Answer

    为了使格雷厄姆的遍历正确工作，必须对点进行排序。否则，遍历有权画自相交的折线，就是你看到的样子。

    要将一组点转换为多边形，不需要构造凸包：

    1. 我们按字典顺序对点进行排序。
    2. 在极值点之间，我们画一条假想线段，并将所有点分为该线段下方和上方的点。
    3. 对于上面的，我们颠倒顺序并将它们与下面的连接起来。多边形已准备就绪。

    在此输入图像描述

    using System;
using System.Collections;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;

public class RandomPolyForm : Form
{
    static public void Main()
    {
        Application.Run(new RandomPolyForm());
    }
 
    public RandomPolyForm()
    {
        Button b = new Button();
        b.Text = "Click Me!";
        b.Click += new EventHandler(Button_Click);
        Controls.Add(b);
    }
 
    private void Button_Click(object sender, EventArgs e)
    {
        Random random = new Random();
        Graphics g = CreateGraphics();
        g.Clear(Color.White);

        int n = random.Next(3, 40);
        Point[] points = new Point[n];

        for (int i = 0; i < n; ++i)
        {
            points[i] = new Point(
                random.Next(50, ClientRectangle.Width - 50),
                random.Next(50, ClientRectangle.Height - 50)
            );
        }

        Pen pen = new Pen(Color.Gray, 1);
        g.DrawPolygon(pen, points);
        pen.Dispose();

        Array.Sort(points, new PointComparer());

        Point[] upper = points.Where(p => ccw(points[0], points.Last(), p)).ToArray();
        Array.Reverse(upper);
        Point[] lower = points.Where(p => !ccw(points[0], points.Last(), p)).ToArray();
        lower.CopyTo(points, 0);
        upper.CopyTo(points, lower.Length);

        pen = new Pen(Color.Black, 2);
        g.DrawPolygon(pen, points);
        pen.Dispose();

    }

    private class PointComparer : IComparer
    {
        int IComparer.Compare(Object x, Object y)
        {
            Point p1 = (Point) x;
            Point p2 = (Point) y;
            if (p1.X < p2.X) { return -1; }
            if (p1.X > p2.X) { return 1; }
            if (p1.Y < p2.Y) { return -1; }
            if (p1.Y > p2.Y) { return 1; }
            return 0;
        }
    }

    private bool ccw(Point p0, Point p1, Point p2)
    {
        return (p2.Y - p0.Y) * (p1.X - p0.X) - (p1.Y - p0.Y) * (p2.X - p0.X) > 0;
    }
}
    • 1

相关问题