ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пересечение отрезков
11 сообщений из 11, страница 1 из 1
Пересечение отрезков
    #37567872
Каролиночка
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Каролиночка
Участник
Есть числовая прямая.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗЫ. Вы бы уж сказали, на чём вообще данное дело реализутся...
...
Рейтинг: 0 / 0
10.12.2011, 03:44
| Ответить | Цитировать | Написать  
Пересечение отрезков
    #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:38
| Ответить | Цитировать | Написать  
Пересечение отрезков
    #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, 12:53
| Ответить | Цитировать | Написать  
Пересечение отрезков
    #37568843
Каролиночка
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Каролиночка
Участник
ИринаВ,

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


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

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

Если множество возможных значений времени небольшое, например, номер минуты внутри суток,
то можно использовать битовую карту.
...
Рейтинг: 0 / 0
11.12.2011, 23:47
| Ответить | Цитировать | Написать  
11 сообщений из 11, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Пересечение отрезков
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=75&tid=1342568]:
 0ms
get settings:
 8ms
get forum list:
 17ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 52ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 49ms
get tp. blocked users:
 2ms
others: 200ms
total:  348ms
созд. / загр.: 348ms
x
x
Закрыть


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