2D ограничивающая рамка сектора? - PullRequest
8 голосов
/ 26 августа 2009

Я гуглил, пока не посинел, и, если я не пропустил что-то действительно очевидное, я не могу найти какие-либо алгоритмы для вычисления ограничительной рамки 2D-сектора.

Учитывая центральную точку окружающего круга, радиус и углы экстента сектора, каков наилучший алгоритм для вычисления выровненного по оси ограничительного прямоугольника этого сектора?

Ответы [ 3 ]

15 голосов
/ 26 августа 2009
  • Создайте следующие пункты:
    • Центр круга
    • Положение двух радиусов на круге
    • Точки на окружности для каждого угла между двумя, которые делятся на 90 o (максимум 4 точки)
  • Рассчитайте минимальные и максимальные значения x и y из вышеуказанных точек. Это ваша ограничительная рамка
8 голосов
/ 26 августа 2009

Я собираюсь перефразировать ответ Яирчу, чтобы он был понятнее (во всяком случае, для меня).

Пока игнорируйте координаты центра и нарисуйте круг в начале координат. Убедите себя в следующем:

  1. Везде, где дуга пересекает ось, будет максимум или минимум.
  2. Если дуга не пересекает ось, то центр будет одним углом ограничивающего прямоугольника, и это единственный случай, когда это будет.
  3. Единственными другими возможными крайними точками сектора, которые следует учитывать, являются конечные точки радиусов.

Теперь у вас есть максимум 4 + 1 + 2 очка. Найдите максимум и минимум этих координат, чтобы нарисовать прямоугольник.

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

3 голосов
/ 12 февраля 2013

Прежде всего, я прошу прощения, если я допускаю ошибки в написании, но английский не мой родной язык, испанский на самом деле!

Я столкнулся с этой проблемой и думаю, что нашел эффективное решение.

Прежде всего, давайте посмотрим на изображение ситуации

Graphical situation

Итак, у нас есть эллипс (фактически круг) и две точки (C, D), которые указывают на наш сектор. У нас также есть центр нашего круга (B) и угол дуги alpha.

Теперь, в этом случае я сделал это через 360º на porpouse, чтобы посмотреть, сработает ли это.

Скажем, alpha -> -251.1º (это отрицательная причина по часовой стрелке), давайте преобразуем его в положительное значение 360º - 251.1º = 108.9º Теперь наша цель состоит в том, чтобы найти угол деления пополам этого угла, чтобы мы могли найти максимальную точку для ограничительной рамки. (E на изображении), на самом деле, как вы могли догадаться, длина отрезка BE равна радиусу окружности, но у нас должен быть угол, чтобы получить действительные координаты точки E.

Итак 108.9º / 2 -> 54.45º Теперь у нас есть угол.

Чтобы найти координаты E, мы используем полярные координаты, поэтому

x = r * Cos(theta)
y = r * Sin(theta)

у нас есть r и theta, поэтому мы можем вычислить x и y

в моем примере r = 2.82… (на самом деле это иррационально, но я взял первые две десятичные цифры для удобства)

Мы знаем, что наши первые радиусы 87.1º, поэтому тета будет 87.1 - 54.45º -> 32.65º

мы знаем, что * тэта * - это 32.65º, поэтому давайте немного посчитаем

x = 2.82 * Cos(32.65º) -> 2.37552
y = 2.82 * Sin(32.65º) -> 1.52213

Теперь нам нужно откорректировать эти значения до фактического центра круга, чтобы

x = x + centerX
y = y + centerY 

В этом примере круг центрируется на (1.86, 4.24)

x -> 4.23552
y -> 5.76213

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

Мы знаем, что касательная проходит через нашу точку (4.23, 5.76) Теперь нам нужен наклон.

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

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

x = r * Cos(theta)
y = r * Sin(theta)

Итак

p0 = (centerX + 2.82 * Cos(87.1º), centerY + 2.82 * Sin(87.1º))
p1 = (centerX + 2.82 * Cos(-21.8º), centerY + 2.82 * Sin(-21.8º))

(21.8º - это угол, измеренный по часовой стрелке от горизонтальной оси до радиусов, которые находятся ниже его, и поэтому я положил его отрицательным)

p0 (2, 7.06)
p1 (4.48, 3.19)

Теперь давайте найдем наклон:

m = (y - y0) / (x - x0)
...
m = (3.19 - 7.06) / (4.48-2) = -3.87 / 2.48 = -1.56048
...
m = -1.56 

с наклоном нам нужно вычислить уравнение для касательной, в основном это прямоугольник с уже известным наклоном (m = -1.56), который проходит через уже известную точку (E -> (4.23, 5.76))

Итак, у нас есть Y = mx + b, где m = -1.56, y = 5.76 и x = 4.23, поэтому b должно быть

b = 5.76 - (-1.56) * 4.23 = 12.36

Теперь у нас есть полное уравнение для нашей касательной -> Y = -1.56X + 12.36 Все, что мы должны знать, это проецировать точки C и D над этим прямоугольником.

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

Давайте начнем с CH:

Мы знаем (из уравнения Тангета), что наш вектор направления равен (1.56, 1)

Нам нужно найти прямоугольник, который проходит через точку C -> (2, 7.06)

(x - 2) / 1.56 = (y - 7.06) / 1

Делаем алгебру -> y = 0.64x + 5.78

Мы знаем, что есть уравнение для прямоугольника CH, мы должны вычислить точку H.

мы должны решить линейную систему следующим образом

y = -1.56x + 12.36
y = 1.56x + 5.78

Решая это, мы найдем точку H (3, 7.69)

Нам нужно сделать то же самое с прямоугольником DI, поэтому давайте сделаем это

Наш вектор направления (1.56, 1) еще раз

D -> (4.48, 3.19)

(x - 4.48) / 1.56 = (y -3.19) / 1

Делаем алгебру -> y = 0.64x + 0.32

Позволяет решить линейную систему

y = -1.56x + 12.36
y = 0.64x + 0.32

I (5.47, 3.82)

На этом этапе у нас уже есть четыре точки, которые составляют нашу Ограничительную рамку -> C, H, D , I

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

Это чистая алгебра

Допустим, у нас есть следующая система

Ax + By = C
Dx + Ey = F

, то * * тысячу сто сорок одна

Dx = F - Ey
x = (F - Ey) / D
x = F/D - (E/D)y

замена на другое уравнение

A(F/D - (E/D)y) + By = C
AF/D - (AE/D)y + By = C
(AE/D)y + By = C - AF/D
y(-AE/D + B) = C - AF/D
y = (C - AF/D) / (-AE/D + B)
  = ( (CD - AF) / D ) / ( (-AE + BD) / D) )

так

y = (CD - AF) / (BD - AE)

и для x мы делаем то же самое

Dx = F - Ey
Dx - F = -Ey
Ey = F - Dx
y = F/E - (D/E)x

замена на другое уравнение

Ax + B(F/E - (D/E)x) = C
Ax + (BF/E - (DB/E)x) = C
Ax - (DB/E)x = C - BF/E
x (A-(DB/E)) = C - BF/E
x = (C - BF/E)/(A-(DB/E))
  = ((CE - BF) / E) / ((AE-DB) / E)

x = (CE - BF) / (AE - DB)

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...