Нахождение всех точек, общих для двух кругов

Question

Как в Python найти все целые точки, общие для двух окружностей?

Например, представьте диаграммное пересечение Венна из двух (одинакового размера) окружностей с центральными точками (x1,y1) и (x2,y2) и радиусами r1=r2. Кроме того, мы уже знаем две точки пересечения окружностей: (xi1,yi1) и (xi2,yi2).

Как можно было бы эффективно составить список всех точек (x,y), содержащихся в обоих кругах? То есть было бы просто нарисовать прямоугольник, содержащий пересечения, и перебрать его, проверяя, находится ли заданная точка в обеих окружностях, но есть ли лучший способ?

Answer 1

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

Скажем, сначала вы выполняете итерацию по оси x, а затем по оси y, вместо того, чтобы перебирать координаты ограничивающего прямоугольника, выясните, где каждый круг пересекает линию x, более конкретно вас интересует координата y точек пересечения, и итерация между ними (обратите внимание на округление)

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

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

Answer 2

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

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

r1 + r2 - D

с D - это разделение двух центров. Обратите внимание, что этот прямоугольник вообще не выровнен с осями X и Y. (Это также дает вам тест на то, пересекаются ли два круга!)

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

Answer 3

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

Answer 4

Имейте в виду, что здесь есть четыре случая.

1. Ни один круг не пересекается, что означает, что «общая область» пуста.
2. Один круг полностью находится внутри другого, означая, что "общая область" - это меньший / внутренний круг. Также обратите внимание, что вырожденным случаем этого является случай, когда они являются одинаковыми концентрическими окружностями, что должно быть так, если учесть критерии, что они являются кружками равного диаметра, которые вы указали.
3. Два круга касаются одной точки пересечения.
4. «Общий» случай, когда будут две точки пересечения. Оттуда у вас есть две дуги, которые определяют закрытую область. В этом случае метод рисования прямоугольников может работать на данный момент, я не уверен, что есть более эффективный метод для определения того, что содержится в пересечении. Обратите внимание, однако, если вы просто заинтересованы в области, есть формула для этого.

Answer 5

Я предполагаю, что под "всеми точками" подразумевается "все пиксели". Предположим, что ваш дисплей имеет размер NX от NY. Есть два массива

int x0[NY], x1[NY]; initially full of -1.

Пересечение ромбовидное, между двумя кривыми. Итерируйте значения x, y вдоль каждой кривой. Для каждого значения y (то есть, где кривая пересекает y + 0,5) сохраните значение x в массиве. Если x0 [y] равно -1, сохраните его в x0, иначе сохраните в x1.

Также следите за самыми низкими и самыми высокими значениями y.

Когда вы закончите, просто выполните итерацию по значениям y, и в каждом y выполните итерацию по значениям x в диапазоне от x0 до x1, то есть for (ix = x0[iy]; ix < x1[iy]; ix++) (или наоборот).

Важно понимать, что пиксели не являются точками, где x и y являются целыми числами. Скорее пиксели - это маленькие квадраты между линиями сетки. Это избавит вас от проблем с крайними случаями.

Answer 6

То есть вы хотите найти точки решетки, которые находятся внутри обоих кругов?

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

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