VV>В базе есть порядка 100000 отрезков. VV>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R.
VV>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
VV>В базе есть порядка 100000 отрезков. VV>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R.
VV>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
VV>Зарание благодарен.
VV>В базе есть порядка 100000 отрезков. VV>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R.
VV>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
VV>Зарание благодарен.
Если концы отрезка лежат внутри окружности — то не пересекает
Если концы отрезка лежат один за окружностью другой внутри — то пересекает 1 раз
Если концы отрезка лежат за окружностью — то либо пересекает 2 раза либо не пересекает
надо считать расстояние от точки (центра окр) до прямой отрезка
если она больше радиуса то не пересекает иначе надо искать точку на прямой
если она вне отрезка то не пересекает иначе пересекает
Здравствуйте, nut888, Вы писали:
N>Здравствуйте, VishenV, Вы писали:
VV>>В базе есть порядка 100000 отрезков. VV>>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R.
VV>>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
VV>>Зарание благодарен.
N>Если концы отрезка лежат внутри окружности — то не пересекает N>Если концы отрезка лежат один за окружностью другой внутри — то пересекает 1 раз N>Если концы отрезка лежат за окружностью — то либо пересекает 2 раза либо не пересекает N>надо считать расстояние от точки (центра окр) до прямой отрезка N>если она больше радиуса то не пересекает иначе надо искать точку на прямой N>если она вне отрезка то не пересекает иначе пересекает
Вы все, конечно, интересно говорите =) Но нужна формула. То, каков должен быть алгоритм, думаю и так ясно )
К сожалению, алгоритм, который Вы предлагаете, слишком тяжел для данной задачи. Вы представьте только как долго будут обрабатываться 100000 отрезков по такому алгоритму! Я сам ищу (неспешно ), но пока не нашел. Думаю, есть какое-нибудь уравнение, наподобии того, что используется для определения точки пересечения прямых заданных двумя точками. Может быть, здесь нужно применить производную или еще что-то, но точно не такой способ как Вы предложили, так как он требует много времени на выполнение. Если я окажусь не прав, буду рад )
Здравствуйте, Saruwatari, Вы писали:
S>Здравствуйте, nut888, Вы писали:
N>>Здравствуйте, VishenV, Вы писали:
VV>>>В базе есть порядка 100000 отрезков. VV>>>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R.
VV>>>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
VV>>>Зарание благодарен.
N>>Если концы отрезка лежат внутри окружности — то не пересекает N>>Если концы отрезка лежат один за окружностью другой внутри — то пересекает 1 раз N>>Если концы отрезка лежат за окружностью — то либо пересекает 2 раза либо не пересекает N>>надо считать расстояние от точки (центра окр) до прямой отрезка N>>если она больше радиуса то не пересекает иначе надо искать точку на прямой N>>если она вне отрезка то не пересекает иначе пересекает
S>Вы все, конечно, интересно говорите =) Но нужна формула. То, каков должен быть алгоритм, думаю и так ясно ) S>К сожалению, алгоритм, который Вы предлагаете, слишком тяжел для данной задачи. Вы представьте только как долго будут обрабатываться 100000 отрезков по такому алгоритму! Я сам ищу (неспешно ), но пока не нашел. Думаю, есть какое-нибудь уравнение, наподобии того, что используется для определения точки пересечения прямых заданных двумя точками. Может быть, здесь нужно применить производную или еще что-то, но точно не такой способ как Вы предложили, так как он требует много времени на выполнение. Если я окажусь не прав, буду рад )
Я думаю что быстрее не сделать
Скорость здесь можно повысить отсеивая простые случаи
В частности первые два пункта моего алгоритма на один отрезок потребуют 4 возведения в квадрат 2 сложения и 2 сравнения
(Вычисление квадрата радиуса я не считаю)
Если хотя бы половина отрезков будет классифицирована то это уже даст выигрыш скорости
Для расчета расстояния до прямой на которой лежит отрезок можно использовать предыдущие результаты вычислений (квадраты длин)
Формулы я не приводил по причине их простоты
Все что надо знать чтобы их написать
1) Расстояние между двумя точками
2) Скалярное произведение двух векторов
Здравствуйте, nut888, Вы писали:
N>Формулы я не приводил по причине их простоты N>Все что надо знать чтобы их написать N>1) Расстояние между двумя точками N>2) Скалярное произведение двух векторов
Мне кажется странной позиция, выбранная Вами. Если они простые, напишите, пожалуйста. В мыслях, они, конечно, простые, но практическая реализация сопряжена с кучей подводных камней, которые, если человек ранее не писал такого, сразу не видны.
И мне кажется, что данное решение либо не верно, либо не полное.
Вычислив расстояние от точки до прямой, заданной двумя точками, определяющими саму прямую и не имеющие отношения к точкам пересечения окружности с прямой, мы сможем выяснить только одно: сколько точек пересечения у нас есть. Сами точки для нас останутся загадкой, нее так ли? Думаю, здесь нужно решать систему уравнений из двух формул: прямой и окружности.
Здравствуйте, Saruwatari, Вы писали:
S>Здравствуйте, nut888, Вы писали:
N>>Формулы я не приводил по причине их простоты N>>Все что надо знать чтобы их написать N>>1) Расстояние между двумя точками N>>2) Скалярное произведение двух векторов
S>Мне кажется странной позиция, выбранная Вами. Если они простые, напишите, пожалуйста. В мыслях, они, конечно, простые, но практическая реализация сопряжена с кучей подводных камней, которые, если человек ранее не писал такого, сразу не видны. S>И мне кажется, что данное решение либо не верно, либо не полное. S>Вычислив расстояние от точки до прямой, заданной двумя точками, определяющими саму прямую и не имеющие отношения к точкам пересечения окружности с прямой, мы сможем выяснить только одно: сколько точек пересечения у нас есть. Сами точки для нас останутся загадкой, нее так ли? Думаю, здесь нужно решать систему уравнений из двух формул: прямой и окружности.
Сначала речь шла только об ответе на вопрос есть точки пересечения или их нет
Если их искать силовым методом как Вы предлагаете то это может сделано так
Solve[{(xc-x)^2+(yc-y)^2==rc^2, x1*(1-t)+x2*t==x, y1*(1-t)+y2*t==y}, {x, y, t}]
Решение внутри отрезка при t [0..1] и все числа естественно действительные
Код написан на языке Mathematika
По поводу правильного подхода к решению таких задач есть книжка
П.Е. Кочин Векторное исчисление и начало тензорного исчисления
Там много примеров решений всяких задач
Она есть в djvu
Поищи на http://lib.homelinux.org/
Здравствуйте, nut888, Вы писали:
N>Сначала речь шла только об ответе на вопрос есть точки пересечения или их нет N>Если их искать силовым методом как Вы предлагаете то это может сделано так
N>Solve[{(xc-x)^2+(yc-y)^2==rc^2, x1*(1-t)+x2*t==x, y1*(1-t)+y2*t==y}, {x, y, t}] N>Решение внутри отрезка при t [0..1] и все числа естественно действительные N>Код написан на языке Mathematika
N>По поводу правильного подхода к решению таких задач есть книжка N>П.Е. Кочин Векторное исчисление и начало тензорного исчисления N>Там много примеров решений всяких задач N>Она есть в djvu N>Поищи на http://lib.homelinux.org/
N>Успехов
Любят же писать на языках ОЧЕНЬ высокого уровня.
У меня, при переходе на указанную Вами страничку, запрашиваются авторизационные данные
Здравствуйте, Saruwatari, Вы писали:
S>Здравствуйте, nut888, Вы писали:
N>>Сначала речь шла только об ответе на вопрос есть точки пересечения или их нет N>>Если их искать силовым методом как Вы предлагаете то это может сделано так
N>>Solve[{(xc-x)^2+(yc-y)^2==rc^2, x1*(1-t)+x2*t==x, y1*(1-t)+y2*t==y}, {x, y, t}] N>>Решение внутри отрезка при t [0..1] и все числа естественно действительные N>>Код написан на языке Mathematika
N>>По поводу правильного подхода к решению таких задач есть книжка N>>П.Е. Кочин Векторное исчисление и начало тензорного исчисления N>>Там много примеров решений всяких задач N>>Она есть в djvu N>>Поищи на http://lib.homelinux.org/
N>>Успехов
S>Любят же писать на языках ОЧЕНЬ высокого уровня.
Скорее не писать а решать
S>У меня, при переходе на указанную Вами страничку, запрашиваются авторизационные данные
Ну так угадай ответ на вопрос — труда это не составляет там подсказка есть
Это специально сделано чтобы отсеять англоязычных пользователей
так как сервер всегда сильно перегружен
Здравствуйте, Xeor, Вы писали:
X>Здравствуйте, VishenV, Вы писали:
VV>>В базе есть порядка 100000 отрезков. VV>>Нужно найти отрезки пересекающие произвольно заданную окружность c центром x,y и радиусом R. VV>>Хочется как-то оптимизировать базу что бы не искать отрезки тупым перебором.
X>Может quad-tree?
У самого уже развивалась мысль поделить пространство на секторы.
Похоже что quad-tree это стандартное решение для таких проблем. Хорошо что не начал изобретать велосипед.
Здравствуйте, nut888, Вы писали:
S>>У меня, при переходе на указанную Вами страничку, запрашиваются авторизационные данные N>Ну так угадай ответ на вопрос — труда это не составляет там подсказка есть N>Это специально сделано чтобы отсеять англоязычных пользователей N>так как сервер всегда сильно перегружен
Смотрел с другого компа: там каракули были и об этом не подумал
Здравствуйте, VishenV, Вы писали:
Может и велосипед, но...
Надеюсь отрезки не очень динамично гуляют (добавляются, удаляются...).
1. Разбить пространство на квадраты со стороной примерно 2 удвоенных средних предполагаемых ... диаметров окружностей (ИМХО).
Организовать двумерный массив, элементами которого будут векторы с номерами всех отрезков, имеющих точки внутри квадрата, вероятно хэш, обращаться, например, по координатам левого верхнего угла. Для векторов заранее посчитать, если не ошибаюсь, общее уравнение (Ax+By+C=0, в смысле A,B и C) прямой, на которой он лежит и длину нормали (L=sqrt(A^2+B^2)) — для вычисления расстояния от центра окр. до прямой.
2. "Средняя" окружность может лежать в макс. 4 квадратах, для больших может быть хуже. Тем не менее, для очередной окружности необходимо вычислить все квадраты (можно сразу избавиться от внутренних). По полученным квадратам найти все уникальные отрезки, через них проходящие и собрать их в массив: c1=x1-x0,d1=y1-y0,c2=x2-x0,d2=y2-y0 (перенос центра координат в центр окружности) ,A,B,C,L. Существует мнение, и не только мое, что лучше им быть вещественными (если координаты отрезка по модулю >2^16 для AI32). Ещё можно (нужно) посчитать xl=x0-r,xr,yu,yd — аналогично и R=r*r.
3. Проверить лежит ли i-ый отрезок левее, правее... окружности
отступление Во что в релизе скомпилируют последние компиляторы от MS и Intel след. код:
if (((x1<xl)&&(x2<xl))||((x1>xr)&&(x2>xr))||((y1<yd)&&(y2<yd))||((y1>yu)&&(y2>yu))) continue;
с полным и неполным вычислением условия (или как этот стон зовётся)
Поэкспериментировать даёт ли это эффект.
4. Оставшиеся (из 3 тоже, но их можно выделить особо) отрезки по отношению к окружности могут быть в следующих 5 положениях:
рис. 1
Первым отделяем случай 1. Требуется найти расстояние от центра окружности до прямой S=abs((Ax0+By0+C)/L), x0 и y0 — не =0, а начальные, соответственно, если S>r, то не пересекает, continue. * Собирать массив, всё же, лучше после 4. или не собирать его вообще, а только индексы векторов и левые и пр. границы окружности посчитать...
5. Находим квадрат расстояния от концов отрезка до центра окружности S1=c1*c1+d1*d1, S2 — аналогично.
Сравниваем их с R, если оба меньше — случай 2, если 1 — 3. Остались случаи 4 и 5.
6. Осталось самое медленное — разделить 4 и 5.
рис. 2
спать хочу... Из рисунка видно, что в случае пересечения отрезка и окружности случай 5 (на рис.2. — 1) между самой прямой и одной из прямых, соединяющих концы отрезка с центром окружности, угол <=90 (прямой в случае касания) , а другой — > 90. В случае 4 (на рис.2. — 2) оба эти угла < 90.
Выразив это условие через произведение скалярных произведений направляющих этих прямых:
самого отрезка (B,-A)
через первый конец (c1,d1)
через второй конец (c2,d2); получим (Bc1-Ad1)(Bc2-Ad2)?0. Если больше — не пересекает, в противном случае пересекает.
Дольше можно попробовать, если знаете ( я — нет), SSE[x]
P.S. Простите за возможные ошибки и недочеты.
P.P.S. Вероятно, есть способ и быстрее.
Не понял как в оффлайне правильно ссылаться на рисунки, вот исправляю...
И 250К — это предел?
VEA>Здравствуйте, VishenV, Вы писали: VEA>Может и велосипед, но... VEA>Надеюсь отрезки не очень динамично гуляют (добавляются, удаляются...). VEA>1. Разбить пространство на квадраты со стороной примерно 2 удвоенных средних предполагаемых ... диаметров окружностей (ИМХО). VEA>Организовать двумерный массив, элементами которого будут векторы с номерами всех отрезков, имеющих точки внутри квадрата, вероятно хэш, обращаться, например, по координатам левого верхнего угла. Для векторов заранее посчитать, если не ошибаюсь, общее уравнение (Ax+By+C=0, в смысле A,B и C) прямой, на которой он лежит и длину нормали (L=sqrt(A^2+B^2)) — для вычисления расстояния от центра окр. до прямой.
VEA>2. "Средняя" окружность может лежать в макс. 4 квадратах, для больших может быть хуже. Тем не менее, для очередной окружности необходимо вычислить все квадраты (можно сразу избавиться от внутренних). По полученным квадратам найти все уникальные отрезки, через них проходящие и собрать их в массив: c1=x1-x0,d1=y1-y0,c2=x2-x0,d2=y2-y0 (перенос центра координат в центр окружности) ,A,B,C,L. Существует мнение, и не только мое, что лучше им быть вещественными (если координаты отрезка по модулю >2^16 для AI32). Ещё можно (нужно) посчитать xl=x0-r,xr,yu,yd — аналогично и R=r*r.
VEA>3. Проверить лежит ли i-ый отрезок левее, правее... окружности VEA>отступление VEA>Во что в релизе скомпилируют последние компиляторы от MS и Intel след. код: VEA>
VEA>с полным и неполным вычислением условия (или как этот стон зовётся)
VEA>Поэкспериментировать даёт ли это эффект.
VEA>4. Оставшиеся (из 3 тоже, но их можно выделить особо) отрезки по отношению к окружности могут быть в следующих 5 положениях: VEA> VEA>рис. 1 VEA>Первым отделяем случай 1. Требуется найти расстояние от центра окружности до прямой S=abs((Ax0+By0+C)/L), x0 и y0 — не =0, а начальные, соответственно, если S>r, то не пересекает, continue. VEA>* Собирать массив, всё же, лучше после 4. или не собирать его вообще, а только индексы векторов и левые и пр. границы окружности посчитать...
VEA>5. Находим квадрат расстояния от концов отрезка до центра окружности S1=c1*c1+d1*d1, S2 — аналогично. VEA>Сравниваем их с R, если оба меньше — случай 2, если 1 — 3. Остались случаи 4 и 5.
VEA>6. Осталось самое медленное — разделить 4 и 5. VEA> VEA>рис. 2 VEA>спать хочу... Из рисунка видно, что в случае пересечения отрезка и окружности случай 5 (на рис.2. — 1) между самой прямой и одной из прямых, соединяющих концы отрезка с центром окружности, угол <=90 (прямой в случае касания) , а другой — > 90. В случае 4 (на рис.2. — 2) оба эти угла < 90. VEA>Выразив это условие через произведение скалярных произведений направляющих этих прямых: VEA>самого отрезка (B,-A) VEA>через первый конец (c1,d1) VEA>через второй конец (c2,d2); получим (Bc1-Ad1)(Bc2-Ad2)?0. Если больше — не пересекает, в противном случае пересекает.
VEA>Дольше можно попробовать, если знаете ( я — нет), SSE[x] VEA>P.S. Простите за возможные ошибки и недочеты. VEA>P.P.S. Вероятно, есть способ и быстрее.
Здравствуйте, Saruwatari, Вы писали:
S>Вы все, конечно, интересно говорите =) Но нужна формула. То, каков должен быть алгоритм, думаю и так ясно ) S>К сожалению, алгоритм, который Вы предлагаете, слишком тяжел для данной задачи. Вы представьте только как долго будут обрабатываться 100000 отрезков по такому алгоритму! Я сам ищу (неспешно ), но пока не нашел. Думаю, есть какое-нибудь уравнение, наподобии того, что используется для определения точки пересечения прямых заданных двумя точками. Может быть, здесь нужно применить производную или еще что-то, но точно не такой способ как Вы предложили, так как он требует много времени на выполнение. Если я окажусь не прав, буду рад )
Как давно Вы пользовались Рексоной?
Для прямых Вы имеете ввиду:
y — аналогично.
где 1 и 2 — точки первой прямой ...
могу предложить следующую:
только вряд ли так будет быстрее, так как от корня не избавиться
если получиться сообщите.
Здравствуйте, Saruwatari, Вы писали:
S>Вот что получилось Класс Line.
Я говорил про пересечение отрезка с окружностью, там от квадратного корня в формуле не знаю как избавиться...
Кажется это С#, которого я совсем не знаю.
IsNaN используется при почти параллельных прямых?
И у меня 4 суммы 2 произведения и 1 частное на координату.
Здравствуйте, VEAPUK, Вы писали:
VEA>Я говорил про пересечение отрезка с окружностью, там от квадратного корня в формуле не знаю как избавиться...
Да, здесь не окружность. С окружностью я пока не разобрался. Разбираюсь потихоньку, т.к. это в свободное вермя от работы происходит...
VEA>IsNaN используется при почти параллельных прямых?
Да, в случае, если точек пересечения не обнаружено, т.е. линии совсем или "почти" параллельны.
), но пока не нашел. Думаю, есть какое-нибудь уравнение, наподобии того, что используется для определения точки пересечения прямых заданных двумя точками. Может быть, здесь нужно применить производную или еще что-то, но точно не такой способ как Вы предложили, так как он требует много времени на выполнение. Если я окажусь не прав, буду рад )
