Геометрия, блин

← →
Merlin (2003-03-20 12:41) [0]

Нужно два алгоритма:
1. определить факт пересечения двух отрезков
2. определить факт пересечения отрезка и окружности
Отрезки заданы координатами концов (x1,y1) - (x2,y2)
Окружность задана координатами центра и радиусом: (x1,y1, radius)
Нужен оптимальный алгоритм, т.к. эти вычисления будут производиться по неск. сотен в секунду. Не надо вычислять координаты пересечения, нужен только факт пересечения: true/false

Для отрезков я сейчас делаю: вычисляю параметры прямой (Ax+By+C=0), вычисляю точку пересечения этих прямых и проверяю принадлежность этой точки обоим отрезкам. Алгоритм получается достаточно громоздкий (много вычисления), наверняка все можно упростить.

← →
myor (2003-03-20 12:51) [1]

> ...наверняка все можно упростить.

сам алгоритм вряд ли, а, вот, реализацию- возможно.
зы
надо покумекать.

← →
Johnmen (2003-03-20 12:53) [2]

1. max(x11,x21)<=min(x12,x22) and max(y11,y21)<=min(y12,y22)

← →
pasha676 (2003-03-20 12:53) [3]

Чую, что по отрезкам, если нужно только тру-фалсе, можно анализировать координаты на больше меньше, как то попарно и делать вывод о пересечении. Но это чисто интуитивно.

Возможно реально что то тем же способом сделать и с кругом. Сравнивать координаты концов отрезка с радиусом и центром.

← →
myor (2003-03-20 12:55) [4]

а если проверить расстояние между прямыми (отрезками) в диепазане (x1..x2;y1..y2) на ноль (т. е. их пересечение)?
выгодского нужно бы полистать.

← →
Думкин (2003-03-20 13:05) [5]

> Merlin © (20.03.03 12:41)

Я знаю ответ. А в чем интерес?

← →
Danilka (2003-03-20 13:09) [6]

пересечение отрезков:

/** * Tests if the line segment from (X1, Y1) to * (X2, Y2) intersects the line segment from (X3, Y3) * to (X4, Y4). * @param X1, Y1 the coordinates of the beginning of the first * specified line segment * @param X2, Y2 the coordinates of the end of the first * specified line segment * @param X3, Y3 the coordinates of the beginning of the second * specified line segment * @param X4, Y4 the coordinates of the end of the second * specified line segment * @return true if the first specified line segment * and the second specified line segment intersect * each other; false otherwise. */ public static boolean linesIntersect(double X1, double Y1, double X2, double Y2, double X3, double Y3, double X4, double Y4) { return ((relativeCCW(X1, Y1, X2, Y2, X3, Y3) * relativeCCW(X1, Y1, X2, Y2, X4, Y4) <= 0) && (relativeCCW(X3, Y3, X4, Y4, X1, Y1) * relativeCCW(X3, Y3, X4, Y4, X2, Y2) <= 0)); }

только это не дельфи, а ява, выдрано из исходников класса: awt.geom.Line2D

← →
Danilka (2003-03-20 13:11) [7]

упс, вот это забыл:

public static int relativeCCW(double X1, double Y1, double X2, double Y2, double PX, double PY) { X2 -= X1; Y2 -= Y1; PX -= X1; PY -= Y1; double ccw = PX * Y2 - PY * X2; if (ccw == 0.0) { // The point is colinear, classify based on which side of // the segment the point falls on. We can calculate a // relative value using the projection of PX,PY onto the // segment - a negative value indicates the point projects // outside of the segment in the direction of the particular // endpoint used as the origin for the projection. ccw = PX * X2 + PY * Y2; if (ccw > 0.0) { // Reverse the projection to be relative to the original X2,Y2 // X2 and Y2 are simply negated. // PX and PY need to have (X2 - X1) or (Y2 - Y1) subtracted // from them (based on the original values) // Since we really want to get a positive answer when the // point is "beyond (X2,Y2)", then we want to calculate // the inverse anyway - thus we leave X2 & Y2 negated. PX -= X2; PY -= Y2; ccw = PX * X2 + PY * Y2; if (ccw < 0.0) { ccw = 0.0; } } } return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0); }

← →
Romkin (2003-03-20 13:12) [8]

Насчет окружности: Довольно просто, определяешь расстояние между концами отрезка и центром окружности, далее если одно меньше, а другое больше радиуса - есть пересечение (корни извлекать не надо, можно взять квадраты расстояний и возвести в квадрат радиус - соотношение сохраняется)
Отрезки: Где-то я видел решение, то ли у Кнута, толи где-то еще...

← →
Nikolay M. (2003-03-20 13:14) [9]

По поводу отрезков:
1) перейти в систему координат, где один из отрезков лежит на оси ОХ, а один из его концов совпадает с началом координат
2) подсчитать уравнение прямой (y=kx+b), на которой лежит второй отрезок исходя из условия (y2-y)/(x2-x) = (y2-y1)/(x2-x1), подсчитать абсциссу точки пересечения прямой с осью ОХ (это будет -b/k). Если эта точка принадлежит первому отрезку (который лежит на ОХ), то есть пересечение.

← →
alxx (2003-03-20 13:14) [10]

Допустим, отрезок описывается прямоугольником,
т.е. отрезок (х1, у1)-(х2,у2) описывается прямоугольником (х1, у1)-(х2,у2).

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

Похоже так. Много условий, ноль делений и умножений.

← →
Nikolay M. (2003-03-20 13:16) [11]

> Romkin © (20.03.03 13:12)
Привет.
Абсолютно не обязательно :)
Оба расстояния могут быть больше, а пересечение может как быть, так и нет

← →
myor (2003-03-20 13:19) [12]

о, по окружности уже есть.

← →
alxx (2003-03-20 13:21) [13]

Похоже, я херню сказал. Надо еще учитывать из какого угла в какой отрезок идет.

← →
myor (2003-03-20 13:24) [14]

перпендикуляр из центра окружности на отрезок меньше радиуса (если отрезок больше диаметра).

← →
Merlin (2003-03-20 13:24) [15]

> Johnmen ©

поясни, не понял.

← →
myor (2003-03-20 13:33) [16]

по отрезкам
a(x11,y11;x12,y12), b(x21,y21;x22,y22):
пусть
x1<x2
y1<y2
тогда:
max(xi1)<=min(xi2)
and max(yi1)<=min(yi2)
т. е., координаты начал обех отрезков (по обеим осям), меньшее координат концов.

← →
Romkin (2003-03-20 13:34) [17]

2Nikolay M. Млин, точно, это достаточное условие... Если выполняется - пересекает.
Дополню: Не пересекает, если перпендикуляр из центра окружности к отрезку пересекает отрезок и меньше радиуса окружности... Вот это найти сложнее, но можно сделать вторым этапом

← →
Romkin (2003-03-20 13:38) [18]

Так.. Надо пояснить... Отрезок пересекает окружность, если
1. расстояния от концов отрезка до центра окружности одно меньше радиуса, другое больше
2. Расстояния от концов отрезка до центра больше радиуса и при этом перпендикуляр из центра окружности пересекает отрезок и его длина меньше радиуса окружности.

Вроде так...

← →
pasha676 (2003-03-20 13:42) [19]

Люди!!! Просят определить оптимальный для вычисления алгоритм.
А вы "растояние между точками", "перпендикуляр из центра...", "перевод в другие координаты".
Да на построение пенпендикуляра уйдет столько же времени, как и на решение уравнений.

Про описание отрезка многоугольниками... вообще сильно.

Вот Ромкин про окружность толково предложил. Пока лучше ничего не придумал.

← →
Merlin (2003-03-20 13:44) [20]

> Danilka ©

Удивительно, но работает :) Хотя смысла этих формул я не понял...

← →
Merlin (2003-03-20 13:47) [21]

> Romkin ©
> ... и при этом перпендикуляр из центра окружности пересекает
> отрезок и его длина меньше радиуса окружности.

А разве одного этого условия недостаточно?

← →
myor (2003-03-20 13:48) [22]

Romkin © (20.03.03 13:38)

хочу заметить, что условие с перпендикуляром выполняется в обоих случаях (l<d, l>d). я не уверен, что заведомо известно отношение длины отрезка и диаметра окружности, поэтому, как вы предлагаете, сначала проверить расстояния от центра до концов, а потом (вторым этапом) длину перпендикуляра- это неправильно. определение длины перпендикуляра, конечно, сложнее (по-моему нужно уравнение прямой), но это достаточное условия (или я уже переработался).

← →
Merlin (2003-03-20 13:49) [23]

Первый пункт по пересечению отрезков снимается. Функций предложенных Danilka © достаточно.

← →
pasha676 (2003-03-20 13:51) [24]

2myor
ЭЭЭЭ.... max(xi1) - это что за хрен в сутане.

← →
myor (2003-03-20 13:52) [25]

таки переработался. нужен отдых.
хочу домой!!!!!!

← →
pasha676 (2003-03-20 13:54) [26]

По варианту Ромкина
1 - го условия не достаточно. В случае хорды или касательной.

← →
MBo (2003-03-20 13:55) [27]

1 отрезок x1,y2-x2,y2
2 - x1",y1"-x2",y2"
В параметрическом виде (t=0..1)

x=t*ax+bx
y=t*ay+by

bx=x1
by=y1
ax=x2-x1
ay=y2-y1

bx"=x1"
by"=y1"
ax"=x2"-x1"
ay"=y2"-y1"

точка пересечения

ax*t+bx=ax"*t"+bx"
ay*t+by=ay"*t"+by"

решив, получим

Z=(y2-y1)(x2"-x1")-(y2"-y1")(x2-x1)

если Z=0, то отрезки параллельны
иначе

t=[(y1"-y1)(x2"-x1")-(x1"-x1)(y2"-y1")]/z

t"=[(y1"-y1)(x2-x1)-(x1"-x1)(y2-y1)]/z

если и t, и t" лежат в пределах промежутка [0..1], то отрезки пересекаются

← →
pasha676 (2003-03-20 13:56) [28]

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

← →
Romkin (2003-03-20 13:58) [29]

Это граничные условия, я исходил из того, что сама окружность не входит в область. Вместо меньше можно подразумевать "не больше" и тд. Уж на совпадение расстояния с радиусом можно проверить.
Дополнение к п.2: Перпендикуляр из центра окружности к отрезку пересекает отрезок в том и только в том случае, если оба угла между отрезком и направлением на центр окружности на концах отрезка меньше 90 градусов. Установить, меньше или больше этот угол можно через скалярное произведение и модуль вектора.

← →
JibSkeart (2003-03-20 13:58) [30]

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

← →
myor (2003-03-20 14:01) [31]

pasha676 (20.03.03 13:51)
а выше что написано?
a(x11,y11;x12,y12)...
см. johnmen
снимешь сутану, а это и не хрен вовсе.

← →
myor (2003-03-20 14:06) [32]

← →
Romkin (2003-03-20 14:11) [33]

2myor Заработался. Поясняю. Отрезок может полностью принадлежать окружности (лежать внутри нее), и может случится, что перпендикуляр к нему его пересекает... А п.1 у меня - чтобы не делать лишней работы по поиску длины перпендикуляра - если один конец - в окружности, а другой - вне ее, то понятно, что отрезок ее пересекает :-))), и напротив, если оба расстояния меньше радиуса - понятно, что не пересекает (лежит внутри). Остается третий случай - оба конца вне окружности, но пересечение есть (две точки пересечения), см. п.2

← →
myor (2003-03-20 14:37) [34]

Romkin © (20.03.03 14:11)

пояснения излишни. давайте лучше сформулируем алгоритм:
O(x0,y0)- центр окружности, R- радиус,
A(x1,y1), B(x2,y2)- концы отрезка,
P- перпендикуляр из центра на отрезок.

если (A-O>R и B-O<=R) или (A-O<=R и B-O>R)
то пересекает
если A-O>R и B-O>R и P<R
то пересекает

так?

← →
MBo (2003-03-20 14:58) [35]

отрезок описываем параметрически
x=t*ax+bx
y=t*ay+by
(t=0..1)

x=(x2-x1)*t+x1
y=(y2-y1)*t+y1

dx=x2-x1
dy=y2-y1

окружность x0,y0,R

найдем точки пересечения окружности и прямой, на которой лежит отрезок

(x-x0)^2+(y-y0)^2=R^2

(dx*t+(x1-x0))^2+(dy*t+(y1-y0))^2=R^2

раскроем скобки

t^2*(dx^2+dy^2)+t*2(dx*(x1-x0)+dy*(y1-y0))+[(x1-x0)^2+(y1-y0)^2-R^2]=0

a=dx^2+dy^2;
b=2(dx*(x1-x0)+dy*(y1-y0))
c=(x1-x0)^2+(y1-y0)^2-R^2

считаем D этого кв. уравнения. Если <0, пересечения нет
иначе находим 2 точки пересечения (1 при D=0)
Если хотя бы одна в промежутке 0..1, то отрезок пересекается с окружностью.

← →
Axis_Of_Evil (2003-03-20 15:39) [36]

>1. определить факт пересечения двух отрезков
>2. определить факт пересечения отрезка и окружности

И это тема на 35 постов???
С такими офигительно сложными вопросами???
Да ...

← →
Danilka (2003-03-20 15:58) [37]

Merlin © (20.03.03 13:44)
я сам не понял... хотя и пользовался ими. ;))

Кстати, в этом пакете есть еще пересечение эллипса с прямоугольником. Тоже такое-же непонятное. Думаю, при желании можно оттуда вывести пересечение окружности с прямой.

Если надо, могу верезать и выложить сюда.

← →
nikkie (2003-03-20 16:30) [38]

алгоритм Ромкина для задачи с окружностью
даны: точки A,B, и O, радиус R
обозначаем: OA = a, OB = b, AB = c

1. считаем a^2 и b^2

2. a^2 < R^2 and b^2 < R^2 => пересечения нет

3. (a^2 < R^2 and b^2 >= R^2) or (a^2 >= R^2 and b^2 < R^2) => пересечения есть

4. остался вариант (a^2 >= R^2 and b^2 >= R^2). считаем высоту перпендикуляра из O на AB.
h^2 = (2 a^2 b^2 + 2 a^2 c^2 + 2 b^2 c^2 - a^4 - b^4 - c^4) / c^2

5. если h^2 > R^2 - пересечения нет.

6. проверяем, что углы острые. если одно скалярных произведений меньше нуля
(AO, AB) < 0 or (BO, BA) < 0 - пересечения нет

7. иначе пересечение есть.

пункты (4,5) и 6 можно поменять местами.

← →
MBo (2003-03-20 16:32) [39]

>Danilka
>Тоже такое-же непонятное
см. (20.03.03 14:58)

← →
Romkin (2003-03-20 16:33) [40]

4. и 6. местами поменяй - если угол тупой, то и перпендикуляр считать не надо.
А вообще, вместо п. 2 Mbo уже сказал - гораздо проще

Геометрия, блин Найти похожие ветки