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

Question

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

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

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

Круг:

• флоат х, у (в центре)
• поплавка г (радиус)

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

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

---

EDIT:

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

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

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

---

EDIT # 2:

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

---

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

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

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

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

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

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

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

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

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

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

Answer 1

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

Затем нанесите the centroid formula,

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

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

(Геометрическая рассечение, как suggested by Vaughn Cato получит точный ответ, но этот приближенный метод имеет преимущество простоты:. Это будет гораздо сложнее программировать его неправильно)

---

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

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

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

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

Answer 2

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

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

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

Answer 3

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

Верно ли это?

Существует окружность с центром (x, y) и радиусом r. Существует прямоугольник с центром (х, у), ширина W и высота Н

Так вот первый разрыв:

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

Уравнение окружности, как описано выше, является (Xa)^2 + (Yb)^2 = R^2

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

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

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

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

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

Стив

Answer 4

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

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

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

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

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