Поиск всех точек, общих для двух кругов

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

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

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

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

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

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

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

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

r1 + r2 - D

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

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

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

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

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

Я предполагаю, что «все точки» означают «все пиксели». Предположим, что ваш дисплей имеет 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 являются целыми числами. Скорее пиксели – это маленькие квадраты между линиями сетки. Это предотвратит возникновение проблем с краем.

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

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

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

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