Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 24.08.2009, 01:53
Новичок

Отправить личное сообщение для Nicholas Посмотреть профиль Найти все сообщения от Nicholas
 
Регистрация: 24.08.2009
Сообщений: 5

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

Имеем:
голова змеи - и бесконечный хвост
сегменты змеи - точечные
пересечение - наложение двух точек
пересечься может любой сегмент с любым

Задача:
найти пересечение

может ли быть более эффективный поиск чем простой перебор?


С уважением,
Николай
  #2  
Старый 24.08.2009, 02:39
гость

 
Сообщений: n/a

Выражайтесь пояснее.

Что такое ваша змейка? Как вы её храните? И почему она бесконечная?
  #3  
Старый 25.08.2009, 01:55
Новичок

Отправить личное сообщение для Nicholas Посмотреть профиль Найти все сообщения от Nicholas
 
Регистрация: 24.08.2009
Сообщений: 5

Змейка - это массив координат.
Бесконечная змейка, потому что массив бесконечный.

Нужно найти первое самопересечение змейки. Ответом являются два номера сегментов, змеи, которые лежат на одних координатах.
  #4  
Старый 25.08.2009, 01:56
Новичок

Отправить личное сообщение для Nicholas Посмотреть профиль Найти все сообщения от Nicholas
 
Регистрация: 24.08.2009
Сообщений: 5

под бесконечным массивом я подразумеваю. массив с элементами [0], [1], ... [n], [n+1]... n любое сколь угодно большое.
  #5  
Старый 27.08.2009, 16:21
Новичок

Отправить личное сообщение для Nicholas Посмотреть профиль Найти все сообщения от Nicholas
 
Регистрация: 24.08.2009
Сообщений: 5

Спасибо за участие в дискуссии, похоже форум умер. Но тем не менее мне решение в голову таки пришло.

1. из непрерывности червая получаем: на каждом следующем шаге проверки пересечения звена Х с другими можно пропускать столько звеньев подряд, длина каковых меньше расстояния от Х до текущего проверяемого.

2. для сведения числа проверок к конечному: для бесконечного червя проверку нужно вести в порядке возрастания номеров звеньев и проверять их на пересечение с более ранними звеньями (например 7 звено проверяется с набором 6,5,4,3,2,1).


Удачи всем
  #6  
Старый 28.08.2009, 07:46
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Рассуждения о бесконечном числе звеньев и конечном числе проверок занятные...
  #7  
Старый 28.08.2009, 11:43
Новичок

Отправить личное сообщение для Nicholas Посмотреть профиль Найти все сообщения от Nicholas
 
Регистрация: 24.08.2009
Сообщений: 5

А что занятного. Если есть конечное пересечение, то время его поиска конечное. Доказательство же отсутствия пересечений на бесконечном колиечестве сегментов, очевидно, бесконечно.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм по определению пересечения линий Ground Вычислительная геометрия 4 05.04.2009 17:42
Вычисление пересечения vilza Реализация, исходники, языки 7 30.01.2009 16:58
Определить точки пересечения эллипсов like-nix Математические алгоритмы 3 13.10.2008 18:15
площадь пересечения многоугольников Artemon Вычислительная геометрия 1 20.03.2008 13:45
проверка пересечения dex Вычислительная геометрия 1 27.02.2007 07:52