IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Геометрическая задача, Пересечение треугольника и окружности
сообщение
Сообщение #1


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


Сама задача:
На плоскости заданы множество точек и окружность радиусом R с центром в начале координат.Построить множество всех треугольников с вершинами в заданных точках, имеющих непустое пересечение с окружностью.

Идеи есть, но они мне абсолютно не нравятся:
1) брать каждую точку из круга и смотреть, не принадлежит ли она треугольнику. если хоть одна принадлежит - рисовать. и так для каждого треугольника...
2) разбить на случаи:
2.0 если все три внутри - этот треугольник нас сразу перестает интересовать. иначе:
2.1. если хотя бы одна вершина лежит внутри - пересечение есть.
2.2 центр окружности лежит внутри треугольника - рисуем.
2.3 хотя бы одна сторона пересекает окружность - рисуем.
для отлавливания 2.3 надо составлять ур-ния сторон.... из-за нецелочисленности возникают дополнительные заморочки.

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


Если я правильно понял задание и ничего не путаю, то наверно можно так:

Рассматриваем по очереди всевозможные комбинации из трех точек.
Для каждой из трех точек с координатами (x1, y1) проверяем справедливо ли неравенство
sqrt(x1^2+y1^2) <= R. Если в данной комбинации из 3-х точек есть такие точки(или одна точка) для
которых неравенство справедливо и в то же время есть такая точка(точки) для которой оно несправедливо
(что означает что какая-то одна точка лежит внутри окружности, а другая вне ее), то рисуем треугольник.

Сообщение отредактировано: LPBoy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(LPBoy @ 4.05.2006 0:05) *

Если я правильно понял задание и ничего не путаю,

Кое что путаешь. Точнее - упускаешь.
Прикрепленное изображение
- тут все вершины тр-ка снаружи, а пересечение есть.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4





Группа: Пользователи
Сообщений: 5
Пол: Мужской

Репутация: -  0  +


А если так:

для каждой комбинации из 3-х точек перебираем все комбинации из 2-х точек (x1,y1), (x2, y2) smile.gif
и проверяем на пересечение с окружностью, по формулам:

dx = x2 - x1
dy = y2 - y1
dr = sqrt(dx^2+dy^2)

D=x1*y2-x2*y1

Дискриминант = R^2*dr^2-D^2,
если <= 0, то прямая не пересекает или касательная
если > 0 - пересекает

точки пересечения:
x=(D*dy±sign(dy)*dx*sqrt(R^2*dr^2 - D^2))/(dr^2)

y=(-D*dx±|dy|*sqrt(R^2*dr^2-D^2))/(dr^2)

где sign(x) = -1 если x<0; 1 если x>0; 0 если x = 0;

и если хотя бы одна из этих 2-х точек лежит на отрезке (x1,y1), (x2, y2) рисуем треугольник. wacko.gif

Сообщение отредактировано: LPBoy -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(LPBoy @ 4.05.2006 1:31) *

А если так:
...

В целом верно, хотя формулы я не проверял. Попробую словесно уточнить и кое-где подправить общий алгоритм.

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

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

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

4. Некоторые треугольники могут быть построены дважды. Нужно ли это отслеживать - решай сама. Можно исключать треугольники по мере их построения.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


то, что с окружностью - точно.
а вот как рассматривать треугольник - не совсем понимаю: как три отрезка или как кусочек плоскости. в принципе, влияет это только на 1 вариант (когда окружность внутри треугольника), так что, думаю, не очень важно.

всем спасибо! буду пробовать...


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


LPBoy, а откуда берутся формулы?
все классно работает, всем спасибо.

Сообщение отредактировано: мисс_граффити -


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 18:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name