Самый быстрый способ закрасить пиксели между двумя точками кистью в форме эллипса?

Question

Скажем, я создаю растровую программу рисования. Моя кисть имеет форму эллипса. Пользователь щелкает, а затем перетаскивает мышь, чтобы нарисовать область. Теперь у меня есть две точки: точка A (там, где они щелкнули) и точка B (первая точка, возвращенная после перетаскивания мышью). Я хочу заполнить все пиксели, которые попадают в область кисти. Какой лучший способ сделать это?

Мой первый подход заключается в том, чтобы вычислить наклон между двумя точками, а затем увеличить значение от точки A к точке B. Для каждой промежуточной точки я ищу все пиксели в пределах диапазона эллипса и включаю их, если они находятся в диапазоне. Но это кажется неэффективным, поскольку пиксели будут часто проверяться более одного раза - часто в несколько раз, поскольку приращение намного меньше, чем эллипс (представьте себе диаграмму Венна).

Есть ли лучший подход к этому? Тот, который более эффективен и минимизирует количество проверок пикселя.

Answer 1

В настоящее время я делаю что-то очень похожее и могу сказать вам, что я делаю:

• Мышь движется, и я получаю очки (х, у), где мышь
• Я использую алгоритм Брезенхэма для оценки линий от одной позиции мыши к другой (я не получаю событие перемещения мыши для каждого пикселя).
• Затем я "проштампую" (он же рисует) кончик кисти (круг) вдоль линии с соответствующим интервалом (20% от кисти).

Поскольку я не знаю, какой язык программирования / фреймворк вы используете, я не могу дать вам код:)