Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пересечение отрезков / 11 сообщений из 11, страница 1 из 1
09.12.2011, 16:31
    #37567872
Каролиночка
Каролиночка
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
Есть числовая прямая.

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

Есть плохие отрезки - тоже с координатами. Их надо пересечь вычитанием с хорошим отрезком. Надо понимать, что из одного хорошего после пересечения может получится два, если плохой отрезок находился внутри хорошего.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2011, 17:30
    #37567991
S.G.
S.G.
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
Каролиночка Надо понимать, что из одного хорошего после пересечения может получится два, если плохой отрезок находился внутри хорошего.значит, надо для начала определиться с тем, как хранить окончательный хороший отрезок. например, список отрезков.

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

все это (1-4) выполняется для плохого, и для каждого хорошего из списка.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2011, 18:31
    #37568112
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
Берём координаты начал и концов плохих отрезков. Началу даём вес 1, концу вес -1. Сортируем по возрастанию координаты. И начинаем движение от самой левой точки, подсчитывая текущий вес. Участки, где вес нулевой - хорошие. Если начало хорошего отрезка левее самой левой плохой точки - участок между ними тоже хороший. Если самая правая плохая точка левее конца хорошего отрезка - участок между ними также хороший.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2011, 19:04
    #37568154
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
КаролиночкаЕсть числовая прямая.

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

Есть плохие отрезки - тоже с координатами. Их надо пересечь вычитанием с хорошим отрезком. Надо понимать, что из одного хорошего после пересечения может получится два, если плохой отрезок находился внутри хорошего.
Что будет если вследствие вычитания мы получит 3 и более хороших отрезков?

Не противоречит ли это пункту первому?

Может лучше работать с множеством хороших отрезков? (так удобнее для хранения в динамических структурах для данного алгоритма)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2011, 21:04
    #37568321
ИринаВ
ИринаВ
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
КаролиночкаЕсть числовая прямая.
Есть хороший отрезок - он может быть только один, у него есть координаты первой и последней точек.
Есть плохие отрезки - тоже с координатами. Их надо пересечь вычитанием с хорошим отрезком. Надо понимать, что из одного хорошего после пересечения может получится два, если плохой отрезок находился внутри хорошего.
Хорошо. Каролиночка, а что нужно сделать? Нарисовать на экране? Пожалуйста, в чем задача?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.12.2011, 01:59
    #37568661
Каролиночка
Каролиночка
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
На самом деле задача стоит примерно таким образом:

- оперируем временными интервалами, каждый из которых задан объектом с полями startDate и endDate

- на входе дается несколько интервалов + имеем список объектов ограничивающих отрезков

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

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

На данный момент я пытаюсь придумать критерий запуска рекурсии и, соответственно, ее окончания.

Как-то так :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.12.2011, 03:44
    #37568691
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
А зачем рекурсия-то нужна?
У вас же последовательная обработка...

Давайте рассмотрим такой вариант: ваш "хороший" интервал (на самом деле, это будет допустимое множество) будет задаваться неким объектом. Например, объектом будет коллекция этих ваших объектов со старт/энд датами. И этот объект будет иметь методы для преобразования собственного состояния - например, даем методу некий соответствующий по типу интервал - а метод изменяет коллекцию, разбивая/соединяя имеющиеся интервалы. А "обвязка" пусть организует стек FIFO для поступающих интервалов...

Или вам надо все сделать чисто структурным программированием?

ЗЫ. Вы бы уж сказали, на чём вообще данное дело реализутся...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.12.2011, 12:38
    #37568803
ИринаВ
ИринаВ
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
+1 . ИМХО рекурсия не нужна, и FIFO тоже. Я б делала так (с учетом 11738645 )
Есть список результ. отрезков, "хороших", Напр. GoodList. Кладем в него исх. отрезок.
Есть список огр. отрезков, напр. BadList .
Для кажд. BadList[i], просматирваем GoodList:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
1) Если BadList[i].startDate<GoodList[k].startDate & BadList[i].endDate<GoodList[k].endDate , то обрезаем слева
   GoodList[k].startDate=BadList[i].endDate
   продолжаем просматривать GoodList
2) Если BadList[i].startDate>GoodList[k].startDate & BadList[i].endDate>GoodList[k].endDate , то обрезаем справа
   GoodList[k].endDate=BadList[i].startDate
   продолжаем просматривать GoodList
3) Если BadList[i].startDate>GoodList[k].startDate & BadList[i].endDate<GoodList[k].endDate , то
   добавляем в  GoodList , новый отрезок, GoodList[new]
      GoodList[new].startDate=BadList[i].endDate
      GoodList[new].endDate=GoodList[k].endDate
   исх. отрезол GoodList[k] обрезаем справа
      GoodList[k].endDate=BadList[i].startDate 
   переходим к след. BadList
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.12.2011, 12:53
    #37568814
ИринаВ
ИринаВ
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
Сорри, еще пункт
Код: sql
1.
2.
3.
4) Если BadList[i].startDate<GoodList[k].startDate & BadList[i].endDate>GoodList[k].endDate , то
   удаляем GoodList[k] из списка
   продолжаем просматривать GoodList
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.12.2011, 13:39
    #37568843
Каролиночка
Каролиночка
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
ИринаВ,

да, точно. У меня был просмотр GoodList по BadList, а у вас наоборот. Получалось, что у меня некоторые отрезки могли "пролететь" проверку, особенно образовавшиеся после деления.


А вообще реализация идет на Java. Я сегодня попробую написать метод, потом тут покажу.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
11.12.2011, 23:47
    #37570109
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пересечение отрезков
Каролиночка,

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

Если множество возможных значений времени небольшое, например, номер минуты внутри суток,
то можно использовать битовую карту.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пересечение отрезков / 11 сообщений из 11, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 575ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1342568]:
 0ms
get settings:
 7ms
get forum list:
 20ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 239ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 61ms
get tp. blocked users:
 2ms
others: 225ms
total:  575ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]