Пересечение прямоугольника и окружности

← →
Override Func (2014-06-14 17:48) [0]

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

p.s. прямоугольник без наклона, т.е. TRect.

заранее спасибо

← →
Павиа (2014-06-14 18:41) [1]

Graphics_Gems_1,ed_A.Glassner.pdf
Graphics_Gems_2,ed_J.Arvo.pdf
Graphics_Gems_3,ed_D.Kirk.pdf

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

Могу ещё предложить по проще, но погрубее метод. Линеарелизовать окружность и использовать пересечение полигонов.

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

← →
Ega23 © (2014-06-14 19:11) [2]

Не понятен смысл вопроса.
Вот есть некое уравнение окружности. Вот есть некое уравнение (система неравенств) прямоугольника.
Что нужно найти? Координаты точек пересечения? Касательные? уравнение поверхности пересечения?

← →
Override Func (2014-06-14 19:32) [3]

> Ega23 © (14.06.14 19:11) [2]

просто: пересекаются или нет.

← →
Ega23 © (2014-06-14 20:08) [4]

> просто: пересекаются или нет.

Посчитать расстояния от центра окружности до каждой из вершин прямоугольника.
Если все 4 больше радиуса, или все 4 меньше радиуса, то не пересекаются.

Вроде так.

← →
Ega23 © (2014-06-14 20:13) [5]

Нет, вру. Если все 4 больше радиуса, то есть варианты.
Тогда придётся на стороны прямоугольника нормали опускать из центра окружности, и уже их расстояния считать.
Если все 4 больше, или все 4 меньше, то не пересекаются.

← →
Юрий Зотов © (2014-06-14 21:07) [6]

Если на экране, то через регионы.

1. Создаем круглый регион.
2. Создаем прямоугольный регион.
3. Находим регион их пересечения.
4. Проверяем, не пустой ли он.

← →
Юрий Зотов © (2014-06-14 21:10) [7]

PS
А если не на экране, то сначала пересчитываем на экран.

← →
DVM © (2014-06-14 21:20) [8]

> А если не на экране, то сначала пересчитываем на экран.

Немного похоже на использование TMemo для загрузки и обработки текстовых файлов, даже если отображения не предусмотрено. Нет?

← →
Юрий Зотов © (2014-06-14 22:22) [9]

> DVM © (14.06.14 21:20) [8]

Нет. TMemo - на экране, а регионы - в памяти. Мы же не собираемся вызывать SetWindowRgn.

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

← →
Юрий Зотов © (2014-06-14 22:29) [10]

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

← →
Кщд (2014-06-14 22:31) [11]

1. уравнение окружности;
2. уравнение на прямоугольник.
система неравенств

опять будете рассуждать про трудоемкость, а не про неспособность автора мыслить?

← →
Dimka Maslov © (2014-06-14 22:31) [12]

>
> Немного похоже на использование TMemo для загрузки и обработки
> текстовых файлов, даже если отображения не предусмотрено.
> Нет?

Я один раз таким образом прикладывал снеговую нагрузку на крышу. У меня была сетка конечных элементов и снеговые карты (изополя нагрузки). Задача стояла вычислить интенсивность нагрузки на каждый конечный элемент. Чтобы не тратить время на поиск (написание) и отладку алгоритма определения пересечения выпуклого четырёхугольника с невыпуклой произвольной замкнутой областью, проще было действовать именно через регионы GDI - определяем регион пересечения элемента и пятна нагрузки - если он нулевой, выкидываем элемент, если не нулевой - вычисляем площадь пересечения и умножаем на интенсивность нагрузки.
Таким образом? я за [6] - это самый простой и доступный способ.

← →
Юрий Зотов © (2014-06-14 22:34) [13]

> DVM © (14.06.14 21:20) [8]

То есть, этот способ похож не на TMemo, а на TStringList. Что совершенно нормально.

← →
Кщд (2014-06-14 22:36) [14]

>Dimka Maslov © (14.06.14 22:31) [12]
фигово, что Вы, зная, что такое изополя нагрузки и МКЭ, пользовали GDI

← →
Юрий Зотов © (2014-06-14 22:45) [15]

> Кщд (14.06.14 22:31) [11]

Мыслить можно по-разному: стандартно и нестандартно. Стандартный способ хорош тем, что он универсален, а нестандартный - тем, что он проще.

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

← →
DVM © (2014-06-14 22:48) [16]

> Юрий Зотов © (14.06.14 22:22) [9]

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

Я думаю ему как раз и надо именно таким способом. Сильно это похоже на задание какое то.
Кроме этого по нынешним временам закладываться на обязательную доступность GDI не стоит наверное.

> Dimka Maslov © (14.06.14 22:31) [12]

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

← →
Дмитрий СС (2014-06-15 03:36) [17]

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

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

← →
Override Func (2014-06-15 09:34) [18]

> Юрий Зотов

GDI нельзя использовать, т.к. его в AS3 нет. :)

← →
Sha © (2014-06-15 09:35) [19]

> Override Func (14.06.14 17:48)

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

← →
Sha © (2014-06-15 10:00) [20]

очень неоптимально, но, может быть, оно работает:

function f(a, b, c: TPoint; r: integer): boolean; var minX, minY: integer; begin; minX:=Min(abs(a.X-c.X), abs(b.X-c.X)); minY:=Min(abs(a.Y-c.Y), abs(b.Y-c.Y)); if (c.X>=a.X) and (c.X<=b.X) then Result:=(minY<=r) else if (c.Y>=a.Y) and (c.Y<=b.Y) then Result:=(minX<=r) else Result:=(minX*minX+minY*minY)<=r*r; end;

← →
Sha © (2014-06-15 11:21) [21]

кроме того, если радиус круга может быть меньше половины стороны прямоугольника,
то надо учитывать возможность нахождения круга целиком внутри прямоугольника:

function f(a, b, c: TPoint; r: integer): boolean; var minX, minY: integer; inX, inY: boolean; begin; minX:=Min(abs(a.X-c.X), abs(b.X-c.X)); minY:=Min(abs(a.Y-c.Y), abs(b.Y-c.Y)); inX:=(c.X>=a.X) and (c.X<=b.X); inY:=(c.Y>=a.Y) and (c.Y<=b.Y); if inX and inY then Result:=true else if inX then Result:=(minY<=r) else if inY then Result:=(minX<=r) else Result:=(minX*minX+minY*minY<=r*r); end;

← →
Дмитрий СС (2014-06-15 12:35) [22]

> Sha © (15.06.14 11:21) [21]

Гениально))

← →
Dimka Maslov © (2014-06-15 13:30) [23]

> Кщд (14.06.14 22:36) [14]

Когда времени на поиск метода решения нет, надо использовать простейший, дающий приемлемый результат. Тем более, что многие, кто знает про МКЭ и изополя нагрузки, понятия не имеют про GDI

← →
Dimka Maslov © (2014-06-15 13:32) [24]

> DVM © (14.06.14 22:48) [16]

Вот погрешность целочисленных вычислений серьёзно бы повлияла не результат. Очень серьёзно.

← →
Кщд (2014-06-15 21:12) [25]

>Дмитрий СС (15.06.14 03:36) [17]
>Не так давно решал задачу, пересекаются ли два прямоугольника. Задача не такая простая, как кажется на первый взгляд.
задача тривиальная
школьная геометрия

← →
Override Func (2014-06-16 04:34) [26]

> Кщд (15.06.14 21:12) [25]

> школьная геометрия

Там есть задания под звёздочкой, их трудно решить.

← →
oldman © (2014-06-16 08:42) [27]

> Ega23 © (14.06.14 20:08) [4]
> > просто: пересекаются или нет.
> Посчитать расстояния от центра окружности до каждой из вершин
> прямоугольника.
> Если все 4 больше радиуса, или все 4 меньше радиуса, то
> не пересекаются.
> Вроде так.

Посчитать расстояние до каждой из сторон (длину попендикуляра на сторону).
Если все больше радиуса - не пересекается.
Иначе - пересекается.

← →
Кщд (2014-06-16 08:44) [28]

>Override Func (16.06.14 04:34) [26]
чтобы определить в какой полуплоскости относительно прямой лежит точка, необходимо подставить координаты точки в уравнение прямой

какие звездочки?

Вам сказали, как решить практически(регионы), сказали, как аналитически(система из двух уравнений) - у Вас остались вопросы?

← →
Кщд (2014-06-16 08:54) [29]

>Ega23 © (14.06.14 20:13) [5]
>Тогда придётся на стороны прямоугольника нормали опускать из >центра окружности, и уже их расстояния считать.
>Если все 4 больше, или все 4 меньше, то не пересекаются.
окружность внутри прямоугольника - все четыре расстояния больше радиуса
прямоугольник внутри окружности - все четыре расстояния меньше радиуса

>oldman © (16.06.14 08:42) [27]
>Посчитать расстояние до каждой из сторон (длину попендикуляра на сторону).
>Если все больше радиуса - не пересекается.
как быть, если на сторону нельзя опустить перпендикуляр(на прямую, конечно, в этом случае можно)?

> как быть, если на сторону нельзя опустить перпендикуляр(на
> прямую, конечно, в этом случае можно)?

два случая:
1. центр окружности принадлежит стороне (пересекается однозначно)
2. центр окружности вне прямоугольника (плюем на этот перпендикуляр, считаем остальные)

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

← →
Override Func (2014-06-16 12:31) [32]

> Кщд (16.06.14 08:44) [28]
> Вам сказали, как решить практически(регионы),

Я же говорю, регионов никаких нету.

> аналитически(система из двух уравнений) - у Вас остались
> вопросы?

Что за система?

← →
Override Func (2014-06-16 12:41) [33]

> Dimka Maslov © (15.06.14 13:32) [24]
>
> > DVM © (14.06.14 22:48) [16]
>
>
> Вот погрешность целочисленных вычислений серьёзно бы повлияла
> не результат. Очень серьёзно.

Так она и повлияла на твой результат получается. В GDI целочисленные координаты.

← →
Кщд (2014-06-16 13:21) [35]

>Override Func (16.06.14 12:31) [32]
>Что за система?
1. Уравнения прямых;
2. Уравнения окружности.
если в школе не учились, пользуйтесь google.

← →
Override Func (2014-06-16 13:43) [36]

> Кщд (16.06.14 08:44) [28]
>
> какие звездочки?

Есть простые задания, после прохождения новой темы, а есть задания под звёздочкой, это те самые сложные задания. Да, та же тема, но трудно.

← →
Кщд (2014-06-16 13:54) [37]

>Override Func (16.06.14 13:43) [36]
вот оно чо...

Радиус окружности мы (я уверен) знаем?
Берем центр окружности за начало координат.
Уравнение окружности принимает вид x^2+y^2=R^2.
В этой системе координат прямоугольник есть четыре отрезка:
x=a1, x=a2, y=a3, y=a4,
ограниченные координатами углов.

дальше писать или сам дойдешь?

> DVM © (16.06.14 12:50) [34]

Исходя из максимального размера региона в 32000 пикселей я подобрал такую систему единиц, чтобы абсолютная погрешность в определении площади пересечения была не более 10 см². Для такой эфемерной величины, как смоделированная снеговая нагрузка, этого вполне было достаточно. Тем более, что коэффициенты надёжности по нагрузке и ответственности сооружения никто не отменял.

Что за проблема посчитать длину 4х перпендикуляров из центра окружности на все стороны? Если хоть один перпендикуляр <= радиуса, то пересечение/касание есть. Работает всегда.

Пересечение прямоугольника и окружности Найти похожие ветки