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

[simples]

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

да, координаты случайны

Этим все сказано (для меня).
Форма полигона - лю-ба-я.

Накидал пробы ради эту задачку с условиями:
100 полигонов
10 точек в каждом
точки внутри квадрата 10*10
проверка "есть пересечение последнего отрезка (посл.точка<->первая точка) с любым другим в этом же полигоне?"

Итого: 60+ из 100

"Вы все еще стирает порошком? Тогда мы идем к Вам!"

[Izotic]

http://ru.wikipedia.org/wiki/%D0%9C%...BD%D0%B8%D0%BA
определение многоугольника - замкнутая ломаная(в общем случае)
поэтому

посл.точка<>первая точка

(если я правильно помню и <> означает неравенство) противоречит этому определению.
В моем же случае, надо поменять координаты так, чтобы многоугольник стал простым(т.е без самопересечений)

[simples]

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

если я правильно помню и <> означает неравенство

Исправил "<>" на "<->".
В моем случае это "отрезок между первой и последней точками".

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

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

Ничего не противоречит. Если принять что НЕ надо дублировать первую точку в последней.

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

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

Соб-но это меня в Вашем вопросе и интересует.
Алгоритм накидайте хотя бы тезисно.

[Izotic]

simples

Алгоритм накидайте хотя бы тезисно.

Мой алгоритм примерно таков:
-мы, начиная с 3-го ребра проходим все ребра многоугольника, сравнивая их с предыдущими ребрами, за исключением последнего предшествующего ребра(т.к их пересечение, кроме как в вершине, в принципе невозможно).
-для проверки пересечения я равняю координату у и из получившегося выражения выражаю х, если этот х принадлежит ребру, то точка пересечения есть, для того чтобы исключить пересечение в вершинах используется строгое неравенство
- если точка пересечения найдена, то координаты второй вершины ребра которое мы проверяем меняются, и цикл проверки пересечения с другими ребрами начинается сначала.
- если же последнее ребро многоугольника имеет пересечение, то, вместе с последней меняем так же первую вершину(которая собственно одна и та же)
и начинаю весь алгоритм проверки сначала

Если принять что НЕ надо дублировать первую точку в последней.

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

[simples]

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

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

Вы путаете набор отрезков из которых состоит мн-ник и набор УНИКАЛЬНЫХ точек из которых строятся отрезки из которых строится мн-ник -)
Последний отрезок мн-ка (который Вас так смущает) - строится из последней и первой точки.
Возьмите листик и ручку, поставьте 3(три) точки. Соедините из отрезками. Получился мн-ник? Отлично. Вам не понадобилась для этого 4я точка? нет? Ну значит Вы меня поняли.

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

- если точка пересечения найдена, то координаты второй вершины ребра которое мы проверяем меняются, и цикл проверки пересечения с другими ребрами начинается сначала.

меняются на что?

[Izotic]

Вы путаете набор отрезков из которых состоит мн-ник и набор УНИКАЛЬНЫХ точек из которых строятся отрезки из которых строится мн-ник -)

да, действительно, спасибо, только сейчас понял

меняются на что?

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

и все таки вот в этом фрагменте кода что то не срабатывает, и пересечения остаются.(

for (int j = 3; j <= (k+1); j++)
            {
               
                
                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; 

                    }

                }

[simples]

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

и все таки вот в этом фрагменте кода что то не срабатывает

                    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])))

Это же проверка на "пересекаются отрезки"?
Советую вырезать этот кусок в отд.функцию и протестировать ее известным Вам набором данных.
О результатах - телеграфируйте.

[Izotic]

Советую вырезать этот кусок в отд.функцию и протестировать ее известным Вам набором данных.

Блин, не люблю так делать если честно(
и разве от этого что то поменяется?
проверил(пока не вынося в отдельную функцию) на известной фигуре с пересечением, пересечение есть, но координаты вершин сдвинуты, весьма рандомно

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

[simples]

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

Блин, не люблю так делать если честно(

А что делать - так учат.

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

и разве от этого что то поменяется?

Да, можно будет проверить (тестами) - КОНКРЕТНО.ЭТОТ.КУСОК.

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

проверил(пока не вынося в отдельную функцию) на известной фигуре с пересечением, пересечение есть

Надо проверить все возможные варианты ("есть пересечение, нет пересечения, есть общая точка у 2х отрезков". Не стесняйтесь, это Ваш интерес "найти проблему").

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

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

Я все же настаиваю на отладке проверки до 100% результата. А то в случае неправ.проверки - Вы просто делаете НЕ нужные телодвижения приводящие хз к чему вообще.

[Izotic]

Я все же настаиваю на отладке проверки до 100% результата.

я понимаю что она у меня не работает, и самое прискорбное что я и не знаю, что в ней отлаживать, я уже 6 алгоритмов определяющих пересечение попробовал, вот этот подсказал препод, и все равно не получается 100% результата(