LINUX.ORG.RU

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

 , ,


0

1

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

Проблема в том, что в матане я ноль, и загуглить ничего толкового не удалось. Нагуглил только js-методы в браузерах и svg.js, но они какой-то кривой результат выдают (пруф).

Картинка: https://hostingkartinok.com/show-image.php?id=b05c8e5de02be73009bb88733c06afb1

На картинке у нас прямоугольник к которому применили skew трансформацию и мне нужно получить bbox, который на картинке пунктиром.

То есть локальный bbox у меня есть. Теперь нужно перевести его в глобальный. Но как?

★★★★★

Пусть 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)))

Crocodoom ★★★★★
()
Ответ на: комментарий от RazrFalcon

В общем случае 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 от нескольких произвольных прямоугольников. Собственно точно так же через минимум и максимум координат вершин.

alpha ★★★★★
()
Ответ на: комментарий от RazrFalcon

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

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

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

Crocodoom ★★★★★
()
Ответ на: комментарий от alpha

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

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

RazrFalcon ★★★★★
() автор топика
Ответ на: комментарий от Crocodoom

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

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

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

RazrFalcon ★★★★★
() автор топика
Ответ на: комментарий от RazrFalcon

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

peregrine ★★★★★
()
Ответ на: комментарий от RazrFalcon

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

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

Crocodoom ★★★★★
()
Ответ на: комментарий от Crocodoom

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

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 1)
Ответ на: комментарий от peregrine

Возьми за исходную фигуру 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.

alpha ★★★★★
()
Последнее исправление: alpha (всего исправлений: 1)
Ответ на: комментарий от peregrine

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

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

Crocodoom ★★★★★
()
Ответ на: комментарий от RazrFalcon

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

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

alpha ★★★★★
()
Ответ на: комментарий от alpha

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

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

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

alpha ★★★★★
()
Ответ на: комментарий от Crocodoom

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

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

RazrFalcon ★★★★★
() автор топика

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

peregrine ★★★★★
()

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

gag ★★★★★
()
Ответ на: комментарий от RazrFalcon

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

Это тот, в который гарантированно влезет твоя фигура. Но чтобы это обеспечить и гарантировать надо строить его вокруг старого 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()
Но у тебя SVG, а в SVG крайние точки могут и не храниться, как я понимаю, например если у тебя какая-то кривая, вроде безье. Ну и со шрифтами будет проблема.

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 2)
Ответ на: комментарий от peregrine

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

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

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

RazrFalcon ★★★★★
() автор топика
Ответ на: комментарий от RazrFalcon

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

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

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 2)
Ответ на: комментарий от peregrine

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

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

RazrFalcon ★★★★★
() автор топика
Ответ на: комментарий от RazrFalcon

Пожалуй да. Правда я не знаю, как в пути записываются разные кривые, они могут записываться не обязательно по крайним точкам в теории, но я формат 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

peregrine ★★★★★
()
Последнее исправление: peregrine (всего исправлений: 1)
8 мая 2018 г.
Ответ на: комментарий от RazrFalcon

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

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

gag ★★★★★
()
Ответ на: комментарий от gag

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

RazrFalcon ★★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.