» Вопрос по геометрии или спасите бывшего двоечника

Бьюсь вот над одной проблемой... Суть: есть некая ограниченная плоскость; на плоскости находится окружность с центром (X,Y) и радиусом R. Также на плоскости есть несколько ломаных прямых, заданных координатами их отрезков (xi,yi) - ну, упростим: пусть будет одна ломаная. Надо определить, принадлежит ли хотя бы одна точка этой ломаной окружности (X,Y,R)? Проще - как определить, принадлежит ли хоть одна из точек отрезка (x0,y0 - x1,y1) кругу (X,Y.R) ?
Чтобы было понятнее - нужно вот для чего: есть карта города (картинка 800х600), есть некий объект (центр окружности (X,Y). Требуется определить, какие ближайшие маршруты общественного транспорта проходят в радиусе R кварталов от этого объекта.
Пока это делается проходом по всей ломаной с некоторым шагом и вычисление для каждой точки условия. Скрипт на PHP, работает медленно.
Может быть, есть какие-то более общая математическая формула/алгоритм?
Чтобы проверять только граничные точки отрезка, а не идти по всей ломаной?

На вскидку:
Круг задается (1) (x-X)^2 + (y-Y)^2 = R^2
Подставляешь в левую часть координаты концов отрезка если получается не больше R^2 значит, да точки внутри круга есть.
Если нет:
Прямая на плоскости задается уравненимем:
(2) Ax+By=C (зная x0,y0,x1,y1 - можно просто получить A,B,C)

Из (2) можно выразить, либо x, либо y ( A или B может равняться 0 )
и подставить в (1) - получится квадратное уравнение.
Если оно не имеет решений - значит точек в круге нету.
Если имеет решение/я и хотябы одно из них находится на искомом отрезке ( получил x=чему-то-там, если это чего-то там принадлежит [x0,x1], анологично для y) значит значит точки есть, иначе - нету.

Kokoc
Имхо надо решить простое уравнение. Здесь Kain прав.
Уравнение прямой в отрезках выглядит так:

x-X0 y-Y0
------- = --------
X1-X0 Y1-Y0


Вырази отсюда x или y, потом подставь в уравнение круга на плоскости (см пост Kain) и решай уравнение. Если как правильно заметил Kain решений нету (дискриминант меньше 0), то прямая и круг не содержат обших точек.
НО!!!!
Даже учитывая проверку на принадлежность корней промежутку [x0;x1] и тд, отрезок может полностью находиться внутри круга. Общих точек при этом не будет. Поэтому вместо уравнения (1) на мой взгляд правильнее будет решить неравенство
(x-X)^2 + (y-Y)^2 <= R^2.
Технология аналогична. В случае получения непустого множества в качестве решения - отрезок (или его часть) однозначно находится внутри круга.

Если правилно понял задача находиться ли точка Х,У внутри окружности радиусом R и центром Xo,Yo.
Элементарно Ватсон:
Расстояние между центром и точкой:
len=(X-Xo)^2+(Y-Yo)^2
если R>len то точка находиться внутри круга

DeDok
Ты не правильно понял -- человек так и делает сейчас. Но это слишком медленно ибо надо трейсить каждую точку (с определённо точностью, разумеется).

IntenT
Неравенство решать сложнее... А я вначале специально написал, что надо проверить не принадлежит ли хотя бы одна точка кругу.


Добавлено

Цитата:

x-X0 y-Y0
------- = --------
X1-X0 Y1-Y0

Тоже не до конца верно поскольку возможно что X1=X0 или Y1=Y0

Kain
Не сильно сложнее..
А если такой вариант? (copи за неровный круг... сейчас кто-нить скажет, что для этой фигуры неприменим указаный выше алгоритм решения..)

_______
/ \
| ______ |
| |
\_______/

Тогда ни одна точка отрезка не пренадлежит окружности, то сам отрезок принадлежит кругу.

Добавлено

Цитата:

возможно что X1=X0 или Y1=Y0

возможно, но попробуй выразить такую прямую предложеным тобой уравнением..
А
x-X0 y-Y0
------- = --------
X1-X0 Y1-Y0
- это уравнение 1-го курса вышки в универе. Матанализ.

IntenT
Еще раз:

Цитата:

надо проверить не принадлежит ли хотя бы одна точка кругу

Цитата:

Подставляешь в левую часть координаты концов отрезка если получается не больше R^2 значит, да точки внутри круга есть.

IntenT

Цитата:

но попробуй выразить такую прямую предложеным тобой уравнением

Издеваешся?
Ладно вдруг не издеваешся отвечу: Для случая X1!=X0 & Y1!=Y0:
A=1/(X1-X0)*k
B=-1/(Y1-Y0)*k
C=(X0/(X1-X0)-Y0/(Y1-Y0))*k
где k - произвольная, отличная от нуля, константа.


Цитата:

это уравнение 1-го курса вышки в универе

А что за университет если не секрет?

так, скажите, мне, любезные ....
а расстояние между двумя точками вычисяется как - все дружно забыли что ли ?

delta=^(x1-x2)*(y1-y2)

if (delta<radius) = наше дело сделанно

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

Intelligent
Твой ответ очень напоминает анекдот о том как математик, физик и статистик доказывали что все числа простые



Добавлено

Цитата:

а расстояние между двумя точками вычисяется как - все дружно забыли что ли?
delta=^(x1-x2)*(y1-y2)

Что ты вычислишь по такой формуле я даже не берусь сказать,
а расстояние между двумя точками вычисляется немного подругому:
R=sqrt((x1-x2)^2 + (y1-y2)^2)

Kain
ну ты понял
стыд и позор на мои седины, а так же спать надо чаще, и дольше

воть.
ну а имея такую фунь, запросто понимаем в кругу точка или не совсем.

Цитата:

улицы обычно короче чем наш радиус.

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

Цитата:

это уравнение 1-го курса вышки в универе. Матанализ.

Не знаю, что нынче универами называется, но мы геометрию и алгебру проходили в школе. Причём требуются знания 7-го класса, нынче стало быть 8-го.


Kokoc
Задачка решается элементарно.
Есть прямая (отрезок ломаной) и точка, задающая центр окружности.
Чтобы прямая касалась окружности, она должна быть перпендикулярна радиусу. Опускаешь перпендикуляр из точки на прямую и получаешь его длину (как найти высоту в треугольнике надеюсь объяснять не надо ). Если длина перпендикуляра меньше радиуса заданной окружности, то существуют точки прямой, принадлежащие кругу. Если равна, то такая точка ровно одна (точка касания). Если больше, то вся прямая лежит вне круга.

Успехов.

AiK
Нет, это не топик - это просто песня


Цитата:

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

Ага, а если треугольник тупоугольный? В этом случае основание перпендикуляра будет не на отрезке ломанной, а на его продолжение. И, соответственно, точек может не быть!

Цитата:

И, соответственно, точек может не быть!

Тогда надо делать проверку концов отрезка. Если оба за пределами то точек нет. Это в любом случае быстрее будет работать!

НУ БЛИН ВЫ ДАЕТЕ

Цитата:

Ага, а если треугольник тупоугольный?

А кто мешает выбирать отрезки так, чтобы он не был тупоугольным?
Кроме того, при совпадении одной из координат центра круга и одного из концов отрезка, перпендикуляр строить не надо, т.к. треугольник будет прямоугольным.

Только "не грузите меня мелочами, я стратегией занимаюсь" © анекдот - это всё из разряда оптимизации.

Да хватит споров,
кокосу помоему уже все равно,- ни ответа ни привета.
За опечатку - сорри

Цитата:

len=(X-Xo)^2+(Y-Yo)^2

а нужно
len=sqrt((X-Xo)^2+(Y-Yo)^2 )
но думаю это и так всем понятно и вышка тут не причем (7 класс "теорема пифагора" если не ошибаюсь)
Решение это самое простое и ИМХО премлемое по скорости, для той задачи которая решалась. Все траблы с ПХП.
Лучше написать программу на С для мат части и потом ее вызывать передавая данные через параметы.

UncoNNecteD

Цитата:

огда надо делать проверку концов отрезка. Если оба за пределами то точек нет. Это в любом случае быстрее будет работать!

Согласен. Но тогда надо еще вычислять основание перепендикуляра, а работать будет примерно с той же скоростью

AiK
Так, праздник продолжается

Цитата:

А кто мешает выбирать отрезки так, чтобы он не был тупоугольным?

Гм... А отрезки вроде заданы Или для упрощения задачи будем прокладывать новые улицы?

Цитата:

Кроме того, при совпадении одной из координат центра круга и одного из концов отрезка, перпендикуляр строить не надо, т.к. треугольник будет прямоугольным.

Это в том смысле, что все дороги ведут в Рим?


Цитата:

Только "не грузите меня мелочами, я стратегией занимаюсь" © анекдот - это всё из разряда оптимизации.

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

DeDok

Цитата:

а нужно len=sqrt((X-Xo)^2+(Y-Yo)^2 )

А лучше все же считать квадраты расстояния, как у тебя первоначально было написано. Операция извлечения корня выполняется медленнее чем возведение в квадрат!


Цитата:

Решение это самое простое и ИМХО премлемое по скорости, для той задачи которая решалась

Ну да, ну да мне тоже всегда нравился метод натурального перибора. Главное думать не надо Но зачем так делать если все-таки можно просто реализовать намного более эффективный алгоритм.

Не, я внимательно читаю. Но пока плохо въезжаю.
Сейчас у меня работает вот такая функция - определяет минимальное расстояние от точки (px,py) до отрезка:

Код:
function FindNearestPoint($path, $px, $py)
{
$path_size = count($path);
// $path - координаты кривой в виде строки: "200,120,200,150,150,50"
if($path_size<2) return false;
// Последние 2 точки - с одинаковыми координатами,
// т.к. начинаем с
$x = $path[$path_size-2];
$y = $path[$path_size-1];
$path[$path_size++] = $x;
$path[$path_size++] = $y;
$iterations = 10000; // для избежания зацикливания
$index = 0;
$mLen=10000; // минимальная длина.
$mX = 0; $mY = 0;
$xi = $path[0]; $yi = $path[1];
$index = 2; // начинаем со второго элемента
$next_x = $path[2]; $next_y=$path[3];
while(--$iterations >0 && $index < $path_size) {
// $len - длина от точки центра окружности (px,py) до точки на отрезке
$len = sqrt(abs($py - $yi)*abs($py - $yi) + abs($px-$xi)*abs($px-$xi));
if($len < $mLen) {
$mLen = $len;
$mX = $xi; $mY = $yi;
}
if($len < 25) break; // 25 - это "радиус" окружности
// Корректируем отклонения от кривой
if($xi == $next_x && $yi == $next_y) {
$index+=2;
$next_x = $path[$index]; $next_y = $path[$index+1];
}
if($xi < $next_x) $xi+=2;
if($xi > $next_x) $xi-=2;
if($yi > $next_y) $yi-=2;
if($yi < $next_y) $yi+=2;
}
return $mLen;
}

Kain

Цитата:

А лучше все же считать квадраты расстояния, как у тебя первоначально было написано. Операция извлечения корня выполняется медленнее чем возведение в квадрат!

не спорю, но я показал мат. формулу, а не оптимизированный алгоритм

Kokoc

Цитата:

Что тут можно оптимизировать?

Очень многое, читай выше.
НО ИМХО это все не поможет, РНР выполняется в режиме трансяции и для решения таких задач не подходит. Или пиши свой плагин к РНР или (что проще) Перепиши програму на С и вызывай через РНР

Kain

Цитата:

Ну да, ну да мне тоже всегда нравился метод натурального перибора. Главное думать не надо Но зачем так делать если все-таки можно просто реализовать намного более эффективный алгоритм.

Я тоже был любителем посидеть за чашечкой кофе и в спокойной обстановке подумать над интересным и эффективным алгоритмом.
....Пока был студентом.
Но давай будем реалистами : Человеку сделали заказ на разработку ПО в определенный срок, судя по своему опыту времени программисту всегда не хватает. Сочинять новые эффективные алгоритмы -прекрассно, но а в данном случае, лучше предоставить самое простое и эффективное решение, а когда будет нормальная работающая программа, можно вести переговоры о версии №2, более эффективной и за доп. плату.
А решение может быть не обязателно абсолютно эффективно в мат. части. Тем более для такой простой задачи.
Это вам не 8086

Для вящего прокола надо было сделать тему "2+2=?". Гораздо прикольнее было бы запутаться именно в ней. А для определения расстояния от точки до прямой вы забыли ввести ещё нечеткие множества, криволинейные интегралы и полином Лагранжа...

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

Kokoc
1. Как я уже выше написал извлечение корня надо заменить квадратом, т.е. сравнивать не растояния, а квадраты расстояния. Это самое простое что можно оптимизировать.

2. А вообщем так (немножко на другом языке но думаю переведешь):

/* Проверяет принадлежит ли точка отрезка кругу
(X0,Y0,R) - окружность
(X1,Y1) - точка
Возвращает 0 - если точка принадлежит кругу
1 - если да
*/
int IsPointIn(X0,Y0,R,X1,Y1)
{
if (((X1-X0)*(X1-X0)+(Y1-Y0)*(Y1-Y0))>R*R) return 0;
else return 1;
}

/* Проверяет принадлежит ли какие-либо точки отрезка кругу
(X0,Y0,R) - окружность
(X1,Y1,X2,Y2) - отрезок
Возвращает 0 - если есть точки отрезка в круге
1 - если нету
*/

/* Функция возвращает 1, если X принадлежит [X1,X2] и 0 иначе! */
int isPointOnLine(X,X1,X2) {
if (X1<X2) {
if ((X<X1)||(X>X2)) return 0;
return 1;
} else {
if ((X<X2)||(X>X1)) return 0;
else return 1;
}
}

int IsLineIn(X0,Y0,R,X1,Y1,X2,Y2)
{
if (isPointIn(X0,Y0,R,X1,Y1)||(isPointIn(X0,Y0,R,X2,Y2)) return 1;
if (X1!=X2) {
D=(Y2-Y1)/(X2-X1);
E=(Y1-D*X1); /* y=Dx+E */
B=2*( D*(E-Y0) - X0);
C=X0*X0+(E-Y0)*(E-Y0)-R*R;
mode=1;
} else if (Y1!=Y2) {
D=(X2-X1)/(Y2-Y1);
E=X1-D*X1; /* x=Dy+E */
B=2*( D*(E-X0) - Y0);
C=Y0*Y0+(E-X0)*(E-X0)-R*R;
mode=2;
} else return 0;
A=D*D+1; /* Квадратное уравнение: AX*X+BX+C=0 */
DESCR=B*B-4*A*C;
if (DESCR<0) return 0;
DESCR=SQRT(DESCR);
SOL1=(B+DESCR)/(2*A);
SOL2=(B-DESCR)/(2*A);
if (mode==1) {
if (isPointOnLine(SOL1,X1,X2)) return 1;
if (isPointOnLine(SOL2,X1,X2)) return 1;
return 0;
} else {
if (isPointOnLine(SOL1,Y1,Y2)) return 1;
if (isPointOnLine(SOL2,Y1,Y2)) return 1;
return 0;
}
}

Вот ну проход по отрезкам уже писать лень, разберешся
Написано в синтаксисе языка C, но переменные определять мне было лень!
Могут быть и синтаксические ошибки, но идеологически все правильно и будет работать гораздо быстрее метода перебора! За подробностями смотри мой первый пост!

Добавлено
aim00ver

Цитата:

криволинейные интегралы и полином Лагранжа

Если бы это было эффективно - ввели бы


nafania
Если чуть-чуть вспомнить математику (что вообщем-то человек и хотел сделать) все тоже будет летать!

DeDok
Ну нельзя же быть таким жадным Нет я в принципе согласен насчет действительно сложных алгоритмов. Но эта-то задача на 5 минут и чисто теоретически ее должен уметь решать восьмиклассник средне-образовательной школы!!!

Всем спасибо. Чуток оптимизировал, воспользовавшись советом AiK. Сначала вычисляю расстояние до конечных точек отрезка; если не удовлетворяют - вычисляю перпендикуляр до отрезка (если центр окружности можно спрецировать перпендикулярно на отрезок). В любом случае меньше вычислений. Кажется, работает правильно.

nafania
Именно так у меня и сделано: маршруты транспорта заданы в виде ломаных кривых координатами отрезков в виде строки типа "100,200,457,200" они хранятся в SQL

Kain
Но эта-то задача на 5 минут и чисто теоретически ее должен уметь решать восьмиклассник средне-образовательной школы!!!
Правильное замечание. Я тут подумал, что преподавание лучше бы велось на практических примерах (типа моего), нежели абстракных "иск в квадрате плюс игрек в квадрате..." Мораль: математику учить надо! (Ломоносов был прав!)

Dedok
Но давай будем реалистами : Человеку сделали заказ на разработку ПО в определенный срок, судя по своему опыту времени программисту всегда не хватает.

Это целиком моя идея и делаю "для себя". Просто интересно стало реализовать такую идею.

Цитата:

виде строки типа "100,200,457,200"

Ай-яй-яй, как нехорошо Разве сложно завсети четыре целочисленных поля? По ним и искать бытсрее, да и парсить не надо.

AiK
Хе! Если бы автобусы ходили строго по прямой
Ведь это же маршрут - количество перегибов ломаной заранее неизвестно. Вот примеры:
5,340,200,340,200,240,494,240,494,270
500,236,516,236,516,424,500,456,462,494,382,498
714,238,210,238,102,178,145,100,456,100,456,116,474,116,474,238,714,238
Поэтому у меня строка через split() преобразуется в массив целых. Так намного проще.

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

Неужели так сложно один раз разбить эту строку на отрезки и положить это всё в таблицу?

Во-первых, будет удобно искать.
А во-вторых сэкономишь на вычислениях, так как маршрутов, которые хоть на каком-то из участков не дублируются другим очень мало....

Kokoc

Цитата:

Именно так у меня и сделано: маршруты транспорта заданы в виде ломаных кривых координатами отрезков в виде строки типа "100,200,457,200" они хранятся в SQL

То что я предлагаю немного по другому. Ты хранишь строку с разными координатами и одним маршрутом проходящим через все эти координаты. А ты сделай наоборот. В строке относящейся к координате (допустим 200) запиши все маршруты через нее проходящие. Отсортируй этот database и поиск в этом случае займет очень мало.

nafania
Нет, то что я привел - это разные маршруты разных автобусов/троллебусов в виде списка координат изгиба ломаной на карте 800х600. Маршрутов на самом деле немного. Для каждого имеется свой gif-файл 800x600. Гораздо больше объектов, для которых надо найти ближайшие маршруты.
У меня на MySQL сделан телефонный справочник. Для некоторых организаций указана координата их положения на карте города (GIF 800x600). Если координата непустая, то на странице появляется ссылка, по которой выполняется скрипт, просматривающий все маршруты и выбирающий ближайшие по вышеобсосанному алгоритму (правильнее было бы забить координаты остановок, а не отрезков ломаной - но у меня карты такой нет), а затем слоями над картой рисует соответствующие прозрачные gif'ы маршрутов.
Гораздо проще вбить в БД координату объекта (X,Y), а поиск оптимального транспорта пусть берет на себя скрипт.

AiK
Слушай, а нафига тебе тогда вообще база? С таким же успехом ты можешь хранить эти строчки в обычном файле...
Можно. Но раз есть MySQL - чего б не воспользоваться? С ним проще.

Неужели так сложно один раз разбить эту строку на отрезки и положить это всё в таблицу?

Сложно с добавлением и особенно с корректировкой. Сейчас вбил целую строку - и готово; в случае изменения маршрута проще поправить. Но идея интересная. Действительно, много отрезков дублируются, и разбивка съкономила бы кучу вычислений. Подумаю на досуге.

Я не понял , у тебя одна ломаная для всех маршрутов?
И с координатами не все ясно


Цитата:

Именно так у меня и сделано: маршруты транспорта заданы в виде ломаных кривых координатами отрезков в виде строки типа "100,200,457,200" они хранятся в SQL

где X где Y