Форум программистов, компьютерный форум CyberForum.ru

Множество точек определяет ломаную. Имеет ли она самопересечения? - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ указатели и строки? http://www.cyberforum.ru/cpp-beginners/thread22461.html
Люди помогите понять, ни как не дается это страшное слово указатель. Так в общем немного ясно, не понятно вот что: Считается что эти два выражения идентичны, ТАК? char * st1="string1"; char st2="string2"; При этом я свободно могу вытянуть любое значения (изменить и т.д.) из st2, к примеру так st2='3'; А вот как такое же проделать с седьмым символом st1?
C++ Минимальный элемент матрицы в каждой диагонали, параллельной главной используя какой цикл, можно искать минимальный элемент матрицы в каждой диагонали, параллельной главной диагонали матрицы? http://www.cyberforum.ru/cpp-beginners/thread22453.html
C++ Замена малых латинских букв символом "$"
Как написать функцию, которая для заданного в качестве параметра массива типа char заменяет все малые латинские буквы символом «$» и возвращает количество выполненных замен?
Передача многомерного массива переменного размера в функцию C++
Как в с передается в функцию многомерный массив, чья размерность определеяется "по ходу дела". Вариант в фортране: ... call f(m,n,x) .... subroutine f(m,n,x) integer m,n real x(m,n) x(i,j) = ...
C++ Возвращение функцией wchar_t значения. http://www.cyberforum.ru/cpp-beginners/thread22424.html
Такой вопросик. Нижеследующий код - это концепция. в качестве аргумента функции должна быть переменная типа wchar_t, функция должна произвести некоторые манипуляции со значеним агрумента и отдать получившиюся строку тоже в типе wchar_t , "отдать" можно либо через return или вернуть вторым аргументом функции (как правильно?) whar_t myfunc(*str1) { str1=L"string was changed";
C++ Транспортабельность Как сделать программы на Borlandc++ рабочими в независимости от того установлен ли борланд на компе или нет, как собрать все нужные файлы до одного экзешника. подробнее

Показать сообщение отдельно
maximus09
32 / 32 / 3
Регистрация: 29.12.2008
Сообщений: 75
05.02.2009, 18:52     Множество точек определяет ломаную. Имеет ли она самопересечения?
В общем, не хочу за тебя просто так писать программу. Скажу только алгоритм выполнения. Думаю, дальше ты справишься.

Задача 1.
Эта задача сводится к тому, что надо определить, пересекаются ли два заданных отрезка. Обозначим координаты концов первого отрезка за (x1a,y1a) и (x1b,y1b). Координаты концов второго - (x2a,y2a) и (x2b,y2b).

Вводим величины
k1 = (y1b-y1a)/(x1b-x1a),
k2 = (y2b-y2a)/(x2b-x2a).

Далее находим

x = (y2a-y1a+k1*x1a-k2*x2a)/(k1-k2)
y = k1*(x-x1a)+y1a

Далее находим значения
d1a = sqrt((x1a-x)^2+(y1a-y)^2)
d1b = sqrt((x1b-x)^2+(y1b-y)^2)
d1 = sqrt((x1b-x1a)^2+(y1b-y1a)^2)

d2a = sqrt((x2a-x)^2+(y2a-y)^2)
d2b = sqrt((x2b-x)^2+(y2b-y)^2)
d2 = sqrt((x2b-x2a)^2+(y2b-y2a)^2)

Отрезки пересекаются, если имеет место равенства:
d1a+d1b = d1
d2a+d2b = d2

(эти два равенства должны выполняться одновременно).

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

Добавлено через 20 минут 18 секунд
Задача 2.
Первое, что нужно сделать - это найти площадь всего многоугольника целиком. Для этого разбиваешь его на несколько треугольников, проводя все возможные диагонали из одной вершины. Площадь всего многоугольника находится как сумма площадей всех полученных треугольников.

Площадь треугольника, координаты вершин которого есть (x1,y1), (x2,y2) и (x3,y3) можно найти как
St = abs((x1-x3)(y2-y3) - (y1-y3)(x2-x3))/2.

Обозначим за Sm площадь многоугольника.

Далее соединяем точку, положение которой относительно многоугольника нужно найти также со всеми вершинами многоугольника. Получим несколько треугольников. Находим суммарную площадь всех этих треугольников. Обозначим ее буквой S.

Если S>Sm, то точка лежит вне многоугольника.
Если S=Sm, то точка лежит на границе многоугольника.
Если S<Sm, то точка лежит внутри многоугольника.

Жаль, но все сказанное справедливо только для выпуклого многоугольника. Для невыпуклого вопрос пока остается открытым.

Добавлено через 22 часа 59 минут 36 секунд
Жаль, но все сказанное справедливо только для выпуклого многоугольника. Для невыпуклого вопрос пока остается открытым.
В принципе, и для невыпуклого многоугольника тоже подходит. Но надо правильно рассчитать площадь этого невыпуклого многоугольника.
 
Текущее время: 13:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru