У меня есть произвольная прямоугольная декартова сетка, разделенная на потенциально 10 ^ 6 или около того прямоугольных ячеек. (Произвольный означает, что сетка $ x $ проходит вдоль точек $ x_1, ... x_n $, и то же самое относится к сетке $ y $.) Я хотел бы нарисовать произвольный объект поверх нее (скажем, повернутый прямоугольник или кружок) и эффективно рассчитать, какая доля каждой ячейки перекрывается объектом: если ячейка находится полностью внутри границ объекта, 1,0; если ячейка полностью снаружи, 0,0; если половина ячейки покрыта объектом, 0,5. Если вы отобразите это как изображение и масштабируете его, где 1 - черный, а 0 - белый, результат будет выглядеть как сглаженный рисунок черного объекта.
Мое приложение для этого вопроса написано на Python, и кажется, что эта возможность может быть предоставлена некоторой существующей графической библиотекой. Есть ли модуль Python, который будет проверять дробное пересечение прямоугольника и произвольного объекта? Существует ли библиотека Python, которая может хотя бы эффективно проверить, находится ли точка внутри произвольного объекта, такого как повернутый прямоугольник?