Как нарисовать заполненный круг без использования умножения?

Question

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

Answer 1

Вот сценарий Python, который демонстрирует, как вы могли бы нарисовать круг без использования умножения. Он использует формулу x + y > r , чтобы проверить, находится ли текущее положение пикселя (x, y) вне круга.

Можно выполнить текущее вычисление квадратов значений с использованием с добавлением, начиная с the rate of change of the difference between the squares of adjacent pixel indices is 2. По мере того, как вы повторяете пиксели, вы будете продолжать добавлять число (назовите этот номер z) на свои вычисления «квадраты», и для каждого пикселя вы также добавите 2 до z.

Функция __init__ ниже содержит некоторые операции умножения. Однако, если размеры изображения постоянны, компилятор выполнит умножение и загрузит только результат на устройство. Если размеры изображения не постоянны, «медленное» умножение нужно выполнять только один раз при запуске, а не один раз на пиксель.

#!/usr/bin/env python 

class CircularMaskGenerator: 
    '''Generates a circular "mask" for an image. 
    Maintains a running computation of squared values to eliminate the need for multiplication''' 

    def __init__(self, w, h): 
     self.image_width = w 
     self.image_height = h 

     # Precompute some important values. 
     # The embedded device doesn't actaully have to do this math; the 
     # compiler does it before loading the code onto the device. 

     self.half_image_width = self.image_width >> 1 
     self.half_image_height = self.image_height >> 1 
     self.radius = self.half_image_height 

     self.squared_half_image_width = self.half_image_width*self.half_image_width 
     self.squared_half_image_height = self.half_image_height*self.half_image_height 
     self.squared_radius = self.radius*self.radius 

     # The "deltas" are the difference between the squared values of adjacent pixel indices. 
     self.initial_x_squared_delta = 1 - self.image_width 
     self.initial_y_squared_delta = 1 - self.image_height 

     self.resetFrame() 

    def resetFrame(self): 

     # Start with a white binary image 
     import Image 
     self.image = Image.new("1", (self.image_width, self.image_height), 1) 
     self.pixels = self.image.load() 

     # Reset indices 
     self.resetColumnIndex() 
     self.resetRowIndex() 

    def processPixel(self): 

     # Write a black pixel if we're outside the circle 
     if self.current_x_squared + self.current_y_squared > self.squared_radius: 
      self.pixels[(self.current_column_index, self.current_row_index)] = 0 

     self.updateIndices() 

    def updateIndices(self): 
     '''Update the indices and squares values''' 

     self.incrementColumnIndex() 

     # Wrap to the next row if necessary 
     if self.current_column_index == self.image_width: 
      self.incrementRowIndex() 

      # Wrap to the next frame if necessary 
      if self.current_row_index == self.image_height: 
       self.writeImage() 
       self.resetFrame() 

    def incrementColumnIndex(self): 
     self.current_column_index += 1 
     self.current_x_squared += self.current_x_squared_delta 
     self.current_x_squared_delta += 2 

    def resetColumnIndex(self): 
     self.current_column_index = 0 
     self.current_x_squared = self.squared_half_image_width 
     self.current_x_squared_delta = self.initial_x_squared_delta 

    def incrementRowIndex(self): 
     '''The row increment has to send the column index back to the left.''' 

     self.resetColumnIndex() 

     self.current_row_index += 1 
     self.current_y_squared += self.current_y_squared_delta 
     self.current_y_squared_delta += 2 

    def resetRowIndex(self): 
     self.current_row_index = 0 
     self.current_y_squared = self.squared_half_image_height 
     self.current_y_squared_delta = self.initial_y_squared_delta 

    def writeImage(self): 
     '''Save the image in PNG format in the current directory''' 
     self.image.save("output.png", "PNG") 

# ============================================================================= 
def simulate_system(): 

    image_width = 800 
    image_height = 600 

    # initialize the system 
    circle_processor = CircularMaskGenerator(image_width, image_height) 

    # supply a pixel stream to drive the system 
    for i in xrange(image_width*image_height): 
     circle_processor.processPixel() 

# ============================================================================= 
if __name__ == "__main__": 
    simulate_system()

Этот код создает в центре круга, как так:

Answer 2

Известное midpoint circle algorithm рисует круг, используя только сложение и вычитание.