Среда программирования:
Visual Studio 2015
Статья по теме:
Подсчет площади многоугольника с помощью триангуляции.
Программа разбивает многоугольник на треугольники и подсчитывает площадь многоугольника как сумму треугольников. Площади самих треугольников вычисляются по формуле Герона.
Код программы:
Polygon:
using System; using System.Drawing; namespace Triangulacya { class Polygon { private PointF[] points; //вершины нашего многоугольника private Triangle[] triangles; //треугольники, на которые разбит наш многоугольник private bool[] taken; //была ли рассмотрена i-ая вершина многоугольника public Polygon(float[] points) //points - х и y координаты { if (points.Length % 2 == 1 || points.Length < 6) throw new Exception(); //ошибка, если не многоугольник this.points = new PointF[points.Length / 2]; //преобразуем координаты в вершины for (int i = 0; i < points.Length; i += 2) this.points[i / 2] = new PointF(points[i], points[i + 1]); triangles = new Triangle[this.points.Length - 2]; taken = new bool[this.points.Length]; triangulate(); //триангуляция } private void triangulate() //триангуляция { int trainPos = 0; // int leftPoints = points.Length; //сколько осталось рассмотреть вершин //текущие вершины рассматриваемого треугольника int ai = findNextNotTaken(0); int bi = findNextNotTaken(ai + 1); int ci = findNextNotTaken(bi + 1); int count = 0; //количество шагов while (leftPoints > 3) //пока не остался один треугольник { if (isLeft(points[ai], points[bi], points[ci]) && canBuildTriangle(ai, bi, ci)) //если можно построить треугольник { triangles[trainPos++] = new Triangle(points[ai], points[bi], points[ci]); //новый треугольник taken[bi] = true; //исключаем вершину b leftPoints--; bi = ci; ci = findNextNotTaken(ci + 1); //берем следующую вершину } else { //берем следующие три вершины ai = findNextNotTaken(ai + 1); bi = findNextNotTaken(ai + 1); ci = findNextNotTaken(bi + 1); } if (count > points.Length * points.Length) { //если по какой-либо причине (например, многоугольник задан по часовой стрелке) триангуляцию провести невозможно, выходим triangles = null; break; } count++; } if (triangles != null) //если триангуляция была проведена успешно triangles[trainPos] = new Triangle(points[ai], points[bi], points[ci]); } private int findNextNotTaken(int startPos) //найти следущую нерассмотренную вершину { startPos %= points.Length; if (!taken[startPos]) return startPos; int i = (startPos + 1) % points.Length; while (i != startPos) { if (!taken[i]) return i; i = (i + 1) % points.Length; } return -1; } private bool isLeft(PointF a, PointF b, PointF c) //левая ли тройка векторов { float abX = b.X - a.X; float abY = b.Y - a.Y; float acX = c.X - a.X; float acY = c.Y - a.Y; return abX * acY - acX * abY < 0; } private bool isPointInside(PointF a, PointF b, PointF c, PointF p) //находится ли точка p внутри треугольника abc { float ab = (a.X - p.X) * (b.Y - a.Y) - (b.X - a.X) * (a.Y - p.Y); float bc = (b.X - p.X) * (c.Y - b.Y) - (c.X - b.X) * (b.Y - p.Y); float ca = (c.X - p.X) * (a.Y - c.Y) - (a.X - c.X) * (c.Y - p.Y); return (ab >= 0 && bc >= 0 && ca >= 0) || (ab <= 0 && bc <= 0 && ca <= 0); } private bool canBuildTriangle(int ai, int bi, int ci) //false - если внутри есть вершина { for (int i = 0; i < points.Length; i++) //рассмотрим все вершины многоугольника if (i != ai && i != bi && i != ci) //кроме троих вершин текущего треугольника if (isPointInside(points[ai], points[bi], points[ci], points[i])) return false; return true; } public PointF[] getPoints() //возвращает вершины { return points; } public Triangle[] getTriangles() //возвращает треугольники { return triangles; } public double getArea() //подсчет площади { if (triangles == null) return 0; //площадь нулевая, если триангуляция не удалась double s = 0; for (int i = 0; i < triangles.Length; i++) //суммируем площади для каждого треугольника s += triangles[i].getArea(); return s; } } public class Triangle //треугольник { private PointF a, b, c; public Triangle(PointF a, PointF b, PointF c) { this.a = a; this.b = b; this.c = c; } public PointF getA() { return a; } public PointF getB() { return b; } public PointF getC() { return c; } public double getArea() //подсчет площади треугольника { //длины трех сторон double a = storona(this.a, this.b); double b = storona(this.b, this.c); double c = storona(this.c, this.a); double p = (a + b + c) / 2; return Math.Sqrt(p * (p - a) * (p - b) * (p - c)); //площадь по трем сторонам } private double storona(PointF a, PointF b) //подсчет длины отрезка ab { float x = a.X - b.X; float y = a.Y - b.Y; return Math.Sqrt(x * x + y * y); } } }
Form1:
using Triangulacya; using System; using System.Drawing; using System.Drawing.Drawing2D; using System.Windows.Forms; namespace WindowsFormsApplication6 { public partial class Form1 : Form { private Pen polygonPen; //для рисования контура многоугольника private SolidBrush trianBrush; //для рисования треугольников private Graphics g; private Bitmap bitmap; private Polygon polygon; //многоугольник private float translateX, translateY, scale; public Form1() { InitializeComponent(); } private void drawPolygon() //рисует многоугольник { g.TranslateTransform(translateX, translateY); //центрируем g.ScaleTransform(scale, scale); //масштабируем //рисуем контур PointF[] points = polygon.getPoints(); g.DrawLines(polygonPen, points); g.DrawLine(polygonPen, points[0], points[points.Length - 1]); GraphicsPath p = new GraphicsPath(); Triangle[] trians = polygon.getTriangles(); if (trians == null) return; Random rand = new Random(); //рисуем треугольники for (int i = 0; i < trians.Length; i++) { Triangle t = trians[i]; p.Reset(); p.AddLine(t.getA(), t.getB()); p.AddLine(t.getB(), t.getC()); p.AddLine(t.getC(), t.getA()); trianBrush.Color = Color.FromArgb(rand.Next(25, 225), rand.Next(25, 225), rand.Next(25, 225)); //случайный цвет g.FillPath(trianBrush, p); } } private void draw() { bitmap = new Bitmap(pictureBox1.Width, pictureBox1.Height); g = Graphics.FromImage(bitmap); g.SmoothingMode = SmoothingMode.AntiAlias; drawPolygon(); pictureBox1.Image = bitmap; } private void Form1_Load(object sender, EventArgs e) { polygonPen = new Pen(Color.Black, 1); trianBrush = new SolidBrush(Color.Red); float[] vertex = new float[] { 370.48544f, 279.65497f, 160.86003f, 106.81781f, 262.63522f, 390.5683f, 61.91401f, 433.53473f, 358.50208f, 530.45905f, 160.7767f, 869.19434f, 412.4272f, 624.3856f, 439.38974f, 942.13745f, 528.2663f, 601.40356f, 672.0666f, 797.2506f, 598.16925f, 425.54095f, 673.22003f, 276.6573f, 427.4064f, 420.54486f, 660.08325f, 124.77597f, 358.50208f, 356.59485f, 507.29544f, 95.798584f }; //х и y координаты многоугольник против часовой стрелки //вершины многоугольника против часовой стрелки polygon = new Polygon(vertex); //разместим многоугольник на весь экран //масштабирование PointF[] points = polygon.getPoints(); float minX = int.MaxValue, minY = int.MaxValue; float maxX = int.MinValue, maxY = int.MinValue; foreach (PointF p in points) { minX = Math.Min(minX, p.X); minY = Math.Min(minY, p.Y); maxX = Math.Max(maxX, p.X); maxY = Math.Max(maxY, p.Y); } float width = maxX - minX; float height = maxY - minY; float scaleX = pictureBox1.Width / width; float scaleY = pictureBox1.Height / height; scale = Math.Min(scaleX, scaleY) * 0.95f; //коэффициент масштабирования //центрирование многоугольника translateX = (pictureBox1.Width - width * scale) / 2 - minX * scale; translateY = (pictureBox1.Height - height * scale) / 2 - minY * scale; draw(); //площадь многоугольника double area = polygon.getArea(); if (area == 0) label.Text = "Многоугольник задан неверно!"; else label.Text = "Площадь = " + area.ToString("0.000"); //(area * scale).ToString("0.000"); } } }
Прикрепленный файл | Размер |
---|---|
polygon_area.zip | 69.78 кб |