Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
Задачка. |
Философия, технологии, алгоритмы! |
|
Опции темы |
15.05.2003, 01:29 | #1 |
Каннибалисимус
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40
Не в сети |
Задачка.
Вообщем есть задачка. Есть координаты точек. Через 2 точки проводится прямая. Так вот нужно узнать на сколько частей разабьют прямые плоскости. Я конечно знаю алгоритм небольшой но может кто посоветует что.
|
15.05.2003, 03:17 | #2 |
Memory test: failed
|
Так кто кого разбивает? Как я понял, у тебя есть несколько прямых, заданных парами точек и несколько плоскостей. Нужно найти сколько раз разбивают каждую прямую данные плоскости.
Можно пробежаться по всел парам плоскость/прямая и найти все тоски пересечения, а затем посмотреть, к кому что относится. Делается не сложно, но перебором (если память не изменяет, нужно уравнения прямых и плоскостей перевести в параметрические и там была ормулина на понахождению точки пересечения. Сейчас не помню, могу посмотреть). Можно пойти от противного - если плоскость не пересекпет прямую, то она параллельна (хорошая вещь логика), формулина параллельности есть в учебнике геометрии. Но надо обрабатывать вариант пересечения в одной точке двух и более плоскостей с прямой. Для этого нужно найти прямые пересечения плоскостей и посмотреть, пересекают ли они искомые прямые. Какой извариантов оптимальнее на вскидку не скажу, ИМХО второй, но не факт, пробовать надо. DMakeev добавил [date]1052958019[/date]: PS Описание алгоритма пересечения прямой с плоскостью: http://algolist.manual.ru/maths/geom...ineplain3d.php |
19.05.2003, 17:07 | #3 |
Каннибалисимус
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40
Не в сети |
DMakeev Не то. Есть плоскость на ней прямые. эти прямые лежащие на плостоскости разбивают ее на области. Так вот скоко областей будет
|
19.05.2003, 23:42 | #4 |
Форумец
Сообщений: 334
Регистрация: 14.04.2003
Возраст: 42
Не в сети |
Re: Задачка.
> Есть координаты точек. Через 2 точки проводится прямая.
> Так вот нужно узнать на сколько частей разабьют прямые > плоскости. Я конечно знаю алгоритм небольшой но может > кто посоветует что. Задачка -- уровня областной олимпиады по информатике. Через 2 точки проводится прямая, а потом об этих точка забывают и они не учавствуют в построении линий? Или через все-все точки строится множество прямых? |
20.05.2003, 11:44 | #5 |
Каннибалисимус
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40
Не в сети |
RomanPshenichny Нет все прямые учавствуют в разбиении.
|
21.05.2003, 01:47 | #6 |
Memory test: failed
|
LittelBigFace, значтся так:
1. Вычисляешь точки пересечения. 2. Добавляешь 4 точки так, чтобы прямоугольник по ним содержал все остальные точки и искомые точки не должны лежать на сторонах этого прямоугольник (это нужно чтобы избезать бесконечностей - все области должны быть замкнуты). 3. Дальше будем считать плоскости. Алгоритм сканирующий. Суть в том, чтобы идти по искомым точкам сверху вниз, следить за тем, какие полигоны замыкаются. Считаем количество отрезков, примыкающих к верхней кромке прямоугольника. Получаем несколько полигонов "в разработке". По каждому из них мы знаем два отрезка, идущих от последней точки пересечения (в данном случае пересечения с прямоугольником). Берем точку минимальным y. В этой точке сходятся как минимум два отрезка из тех, что мы помним как граничные к полигонам "в разработке". Значит как минимум один полигон замкнулся (т.е. пересеклись его граничные отрезки), его выкидываем из "в разработке" в "готово". Из этой точки выходит несколько отрезков (те, что помечены как граничные или пройденные не считаем), т.е. еще как минимум один полигон переходит "в разработку". Если в точке полигон не замыкается, назначаем граничным отрезок из необработанных, примыкающих к этой точке, у когорого координата x ближе всего к координате х нижней точки второго граничного отрезка данного полигона. Доходим до нижней линии прямоугольника, имеем список всех полигонов. Брррррр, ну я и загнался. Придумал за 15 минут, могут быть подводные камни. Будут вопросы - пиши. |
29.05.2003, 22:37 | #7 |
Каннибалисимус
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40
Не в сети |
DMakeev Есть проще считаем количество пересечений добавляем 1
Если в точке пересекаются больше 2 прямых то вычитаем 1 и ко всему ентому делу прибавляем количество прямых. |