Старый 15.05.2003, 01:29   #1   
Каннибалисимус
 
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40

LittelBigFace вне форума Не в сети
Задачка.

Вообщем есть задачка. Есть координаты точек. Через 2 точки проводится прямая. Так вот нужно узнать на сколько частей разабьют прямые плоскости. Я конечно знаю алгоритм небольшой но может кто посоветует что.
  Ответить с цитированием
Старый 15.05.2003, 03:17   #2   
Memory test: failed
 
Аватар для DMakeev
 
Сообщений: 699
Регистрация: 21.03.2003
Возраст: 41
Записей в дневнике: 7

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

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

LittelBigFace вне форума Не в сети
DMakeev Не то. Есть плоскость на ней прямые. эти прямые лежащие на плостоскости разбивают ее на области. Так вот скоко областей будет
  Ответить с цитированием
Старый 19.05.2003, 23:42   #4   
Форумец
 
Аватар для RomanPshenichny
 
Сообщений: 334
Регистрация: 14.04.2003
Возраст: 42

RomanPshenichny вне форума Не в сети
Re: Задачка.

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

Задачка -- уровня областной олимпиады по информатике.
Через 2 точки проводится прямая, а потом об этих точка забывают и они не учавствуют в построении линий?
Или через все-все точки строится множество прямых?
  Ответить с цитированием
Старый 20.05.2003, 11:44   #5   
Каннибалисимус
 
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40

LittelBigFace вне форума Не в сети
RomanPshenichny Нет все прямые учавствуют в разбиении.
  Ответить с цитированием
Старый 21.05.2003, 01:47   #6   
Memory test: failed
 
Аватар для DMakeev
 
Сообщений: 699
Регистрация: 21.03.2003
Возраст: 41
Записей в дневнике: 7

DMakeev вне форума Не в сети
LittelBigFace, значтся так:
1. Вычисляешь точки пересечения.
2. Добавляешь 4 точки так, чтобы прямоугольник по ним содержал все остальные точки и искомые точки не должны лежать на сторонах этого прямоугольник (это нужно чтобы избезать бесконечностей - все области должны быть замкнуты).
3. Дальше будем считать плоскости. Алгоритм сканирующий. Суть в том, чтобы идти по искомым точкам сверху вниз, следить за тем, какие полигоны замыкаются.
Считаем количество отрезков, примыкающих к верхней кромке прямоугольника. Получаем несколько полигонов "в разработке". По каждому из них мы знаем два отрезка, идущих от последней точки пересечения (в данном случае пересечения с прямоугольником). Берем точку минимальным y. В этой точке сходятся как минимум два отрезка из тех, что мы помним как граничные к полигонам "в разработке". Значит как минимум один полигон замкнулся (т.е. пересеклись его граничные отрезки), его выкидываем из "в разработке" в "готово". Из этой точки выходит несколько отрезков (те, что помечены как граничные или пройденные не считаем), т.е. еще как минимум один полигон переходит "в разработку". Если в точке полигон не замыкается, назначаем граничным отрезок из необработанных, примыкающих к этой точке, у когорого координата x ближе всего к координате х нижней точки второго граничного отрезка данного полигона.
Доходим до нижней линии прямоугольника, имеем список всех полигонов.
Брррррр, ну я и загнался. Придумал за 15 минут, могут быть подводные камни. Будут вопросы - пиши.
  Ответить с цитированием
Старый 29.05.2003, 22:37   #7   
Каннибалисимус
 
Сообщений: 1,264
Регистрация: 22.04.2002
Возраст: 40

LittelBigFace вне форума Не в сети
DMakeev Есть проще считаем количество пересечений добавляем 1
Если в точке пересекаются больше 2 прямых то вычитаем 1 и ко всему ентому делу прибавляем количество прямых.
  Ответить с цитированием
Поиск в теме: 


Опции темы

Быстрый переход:

  Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Support by DrIQ & Netwind