не могу построить многоугольник по заданным рандомом точкам С# Windows Forms
Я хочу построить многоугольник по заданным точкам. Для этого я выполняю 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();
}
}
}
}
Ответы (1 шт):
Для правильной работы обхода Грэхема точки должны быть отсортированы. Иначе обход имеет право рисовать самопересекающиеся ломанные, что вы и видите.
Чтобы превратить набор точек в многоугольник, не нужно строить выпуклую оболочку:
- Сортируем точки лексикографически.
- Между крайними точками проводим воображаемый отрезок и делим все точки на те что ниже и те что выше этого отрезка.
- У тех что выше меняем порядок на обратный и соединяем с теми что ниже. Многоугольник готов.
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;
}
}