Редактирование изображения в графическом редактора

@shyub · Регистрация: 11.07.2013

Студворк — интернет-сервис помощи студентам

Во многих CAD-редакторах есть функция перетаскивания вершин.
Допустим, я начертил ломаную линию и мне необходимо при редактировании передвинуть выбранную вершину.

Редактирование изображения в графическом редактора

Я предполагаю, что помимо отрисовки надо в памяти сохранять координаты вершин и при перемещении мышки сравнивать её координаты с координатами сохраняемых вершин. При их примерном совпадении выделять требуемую. Однако, это работает, если вершин не слишком много.
А как поступают, если на чертеже несколько десятков тысяч вершин, чтобы редактор "не тормозил"?

@vantfiles · 25.07.2023, 15:14

Mikhaylo, спасибо, я думал, меня тут никто не понял.

@Shamil1 · 25.07.2023, 22:18

Сообщение от Igor3D

Однако никакого стандартного, канонического, общепринятого и.т.п. решения не видно и не слышно.

Стандартное решение есть!
Загнать в DB, а затем select top 1 ... order by st_distance(...).

@Igor3D · 26.07.2023, 11:49

Сообщение от Shamil1

Стандартное решение есть!
Загнать в DB, а затем select top 1 ... order by st_distance(...).

Ничего не знаю о БД (наверно дорогое удовольствие), но полагаю проблемы те же. Применить сортировку или ассоциативный контейнер мы конечно можем. Но беда в том что его придется пере-создавать на каждый чих, а это операция дорогая. Поиск в самом контейнере тоже гемор. Интересующий нас "диапазон" (все что попало в прицел) не будет сплошным/непрерывным, придется выцарапывать по кускам. Выходит коряво, а при достаточно большом прицеле (выбор рамкой) это становится медленнее прямого перебора. В общем, мерзкая задачка

@vantfiles · 26.07.2023, 12:49

Сообщение от Igor3D

В общем, мерзкая задачка

Лично мне это говорит о том, что Вы не работали с сортированными списками.
Shamil1, я оценил юмор.

Добавлено через 2 минуты

Сообщение от Igor3D

это операция дорогая.

В том то и дело, что нет. Я же говорил - человек рисует точки и отрезки в разы медленнее вставок в упомянутою мной таблицу.

Добавлено через 4 минуты
И еще про флоаты и даблы.
Целочисленная арифметика здесь более уместна.
Даже если на чертеже нам нужна будет микронная точность.

Добавлено через 32 секунды
Почему так - предлагаю подумать самостоятельно.

@Igor3D · 26.07.2023, 15:20

Сообщение от vantfiles

Лично мне это говорит о том, что Вы не работали с сортированными списками.

Список - организация данных где элемент знает последующий и, возможно, предыдущий. Это обеспечивает эффективную вставку/удаление но ценой отсутствия прямого доступа. Отсортировать список можно (хотя придется постараться), но двоичный поиск (деление отрезка пополам) сработает печально. Возможно Вы употребили слово "список" в широком смысле, типа "контейнер", но почему я должен гадать?

Сообщение от vantfiles

..упомянутою мной таблицу

А с какой стати таблица хранит сами данные (координаты точек)? Эти данные хранятся ядром приложения и вспомогательные структуры поиска не должны знать в каком формате, а только иметь интерфейс доступа к ним. Поиск должен оперировать/возвращать ссылки на данные, в широком смысле, напр индексы, указатели, итераторы. Заметим что повторяющиеся точки - дело рядовое. Пример: сколько вертексов (точек) у простейшего кубика? Нормальный человек ответит 8, но пользователь OpenGL знает "правельный ответ" - 24

Сообщение от vantfiles

Целочисленная арифметика здесь более уместна.

Поиск - небольшая локальная задача, не его дело решать что уместно/неуместно и диктовать точность данных. Если Вы хотели использовать "округленные" значения - надо об этом заявить, там тоже непросто

Вообще впечатление что Вы буквально следуете картинке стартового поста, типа "найти точку в маленьком зеленом квадратике"

Поверьте, все намного хуже, точек внутри может быть сколько угодно (хоть мульен) - и все они должны быть найдены, и квадратик может быть огромным

@vantfiles · 26.07.2023, 18:25

Сообщение от Igor3D

"округленные" значения - надо об этом заявить, там тоже непросто

Я имел в виду арифметику с фиксированной точкой.

@Mikhaylo · 26.07.2023, 18:30

vantfiles, в CAD наверное плавающая точка особо и не нужна, ибо речь идет о координатах точек, размерах и т.п... Но фиг знает, с чем там черт шутит... Один маленькую детальку начертит, другой - плотину через огромную реку. Но в целом, вообще это на решение мало влияет.

@Shamil1 · 26.07.2023, 21:30

Сообщение от Igor3D

придется пере-создавать на каждый чих

Этим занимается СУБД, а пользователь просто добавляет записи (строки) в таблицу и не забивает себе голову деталями реализации СУБД.

Сообщение от Igor3D

Отсортировать список можно (хотя придется постараться)

Это довольно просто. Нужно перегнать его в массив, отсортировать и перегнать обратно в список. По времени займёт примерно столько же, сколько сортировка массива.

@Igor3D · 27.07.2023, 18:19

Не по теме:

Сообщение от Shamil1

Это довольно просто. Нужно перегнать его в массив, отсортировать и перегнать обратно в список. По времени займёт примерно столько же, сколько сортировка массива.

Более в духе списка (интересные, необычные решения) будет сортировка без всяких перемещений, т.е. адреса эл-тов не меняются после сортировки

Как работает "графический редактора" (в общих чертах). Есть оригинальное/исходное представление точек, обычно это 3D координаты записанные в отдельных файлах. Эти базовые данные могут рисоваться всяко-разно в различных окнах, но конечно они не меняются для каждого вида/проекции рисования. Применяется ф-ция/метод (псевдокод)

C++
1
Point2D Transform( const Point3D &, ... );

который из исходной делает точку для рисования на экране в конкретном окне. Часто это просто умножение на матрицу, но не всегда. Хотя трансформация выполняется достаточно быстро, на миллионах точек это время ощутимо. Также общее число точек принципиально не ограничено, просто больше тормоза

Вернемся к злополучной таблице. Конечно имеем полное право пересчитать исходные точки для данного вида, можно и округлить до целых если хотим. Но это спорно/проблематично, зачем хранить то что можно считать на лету? А главное - зависим от вида, чуть он изменился (другой Transform) - и все перезаполнять по новой

Ну и напомню что найденное нужно возвращать. Напр результатом обращения к таблице должен быть ответ типа: "выбраны точки с индексами 3, 10, 11 в исходных данных" возможно чтобы "редактора" могла их подсветить

@Shamil1 · 27.07.2023, 22:14

Сообщение от Igor3D

округлить до целых если хотим

Зачем округлять до целых, если числа с фиксированным количеством знаков после запятой ничем от целых не отличаются?

@vantfiles · 28.07.2023, 14:46

Сообщение от Shamil1

если числа с фиксированным количеством знаков после запятой

Вот-вот. При этом на 32 разрядах и микронной точности можно наваять чертеж с габаритами 4 метра 294 сантиметра
А на 64 разрядах - вообще получится 18446744073 метра 709 сантиметров.

Добавлено через 1 минуту
Авианосец можно отрисовать %)

Добавлено через 2 минуты
Гы-гы, в разрезе.

@Igor3D · 28.07.2023, 17:23

Сообщение от Shamil1

Зачем округлять до целых, если числа с фиксированным количеством знаков после запятой ничем от целых не отличаются?

Как упоминалось выше, мы не собираемся хранить данные в структуре поиска, поэтому можем разделить точки (сначала) по X с любым шагом, никакие фокусы здесь не нужны

C++
1
2
3
// Структура данных поиска
using YPair = std::pair<float, int>; 
struct Picker : public std::map<int, std::vector<YPair>>

Все точки преобразуются в экранные координаты и помещаются в эту структуру

C++
1
2
3
4
5
void Picker::AddPoint( const Point & pt, int index ) 
{
  int key = (int) floor(pt.x / m_step);
  (*this][key].push_back(YPair(pt.y, index));
}

Обязательно сохранять только индекс в исходном контейнере, его(их) поиск будет возвращать. x/y точки можно хранить/кешировать (быстрее) но можно и вычислять (меньше памяти) имея индекс. m_step - шаг деления по x. Напр при m_step = 1.25 все точки с x [1.25..2.5] попадут в вектор по ключу мапы = 1. Шаг меньше 1 возможен но особого смысла не имеет для выбора на экране. После добавления всех точек придется пробежаться по мапе и отсортировать все вектора

Сам поиск

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
std::vector<int> Picker::Pick( const Point & minP, const Point & maxP ) const
{
  std::vector<int> resut;
  int minKey = (int) floor(minP.x / m_step);
  int maxKey = (int) floor(maxP.x / m_step);
  auto it_x = this->lower_bound(key);
  while (it_x != end()) { 
    if (it_x->first >= maxKey) break;
    const auto & vec = it_x->second;
    auto it_y = std::lower_bound(vec.begin(), vec.end(), YPair(minP.y, 0));
    while (it_y != vec.end()) {
     if (it_y->first >= maxP.y) break;
     result.push_back(it_y->second);
     ++it_y;
    }
    ++it_x;
  }
  return result;
}

Все это вполне разумно, но структура жирновата, ее построение затратно и не гарантирует отсутствие тормозов/заминок. Что собсно и вызывает мое недовольство.

Новые блоги и статьи Все статьи Все блоги /
[golang] Двоичная куча, min-heap alhaos 20.05.2026 Двоичная куча Двоичная куча — структура данных, которая всегда держит самый важный элемент наготове. Представьте очередь к хилеру в игре, и очередь из игроков в приоритете те у кого меньше. . .	[golang] Breadth-First Search alhaos 19.05.2026 BFS (Breadth-First Search) — это базовый алгоритм обхода графа в ширину, который поуровнево исследует все связанные вершины. Он начинает с выбранной точки и проверяет всех соседей, прежде чем. . .	[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;
FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .	Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .

@shyub 396 / 196 / 49 Регистрация: 11.07.2013 Сообщений: 1,216

	Редактирование изображения в графическом редактора 21.07.2023, 10:23. Показов 1361. Ответов 31 Метки нет (Все метки) Во многих CAD-редакторах есть функция перетаскивания вершин. Допустим, я начертил ломаную линию и мне необходимо при редактировании передвинуть выбранную вершину. Я предполагаю, что помимо отрисовки надо в памяти сохранять координаты вершин и при перемещении мышки сравнивать её координаты с координатами сохраняемых вершин. При их примерном совпадении выделять требуемую. Однако, это работает, если вершин не слишком много. А как поступают, если на чертеже несколько десятков тысяч вершин, чтобы редактор "не тормозил"? 0

@vantfiles 1018 / 1921 / 177 Регистрация: 07.05.2013 Сообщений: 3,931 Записей в блоге: 12
	25.07.2023, 15:14
	Mikhaylo, спасибо, я думал, меня тут никто не понял. 0

@Mikhaylo 818 / 577 / 75 Регистрация: 20.09.2014 Сообщений: 3,768
	26.07.2023, 18:30
	vantfiles, в CAD наверное плавающая точка особо и не нужна, ибо речь идет о координатах точек, размерах и т.п... Но фиг знает, с чем там черт шутит... Один маленькую детальку начертит, другой - плотину через огромную реку. Но в целом, вообще это на решение мало влияет. 0