Многоугольник без самопересечений

[Izotic]

Здравствуйте, суть задачи в следующем, надо на C# написать программу которая рисует многоугольник с заданным количеством вершин и случайными координатами так, чтобы отсутствовали самопересечения.

На мой взгляд вполне логично использовать два уравнения прямых заровняв их по У координате, и найти возможную точку пересечения, а после проверить принадлежит ли она обоим ребрам, и если да, то соответственно поменять координату. Составил вот такой алгоритм:

for (int j = 3; j <= (k); j++)
            {
               
                k1 = 0;
                k2 = 0;
                b1 = 0;
                b2 = 0;
                for (int m = 1; m <= (j-2); m++)
                {
                    
                    k1 = (Y[j] - Y[j - 1]) / (X[j] - X[j - 1]);
                    k2 = (Y[m] - Y[m - 1]) / (X[m] - X[m - 1]);
                    b1 = Y[j - 1] - k1 * X[j - 1];
                    b2 = Y[m - 1] - k2 * X[m - 1];
                    x = (b2 -b1) / (k1 - k2);
                    if (((x)>X[j-1])&&((x)<X[j])&&(x>X[m-1])&&(x<X[m]))
                    {
                        X[j] = rnd.Next(0, 10) + rnd.NextDouble();
                        Y[j] = rnd.Next(0, 10) + rnd.NextDouble();
                        m=0;
                        if (j == k)
                        {
                            X[0] = X[j];
                            Y[0] = Y[j];
                            j = 3;
                        }

                    }

                }
            }

Проблема в том, что пересечения как были, так и остаются, помогите пожалуйста, уже 2 недели бьюсь над задачей

[phomm]

Весь проект киньте, поглядим )

[Izotic]

Сообщение от phomm

Весь проект киньте, поглядим )

namespace polygon
{
    public partial class Form1 : Form
    {
        Double[] X = new Double[25];
        Double[] Y= new Double[25];
        Random rnd=new Random();
        int i = 0;
        double Xmin, Ymin, Xmax, Ymax;
        

        public Form1()
        {
            InitializeComponent();
        }

        private void button1_Click(object sender, EventArgs e)
        {
            Int32 k = Convert.ToInt32(textBox6.Text);
            
                 

            if ((textBox1.Text != "") && (textBox2.Text != ""))
            {
                if(i!=k)
                
                    X[i] = Convert.ToInt32(textBox1.Text);
                    Y[i] = Convert.ToInt32(textBox2.Text);
                    
                    i++;
                
            }
            else
            {
                for (i = 0; i <= k; i++)
                {
                    X[i] = rnd.Next(0, 10) + rnd.NextDouble();
                    Y[i] = rnd.Next(0, 10) + rnd.NextDouble();
                }
                   
                    
             }
            
            X[k] = X[0];
            Y[k] = Y[0];


        }

        private void button2_Click(object sender, EventArgs e)
        {
            Int32 k = Convert.ToInt32(textBox6.Text);
            double xmin=X[0], ymin=Y[0], xmax=X[0], ymax=Y[0];
            double x,y;

            double k1, k2, b1, b2;

            for (int j = 3; j <= (k); j++)
            {
               
                k1 = 0;
                k2 = 0;
                b1 = 0;
                b2 = 0;
                for (int m = 1; m <= (j-2); m++)
                {
                    
                    k1 = (Y[j] - Y[j - 1]) / (X[j] - X[j - 1]);
                    k2 = (Y[m] - Y[m - 1]) / (X[m] - X[m - 1]);
                    b1 = Y[j - 1] - k1 * X[j - 1];
                    b2 = Y[m - 1] - k2 * X[m - 1];
                    x = (b2 -b1) / (k1 - k2);
                    if (((x)>X[j-1])&&((x)<X[j])&&(x>X[m-1])&&(x<X[m]))
                    {
                        X[j] = rnd.Next(0, 10) + rnd.NextDouble();
                        Y[j] = rnd.Next(0, 10) + rnd.NextDouble();
                        m=0;
                        if (j == k)
                        {
                            X[0] = X[j];
                            Y[0] = Y[j];
                            j = 3;
                        }

                    }

                }
            }
            for (int i = 1; i <= k; i++)
            {
                if (Math.Abs(X[i]) < xmin)
                {xmin=X[i];
                 }
                if (Y[i]<ymin)
                { ymin = Y[i]; }

            }
            for (int i = 1; i <= k; i++)
            {
                if (X[i] > xmax)
                {
                    xmax = X[i];
                    
                }
                if (Y[i] > ymax)
                { ymax = Y[i]; }

            }
            chart1.Series[0].Points.AddXY(xmin, ymin);
            chart1.Series[0].Points.AddXY(xmax, ymin);
            chart1.Series[0].Points.AddXY(xmax, ymax);
            chart1.Series[0].Points.AddXY(xmin, ymax);
            chart1.Series[0].Points.AddXY(xmin, ymin);
            Xmin = xmin; Xmax = xmax; Ymin = ymin; Ymax = ymax;
            for (int i = 0; i <= k; i++)
            {
                chart1.Series[1].Points.AddXY(X[i], Y[i]);
            }
        }

Так, или прям весь проект файлом?
уж поглядите пожалуйста)

[simples]

Вариант
1. генер-я новой точки
2. если точек 3 и больше - проверить последний отрезок с пред-ми на пересечения
3. если есть пересечение - переген-ть точку

+поставить лимит на кол-во повторных генераций (вариант - последняя точка ну никак не может быть без пересечений).

Имхо - генерировать че попало а потом пытаться исправить, какой то сложный.

[phomm]

Вообще, проект это не код, а всё что есть, ибо форма задизайнена и всё такое (например чарт, я ж не знаю как настроен), потом, у Вас тут текстбокс, надо знать какие значения вводить чтобы увидеть разное поведение проги (например при цифре 5 рисует правильно а при 10 - нет) и Вы должны всё это указать, иначе как понять в чём у Вас проблема ? телепатировать до посинения ? лично у меня нет времени на это.
Я открыл студию вставил ваш код в новый винформс проект, кинул 2 батона текстбокс и чарт, на батоны повешал соотв обработчики. Запускаю, ввожу цифру 1 - нажимаю сперва первую кнопку потом вторую и ошибка выхода индекса на коде chart1.Series[1].Points.AddXY(X[i], Y[i]); то же самое с и со значением 10 и 24, тоже самое для всех цифр при нажатии сразу второй кнопки.
Код разбирать не хочется времени тратить, тем более что он запутанный, как обычно это бывает.
Давайте весь проект и все входные данные и опишите чего надо добиться (понять что решается правильно) - вдруг не только непересечения линий.

[Izotic]

simples
Ну так в принципе тут и заложена эта идея, только проверяются уже готовые комбинации точек и в случае удовлетворения условию меняются

+поставить лимит на кол-во повторных генераций (вариант - последняя точка ну никак не может быть без пересечений).

Так последнее ребро должно пересекаться только в вершине, а это ужже учтено тем что в условии стоит строгое неравенство, разве нет?

phomm
Спасибо что ответили, сейчас попробую выложить проект на народ, потому что здесь не нашел кнопки прикрепить файл.) вот ссылка http://yadi.sk/d/Lxs6r9rCALUtH
Значит там еще есть третья кнопка, реализующая вычисление площади этого самого многоугольника методом монте-карло но к ней алгоритм уже есть (был в предыдущей задаче) вот только без работающего алгоритма пересечений его не сделать...
Входящие условия касательно многоугольника такие:
1. количество вершин многоугольника задается пользователем, не больше 15(как сказал препод слишком долго считать будет)
2. координаты вершин также задаются с клавиатуры, если они не заданы, то генерятся случайные координаты, вещественные, в пределах [0,10]
3. Обязательным условием является то, чтобы самопересечения ребер многоугольника не было
4. Ну и вписать многоугольник в прямоугольник (ну с этой задачей я вроде справился))
заранее спасибо

Собственно все чего не хватает, это алгоритма определяющего пересечение и исправляющее координаты вершин так чтобы многоугольник не пересекался

[simples]

Сообщение от Izotic

Так последнее ребро должно пересекаться только в вершине, а это ужже учтено тем что в условии стоит строгое неравенство, разве нет?

Фигура типа спираль - будет иметь НЕ пересекающийся отрезок соединяющий начало с концом?

Алгоритм проверки пересечения отрезков тут есть (не проверял, как и Ваш не осмысливал особо если честно)
http://stackoverflow.com/questions/5...ts-a-rectangle

Сообщение от Izotic

и исправляющее координаты вершин так чтобы многоугольник не пересекался

От этого я и предлагаю отказаться своим вариантом алгоритма.

[Izotic]

simples
а мне по любому такой алгоритм понадобиться чтобы метод трассировки луча после реализовать, поэтому и не могу от него отказаться

http://stackoverflow.com/questions/5...ts-a-rectangle

алгоритм здесь очень похож на мой, только не совсем понятно что за координаторы они используют и почему проверка только между [0,1]

Фигура типа спираль - будет иметь НЕ пересекающийся отрезок соединяющий начало с концом?

а зачем мне такая фигура? мне нужен именно многоугольник, а не спираль, и естественно, раз мне надо искать его площадь, что он должен замыкаться

[simples]

Сообщение от Izotic

многоугольник с заданным количеством вершин и случайными координатами так

Сообщение от Izotic

а зачем мне такая фигура? мне нужен именно многоугольник, а не спираль

Вопросов/комментариев больше не имею. Т.к. не понимаю Вас.

[Izotic]

simples
может так понятней будет, да, координаты случайны, но по коду видно, что последняя точка равна первой, следовательно, даже если точки расположены спиралью, надо вывернуть точки так, чтобы они превратились в замкнутый многоугольник без пересечений ребер кроме как в местах вершин