Нахождение всех точек, характерных для двух кругов
В Python, как можно было бы найти, все целое число указывает характерный для двух кругов?
Например, вообразите Венна подобным схеме пересечением два (одинаково измеренный) круги с центральными точками (x1,y1) и (x2,y2) и радиусы r1=r2. Кроме того, мы уже знаем, что две точки пересечения кругов (xi1,yi1) и (xi2,yi2).
Как можно было бы генерировать список всех точек (x,y) содержавшийся в обоих кругах эффективным способом? Таким образом, было бы просто потянуть поле, содержащее пересечения и выполнить итерации через него, проверив, ли данная точка в обоих кругах, но является там лучшим путем?
5 ответов
Вы также можете изучить различные алгоритмы отсечения, используемые при разработке графики. Я использовал алгоритмы отсечения для решения множества проблем, подобных тем, о которых вы здесь спрашиваете.
Если расположение и радиус ваших кругов могут меняться с детализацией меньше, чем ваша сетка, то вы все равно будете проверять несколько точек.
Вы можете минимизировать количество проверяемых точек, правильно определив область поиска. Он имеет ширину, равную расстоянию между точками пересечения, и высоту, равную
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, то есть для (ix = x0 [iy]; ix
Важно понимать, что пиксели - это не точки, в которых x и y являются целыми числами. Скорее пиксели - это маленькие квадратики между линиями сетки. Это предотвратит возникновение краевых проблем.
Имейте в виду, что здесь четыре случая.
- Ни один из кругов не пересекается, что означает, что «общая зона» пуста.
- Один круг полностью расположен внутри другого, что означает, что «общая область» - это меньший / внутренний круг. Также обратите внимание, что вырожденный случай этого - если они представляют собой тот же концентрический круг, что должно быть так, учитывая критерии, что они являются кругами равного диаметра, которые вы указали.
- Два круга касаются одной точки пересечения.
- «Общий» случай, когда будут две точки пересечения. Оттуда у вас есть две дуги, которые определяют замкнутую область. В этом случае метод рисования прямоугольником может работать сейчас, я не уверен, что есть более эффективный метод определения того, что содержится в пересечении. Однако обратите внимание: если вас интересует только местность, для этого есть формула .
Итак, вы хотите найти точки решетки, которые находятся внутри обоих кругов?
Предложенный вами метод рисования прямоугольника и перебора всех его точек кажется мне самым простым. Вероятно, это будет эффективно, если количество точек в прямоугольнике сопоставимо с количеством точек на перекрестке.
И даже если он не настолько эффективен, насколько это возможно, вам не следует пытаться оптимизировать его, пока у вас не появится веская причина полагать, что это настоящее узкое место.