Найти среднюю точку перекрытия между кругом и прямоугольником - PullRequest
Новая
       67

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

1 голос
/ 11 марта 2012

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

Я готов пожертвовать идеальной точностью, если это означает, что алгоритм будет значительно быстрее.

Основной способ представления каждой фигуры:

круг

  • число с плавающей запятой x, y (в центре)
  • float r (радиус)

Прямоугольник

  • float x, y (в центре)
  • float w, h (значения ширины и высоты, они представляют x и y расстояние от центра до соответствующего края).

EDIT:

Поскольку, как представляется, существует путаница в отношении того, что я имею в виду под "средней точкой", позвольте мне уточнить:

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

Пример: http://en.wikipedia.org/wiki/Centroid

РЕДАКТИРОВАТЬ # 2:

Вы, ребята, дали мне некоторые идеи, позвольте мне поработать над некоторыми из них, и я вернусь к вам.

Заключительные мысли:

Я пометил ответ Гарета как принятый, потому что он дал мне идеи того, с чем я в конечном итоге согласился, но моя окончательная реализация отличается от его, поэтому я объясню это здесь.

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

Метод 1: Фрагментация формы:

An example of Shape Fragmentation

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

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

Метод 2: Интерполяция строки

Example of Line Interpolation

Во-первых, вам нужно вычислить точку в прямоугольнике, которая будет базовой точкой. Это должна быть точка, которую легко вычислить, и она совпадает. Для этой точки я использую среднее значение всех пересечений ребер окружности и прямоугольника (если пересечений ребер не существует, я по умолчанию указываю местоположение кружка, поскольку это означает, что одна фигура содержится в другой).

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

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

Ответы [ 4 ]

5 голосов
/ 12 марта 2012

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

rectangle divided into squares, showing which squares belong to the intersection with a circle

Затем примените формулу центроида ,

Центроид плоской фигуры можно вычислить, разделив ее на конечное число более простых фигур, вычислив центроид C i и область A i каждой части, а затем вычисление Σ C i A i / Σ A i .

, что особенно просто в этом случае, потому что центр тяжести квадрата является его центром, и все A i равны.

(Геометрическое рассечение как по предложению Вона Катона получит точный ответ, но этот приблизительный метод обладает преимуществом простоты: его будет намного сложнее запрограммировать неправильно.)

CodeBunny просит в комментариях "более простой, основанный на уравнении результат ".Вот как можно вычислить результат, используя уравнения, но я не думаю, что он «проще».

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

Cases for intersection of circle and rectangle

Затем для каждого случая вы разбиваете пересечение на сумму круглых отрезков и выпуклых многоугольников.Вычислите площадь и центроид для каждого из них (см. Википедию для формул: площадь и центроид круглого сегмента; площадь и центроид выпуклого многоугольника ) и объединитеони использовали формулу центроида, которую я дал выше.

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

2 голосов
/ 12 марта 2012

Один из способов - разбить его на случаи:

  1. Круг полностью внутри прямоугольника
  2. Прямоугольник полностью внутри круга
  3. Круг, пересекающий одну сторону прямоугольника
  4. Круг, пересекающий две соседние стороны прямоугольника (включая и исключая угол).
  5. Круг, пересекающий две противоположные стороны прямоугольника
  6. Круг, пересекающий три стороны прямоугольника
  7. Круг, пересекающий четыре стороны прямоугольника.

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

0 голосов
/ 13 мая 2014

Может быть, слишком поздно ...

Существует простой, точный и быстрый способ сделать это:

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

Затем вы должны рассмотреть пересечение этого треугольника ABO с кругом. Самое большее, вы получите ABO, разделенное на два круглых сектора (APO, QBO) и подтреугольник (PQO). Для каждого из этих секторов и субтреугольников вы можете рассчитать его среднюю точку и площадь с учетом того, что область считается отрицательной, если угол между OA и OB против часовой стрелки.

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

0 голосов
/ 12 марта 2012

Если я правильно понимаю ваше требование, вы хотите найти центр области, где две фигуры перекрываются?

Это правильно?

Есть круг с центром (x, y) и радиусом r. Имеется прямоугольник с центром (x, y), шириной w и высотой h

Итак, вот первый пробел:

Вы не можете определить прямоугольник в плоскости x, y только с его центральной точкой, шириной и высотой. В каком направлении стоит прямоугольник?

Уравнение круга, как описано выше (х-а) ^ 2 + (у-б) ^ 2 = г ^ 2

Можно решить это уравнение одновременно с уравнением для линии, чтобы получить точки пересечения.

Второй разрыв:

Линия может пересекать окружность в 2 точках, в одной точке или без точек - знаете ли вы наверняка, что окружность и прямоугольник всегда будут перекрываться, поэтому две точки линии пересекают окружность?

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

Это ни в коем случае не ответ «это ответ», но я надеюсь, что это немного поможет?

Steve

...