Уроки, алгоритмы, программы, примеры

Вход на сайт

Материалы по разделам

Построения
на плоскости (2D)
Графика
в пространстве (3D)
Вычислительная
геометрия
Физическое
моделирование
Фрактальная
графика

Новые комментарии

dobryj den, popytalas otkryt prikreplionnyj fail ctoby posmotret kak rabotaet, no mne ego ne pokazyvaet vydajet osibku. Pochemu?
Очень интересно! ии сайт крутой жалко что умирает(
У Вас число превысит максимальное число int. Можно использовать в Вашем случае uint, но лучше все переписать на double.
Добавление к программе строки glutReshapeFunc(changeSize); приводит к тому, что треугольник перестаёт совсем отрисовываться.
Выдаёт ошибку glut32.dll не найден! При том, что он лежит в System32! Всё решил) Нужно отправить не в System32, а в System.

Счетчики и рейтинг

Рейтинг@Mail.ru Яндекс.Метрика
Скриншот к примеру
Среда программирования: 
Microsoft Visual Studio Express 2013

Демонстрация триангуляции многоугольника.
Программа производит триангуляцию заранее заданного против часовой стрелки многоугольника. Она использует класс Polygon для хранения и триангуляции многоугольника и Form1 для вывода его на экран.

Программа демонстрирует процесс триангуляции последовательно (по щелчку).

Код программы: 

Polygon:

using System;
using System.Drawing;
 
namespace RobotInLabuteny
{
    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 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;
        }
    }
 
 
}

Form1.cs:

using RobotInLabuteny;
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 int drawCount = 0; //количество нарисованных треугольников в данный момент
        private Color[] colors; //цвета треугольников
 
        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;
 
            //рисуем drawCount треугольников
            for (int i = 0; i < drawCount; 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 = colors[i];
                g.FillPath(trianBrush, p);
            }
        }
 
        private void pictureBox1_Click(object sender, EventArgs e) //по щелчку
        {
            if (colors != null) //если триангуляция прошла успешно
            {
                drawCount++; //увеличиваем количество отображаемых треугольников
                if (drawCount > polygon.getTriangles().Length)
                    drawCount = 0;
                draw();
            }
        }
 
        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[]
            {
                248.65465f, 99.79547f,
                59.30233f, 437.65973f,
                335.534f, 321.62216f,
                83.8835f, 767.274f,
                378.47433f, 619.3895f,
                287.60056f, 1020.07654f,
                634.11926f, 1001.0913f,
                658.086f, 417.54724f,
                249.65326f, 596.4075f,
                613.14844f, 233.69086f,
                287.60056f, 228.69476f,
                622.1359f, 58.827484f,
                59.40804f, 71.653946f,
                30.957005f, 313.62842f
            }; //х и y координаты многоугольник против часовой стрелки
 
            //вершины многоугольника против часовой стрелки
            polygon = new Polygon(vertex);
            if (polygon.getTriangles() != null) //если триангуляция была проведена успешно
            {
                Triangle[] trians = polygon.getTriangles(); 
                colors = new Color[trians.Length];
 
                Random rand = new Random();
                for (int i = 0; i < colors.Length; i++) //заполняем палитру случайными цветами
                    colors[i] = Color.FromArgb(rand.Next(25, 225), rand.Next(25, 225), rand.Next(25, 225));
            }
 
        //разместим многоугольник на весь экран
            //масштабирование
            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();
        }
    }
}

Прикрепленный файлРазмер
Пример триангуляции на C#57.89 кб