Получение размеров 2d объекта после трансформации

Пусть A : R^2 -> R^2 — аффинное преобразование, F — исходная фигура.

Выбери, что тебе нужно получить: BBOX(A(F)) или BBOX(A(BBOX(F)))?

Пытаюсь понять как получить глобальный/screen bounding box для объекта/фигуры после применения аффинной трансформации.

Это BBOX(A(F))

Картинка: https://hostingkartinok.com/show-image.php?id=b05c8e5de02be73009bb88733c06afb1
На картинке у нас прямоугольник к которому применили skew трансформацию и мне нужно получить bbox, который на картинке пунктиром.

А на картинке у тебя BBOX(A(BBOX(F)))

Понятно, что BBOX(A(F)) ⊆ BBOX(A(BBOX(F)))

Ничего не понял... Можно какой-то пример?

В общем случае bounding box объекта после преобразования никак не связан с bounding box объекта до него. Поэтому BBox надо считать в новых координатах наплевав на что там было в трансформации, а только исходя из свойств результата.

Если у тебя объект - многоугольник, то при любом аффинном преобразовании он останется многоугольником. Соответственно bounding box многоугольника по определению рассчитывается через минимум и максимум _новых_ координат его вершин:

X_1 = min_X
Y_1 = min_Y

X_2 = max_X
Y_2 = max_Y

Если у тебя эллипс - то после трансформации он остается эллипсом, значит надо уметь считать bounding box для эллипса произвольного вида исходя из длины и положения полуосей.

И т.п.

Для составных фигур BBox группы есть BBox от BBox каждого элемента группы. То есть надо уметь считать BBox от нескольких произвольных прямоугольников. Собственно точно так же через минимум и максимум координат вершин.

https://image.ibb.co/dpgEWb/b05c8e5de02be73009bb88733c06afb1.png

A(BBOX(F)) — чёрный
BBOX(A(BBOX(F))) — чёрный пунктир
BBOX(A(F)) — зелёный
A(F) — красный

Видно, что зелёный (истинный) BBOX намного меньше пунктирного. Ты определись, что тебе на самом деле нужно.

Грубо говоря преобразовываем фигуру в path, к неё применяем трансформацию, получаем bbox. Так?

Это было изначальное решение, но тут появляются проблемы с текстом, ибо его переводить в path - боль.

Я не понимаю что вы пишете в inline.

Мне нужен пунктирный прямоугольник. А изначально был тот, что у вас зелёный.

То есть можно ли получить «чёрный пунктир» из «зелёный» зная трансформацию?

Можно. Но скорее всего будут ошибки округления, они приемлемы (хотя если ты делаешь всё преобразование, то это не страшно)? А так, смотри на эту статью с хабра, там расписано что матрица аффинных преобразований делает с координатами рисунка. Можешь брать старые координаты рамки и преобразовывать их матицей преобразования (ты же сказал, что знаешь преобразование, т.е. матрицу). Правда, как я догадываюсь, в случае поворота фигуры у тебя рамка не поворачивается? Т.е. надо вписывать фигуру в новую рамку? Можешь формулы немного изменить для этого, правда надо геометрию знать неплохо.

У тебя есть какие-то базовые объекты, для которых уже известен bbox. И ты хочешь узнать bbox этих же фигур после аффинной трансформации. Правильно?

Тогда эта задача решается довольно просто. Но ты должен понимать, что результат будет неоптимальным, иногда существенно неоптимальным. Ты получишь новый bbox, но это будет уже не minimum bbox. Картинка это и иллюстрирует.

но это будет уже не minimum bbox

В смысле? По какой причине?

На картинке я уже показывал разницу

Красная фигура это черная после трансформации? Или ты рамки фигуры считаешь за box? И да, нарисуй минимальный box.

Возьми за исходную фигуру F ромб - единичный квадрат повернутый на 45 градусов.

Его bounding box BBOX(F) - это квадрат со стороной = sqrt(2)

Теперь применяем преобразование A - поворот на 45 градусов.

Ромб превращается в A(F) - единичный квадрат. Старый bounding box превращается в A(BBOX(F)) - ромб с диагональю = 2.

Если считать новый bounding box по определению, как BBOX(A(F)), то BBOX от единичного квадрата - это сам этот квадрат.

Если считать новый bounding box как bounding box от преобразованного старого bbox, то есть BBOX(A(BBOX(F))), то получится квадрат со стороной 2. В два раза больше «правильного» bounding box.

Не, изначально там было только две фигуры - чёрная и пунктир (это картинка ТС). Чёрная - это bbox после аффинного преобразования, пунктир - искомый bbox. По-крайней мере, я так понял.

Так как на исходной картинке не было самой фигуры, пришлось её дорисовать. Пусть это был ромб. Он изображен красным цветом, уже после аффинного преобразования. И его новый minimum bbox — зелёным цветом. Видно, что он меньше пунктирного.

Применяем трансформацию, получаем новую фигуру. Забываем про трансформацию.

У новой фигуры считаем bbox.

В случае текста задача такая: посчитать bounding box для текста произвольно расположенного на листе.

Какими параметрами задается текст? Например координатами baseline, направлением «вверх» и максимальной высотой букв. Тогда из этих данных строим параллелограмм, и для него находим bounding box.

Что там было раньше с преобразованием - совершенно не важно. Важны параметры фигуры здесь и сейчас.

Чёрная - это bbox после аффинного преобразования

Нет. Это сама фигура. Но да, у неё bbox равен фигуре.

Тогда просто бери min/max координат четырёхугольника, и будет bbox

Который наклонён/черный? Так я не знаю его координаты.

А что тогда знаешь?

Я тебе скину кодец (правда плохенький, в плане оптимизаций так вообще ужасный, т.к. стараюсь писать его не оптимально, а наиболее наглядно и на коленке), наверно ночью, а может завтра вечером, мне самому интересно стало, я давно 2D графику не писал, так что медленно вспоминаю что да как. Как я понял, ты знаешь преобразование (либо в виде матрицы преобразований, либо в виде аргументов функции для skew трансформации) и старый AABB (axis-aligned bounding box), а хочешь получить новый AABB, после трансформации.

Да, матрица у меня есть.

(мимо проходил) так и не понял, необходим ли именно минимальный bbox или сойдёт какой-нибудь. Для минимального, похоже, знания о трансформации не помогут.

Какой-нибудь - это какой?

BBOX(A(BBOX(F))), например.

Какой-нибудь - это какой?

Это тот, в который гарантированно влезет твоя фигура. Но чтобы это обеспечить и гарантировать надо строить его вокруг старого AABBOX-а после поворота. Т.е. он практически во всех случаях (а точнее если был поворот) будет больше, чем надо. Вообще тебе надо перебирать координаты крайних точек как-то так (код очень не оптимален в плане того, что координаты изначально не хранятся в массиве, но так нагляднее, ИМХО):

# -*- coding: utf-8 -*-
from tkinter import *


class Point:
    def __init__(self, x_init, y_init):
        self.x = x_init
        self.y = y_init


def draw_polygon_with_bounds(points_init):
    max_y = points_init[0].y
    max_x = points_init[0].x
    min_y = points_init[0].y
    min_x = points_init[0].x
    temp_points = list()
    for i in points_init:
        temp_points.append(i.x)
        temp_points.append(i.y)
        if i.x > max_x:
            max_x = i.x
        if i.y > max_y:
            max_y = i.y
        if i.x < min_x:
            min_x = i.x
        if i.y < min_y:
            min_y = i.y
    canv.create_rectangle(min_x, min_y, max_x, max_y, fill='white', outline='green')
    canv.create_polygon(*temp_points, fill='white', outline='black')


scene_width = 640
scene_height = 480

points = list()

points.append(Point(40, 40))
points.append(Point(100, 30))
points.append(Point(80, 80))
points.append(Point(30, 90))

canv = Canvas(width=scene_width, height=scene_height, bg='white')
canv.pack()
draw_polygon_with_bounds(points)
mainloop()

Спасибо за пример, но это не то. Тут нет матрицы. То есть у вас координаты объекта уже после трансформации, а у меня этого нет.

Намалевал подробный пример: https://hostingkartinok.com/show-image.php?id=9d3ac6d142c21f0f2bd15dced8d4d86c

То есть я знаю bbox оригинала и трансформацию. Мне нужно получить bbox после трансформации.

Тут нет матрицы

Знаю. я не стал её делать, т.к. AABB не будет минимальным, он будет больше чем нужно. Дело в том, что при повороте фигуры придется пересчитывать весь AABB, т.к. нет никаких гарантий, что между двумя точками, которые описывали старые соприкасающиеся границы AABB нет точки, которая делала бы отрезок между ними выпуклым наружу. Если такая точка есть, то при повороте она вылезет за границы AABB, который просто повернули, учитывая изменения старых вершин. Т.е. наглядно это как-то так будет. Так что можешь либо делать трансформацию старого aabb и вокруг него строить по приведенному алгоритму новый aabb, но это будет неоптимально, т.е. как-то так, например, либо полный пересчет всех крайних точек. Другого там не будет.

То есть получается что проще/надёжнее перевести фигуру в путь, к нему применить трансформацию и уже у этого пути искать bbox.

Я пытался подсмотреть реализацию у librsvg, но он криво работает. И так нечто похожее на ваш пример: https://github.com/GNOME/librsvg/blob/47895f00461271271e6c668c259d87ea3160f77...

Пожалуй да. Правда я не знаю, как в пути записываются разные кривые, они могут записываться не обязательно по крайним точкам в теории, но я формат SVG не знаю. Кстати, конструкцию вида:

if i.x > max_x:
    max_x = i.x
if i.y > max_y:
    max_y = i.y
if i.x < min_x:
    min_x = i.x
if i.y < min_y:
    min_y = i.y

if i.x > max_x:
    max_x = i.x
elif i.x < min_x:
    min_x = i.x
if i.y > max_y:
    max_y = i.y
elif i.y < min_y:
    min_y = i.y

То есть я знаю bbox оригинала и трансформацию. Мне нужно получить bbox после трансформации.

И как, кинул эту идею попытки использования bbox оригинала и просто считаешь bbox нового объекта?

Перевожу в path, применяю трансформации, считаю bbox. Работает хорошо. Уже в релизе.