Вообщем есть задачка. Есть координаты точек. Через 2 точки проводится прямая. Так вот нужно узнать на сколько частей разабьют прямые плоскости. Я конечно знаю алгоритм небольшой но может кто посоветует что. [Ответ]

Так кто кого разбивает? Как я понял, у тебя есть несколько прямых, заданных парами точек и несколько плоскостей. Нужно найти сколько раз разбивают каждую прямую данные плоскости.
Можно пробежаться по всел парам плоскость/прямая и найти все тоски пересечения, а затем посмотреть, к кому что относится. Делается не сложно, но перебором (если память не изменяет, нужно уравнения прямых и плоскостей перевести в параметрические и там была ормулина на понахождению точки пересечения. Сейчас не помню, могу посмотреть).
Можно пойти от противного - если плоскость не пересекпет прямую, то она параллельна (хорошая вещь логика), формулина параллельности есть в учебнике геометрии. Но надо обрабатывать вариант пересечения в одной точке двух и более плоскостей с прямой. Для этого нужно найти прямые пересечения плоскостей и посмотреть, пересекают ли они искомые прямые.
Какой извариантов оптимальнее на вскидку не скажу, ИМХО второй, но не факт, пробовать надо.

DMakeev добавил [date]1052958019[/date]:
PS Описание алгоритма пересечения прямой с плоскостью: http://algolist.manual.ru/maths/geom...ineplain3d.php [Ответ]

DMakeev Не то. Есть плоскость на ней прямые. эти прямые лежащие на плостоскости разбивают ее на области. Так вот скоко областей будет [Ответ]

> Есть координаты точек. Через 2 точки проводится прямая.
> Так вот нужно узнать на сколько частей разабьют прямые
> плоскости. Я конечно знаю алгоритм небольшой но может
> кто посоветует что.

Задачка -- уровня областной олимпиады по информатике.
Через 2 точки проводится прямая, а потом об этих точка забывают и они не учавствуют в построении линий?
Или через все-все точки строится множество прямых? [Ответ]

RomanPshenichny Нет все прямые учавствуют в разбиении. [Ответ]

LittelBigFace, значтся так:
1. Вычисляешь точки пересечения.
2. Добавляешь 4 точки так, чтобы прямоугольник по ним содержал все остальные точки и искомые точки не должны лежать на сторонах этого прямоугольник (это нужно чтобы избезать бесконечностей - все области должны быть замкнуты).
3. Дальше будем считать плоскости. Алгоритм сканирующий. Суть в том, чтобы идти по искомым точкам сверху вниз, следить за тем, какие полигоны замыкаются.
Считаем количество отрезков, примыкающих к верхней кромке прямоугольника. Получаем несколько полигонов "в разработке". По каждому из них мы знаем два отрезка, идущих от последней точки пересечения (в данном случае пересечения с прямоугольником). Берем точку минимальным y. В этой точке сходятся как минимум два отрезка из тех, что мы помним как граничные к полигонам "в разработке". Значит как минимум один полигон замкнулся (т.е. пересеклись его граничные отрезки), его выкидываем из "в разработке" в "готово". Из этой точки выходит несколько отрезков (те, что помечены как граничные или пройденные не считаем), т.е. еще как минимум один полигон переходит "в разработку". Если в точке полигон не замыкается, назначаем граничным отрезок из необработанных, примыкающих к этой точке, у когорого координата x ближе всего к координате х нижней точки второго граничного отрезка данного полигона.
Доходим до нижней линии прямоугольника, имеем список всех полигонов.
Брррррр, ну я и загнался. Придумал за 15 минут, могут быть подводные камни. Будут вопросы - пиши. [Ответ]

DMakeev Есть проще считаем количество пересечений добавляем 1
Если в точке пересекаются больше 2 прямых то вычитаем 1 и ко всему ентому делу прибавляем количество прямых. [Ответ]