Растеризация 2D полигона
Я использую прозрачный для альфы PNG для этого:
div.semi-transparent {
background: url('semi-transparent.png');
}
Для IE6, необходимо было бы использовать PNG, фиксируют ( 1 , 2 ), все же.
3 ответа
Магическая фраза Google, которую вы хотите, это либо «правило ненулевой обмотки», либо «заливка четного нечетного многоугольника».
См. Записи в википедии:
И то, и другое очень легко реализовать и достаточно быстро для большинства целей. Если проявить некоторую изобретательность, их можно также сделать сглаженными.
Вы можете проверить процедуру заполнения многоугольника в Pygame. Посмотрите на функцию draw_fillpoly .
Алгоритм довольно прост. Он находит все позиции, которые каждый сегмент пересекает по оси Y. Эти пересечения сортируются и затем заполняются по горизонтали каждой парой пересечений.
Это будет обрабатывать сложные и пересекающиеся формы, но, очевидно, вы можете сокрушить этот алгоритм с большим количеством сегментов.
- Триангулируйте свой многоугольник
- Растрируйте каждый из треугольников (если вы используете графический процессор, он может сделать это за вас, это примитивная операция графических процессоров)
- Если в треугольнике нет сегмента, параллельного оси x, то разбейте его на два треугольника с линией, параллельной оси x и проходящей через ее точку со средним y
- Теперь оставшаяся задача - нарисовать треугольник с отрезком, параллельным оси x. Такой треугольник имеет левый и правый сегменты.
- Итерация линий развертки треугольника (от min-y до max-y). Для каждого y вычислите точки левого и правого сегментов в этой строке развертки. Заполните сегмент строки развертки этими двумя точками (простой набор данных).
Сложность равна O (Площадь в пикселях)