Алгоритм перебора Palm3D, который я нашел, является хорошей отправной точкой. Этот метод использует ту же предпосылку, но включает несколько способов пропустить проверку большинства пикселей.
Во-первых, вот код:
int largestX = circle.radius;
for (int y = 0; y <= radius; ++y) {
for (int x = largestX; x >= 0; --x) {
if ((x * x) + (y * y) <= (circle.radius * circle.radius)) {
drawLine(circle.center.x - x, circle.center.x + x, circle.center.y + y);
drawLine(circle.center.x - x, circle.center.x + x, circle.center.y - y);
largestX = x;
break; // go to next y coordinate
}
}
}
Далее объяснение.
Первое, что нужно отметить, это то, что если вы найдете минимальную координату х, которая находится внутри круга для данной горизонтальной линии, вы сразу узнаете максимальную координату х.
Это связано с симметрией круга. Если минимальная координата x находится на 10 пикселей впереди левой части ограничительной рамки круга, то максимальная x находится на 10 пикселей позади правой границы ограничительной рамки.
Причина перехода от высоких значений x к низким значениям x заключается в том, что минимальное значение x будет найдено с меньшим количеством итераций. Это связано с тем, что минимальное значение x ближе к левому краю ограничительной рамки, чем центральная координата x круга для большинства линий, из-за того, что круг изогнут наружу, как видно на на этом изображении
Следующее, что следует отметить, это то, что поскольку круг также симметричен по вертикали, каждая найденная линия дает вам свободную вторую линию для рисования, каждый раз, когда вы находите линию в верхней половине круга, вы получаете одну в нижней половине в радиус-у у координата. Следовательно, когда найдена какая-либо линия, можно нарисовать две, и только верхняя половина значений y должна быть перебрана.
Последнее, что следует отметить, это то, что если вы начинаете с значения y, находящегося в центре круга, а затем двигаетесь к вершине для y, то минимальное значение x для каждой следующей строки должно быть ближе к центру координата х круга, чем последняя строка. Это также связано с тем, что окружность изгибается ближе к значению центра х, когда вы поднимаетесь по кругу. Вот изображение того, как это происходит.
В итоге:
- Если вы найдете минимальную x-координату линии, вы получите максимальную x-координату бесплатно.
- Каждая линия, которую вы рисуете в верхней половине круга, дает вам линию в нижней половине круга бесплатно.
- Каждая минимальная координата x должна быть ближе к центру круга, чем предыдущая координата x для каждой линии при итерации от координаты y центра к вершине.
Вы также можете сохранить значение (radius * radius), а также (y * y) вместо их вычисления
несколько раз.