Помощь новичкам


#1734

Есть список координат x;y или объектов. Форма/размеры не важны.

Как правильно искать ближайший элемент, кроме перебора? Хотелось бы способ посовременнее


#1735

Пусть объект - это точка. Пока Вы не обратились к ее координатам, Вы ничего не знаете о ее положении. Поэтому перебрать в любом случае необходимо каждую пару координат. К примеру, вот Вам условие: есть три точки. Координаты первых двух (-2,3) и (1,5). Можете ли Вы, не проверяя координат третьей точки, сказать, какая из трех точек ближе к началу координат?


#1736
type
  TPoint = class
  public
    auto property X: real;
    auto property Y: real;
    
    constructor(x, y: real) := (self.X, self.Y) := (x, y);
    
    function SquareDistanceTo(point: TPoint) := (X - point.X)**2 + (Y - point.Y)**2;
    
    function ToString(): string; override := $'({X}, {Y})';
  end;
  
begin
  var pivot := new TPoint(ReadlnReal('X:'), ReadlnReal('Y:'));
  var points := new TPoint[] (new TPoint(4, 4),
                              new TPoint(2, 2),
                              new TPoint(3, 3));
  points.MinBy(point -> point.SquareDistanceTo(pivot)).ToString().Println();
end.

#1737

Как вариант, корень извлекать нет смысла. В подобных случаях экстремум ищут по квадрату величины.


#1738

Да, спасибо. Так даже лучше.


#1739

Возведение во вторую степень это на много медленнее чем 1 умножение которое выполняется в sqr.


#1740

Да честно говоря, не важно какая там точность, насколько оптимально или что за система отсчёта, хоть пресловутое dist:=abs(x-x’)+abs(y-y’), лишь бы избежать постоянного обновления параметров (так как переоценивать расстояния нужно не часто) и не мучиться приоритетными очередями и прочими хитростями.

Объектов около сотни; может, как-то срезать с заданной выборкой или допусками?


#1741

Спасибо, буду знать.


#1742

Первый раз считаете все и храните результат, последующие - только те, что меняются и сравниваете с запомненным минимумом. А как иначе? Это, конечно, в общем случае.


#1743

Спасибо, Алекс.

Понятно, что изменение координаты точки отсчёта автоматически “смещает” векторы и придётся пересчитывать, но как оптимальнее/современнее делать выборку? Например, можно ли функции min передать формулу и список координат или проще добавить флаг/событие, чтобы объекты сами сравнивали дистанцию и обновляли id если ближе или как-то иначе?

Напомню, речь приблизительно о сотне элементов/объектов


#1744

Я только проснулся и могу тупить, но может вам подойдёт связный список (LinkedList)? Храните в каждом элементе списка точку и её dist. Когда добавляете - сразу вставляйте на нужную позицию. Тогда сравнивать придётся только с примерно половиной элементов (а можно и ещё сократить, если использовать бинарный поиск, хоть он и медленней в связных списках).

А для чего именно вам всё это нужно?


#1745

Пожалуй, я тут присоединюсь к вопросу, заданному @Sun_Serega: можно получить описание задачи в целом? На 100 объектах, если конечно, каждый объект не описывается десятью тысячами точек, координаты которых постоянно изменяются (Вы же не описываете процесс броуновского движения молекул?), вопрос о выборке может оказаться вопросом о паре микросекунд…


#1746

Возможно, кроме (А) поиска ближайших “врагов”-спрайтов, (Б) нахождения и ранжирования “неточного” наиболее близкого значения по цвету/значению и (В) маршрута через ближайшие POI есть и другие применения схожей задачи. На данный момент я ограничил тайминг и порог отсева (10*size=320px для спрайта; советуют 500 единиц отличия по RGB; около 1,2 км для достопримечательностей и максимум 25% расхождение по строковым дистанциям), так что идея с обновлением значений в словаре или упорядоченном списке (sortedset) может и не оптимально, но работает. В общем, как и всегда: надо не надеяться на готовенькое решение мейнстрим, а применять доступные средства)

@Алекс, насколько я пониманию, для моделирования броуновского движения нужны сотни постоянно (realtime) движущихся объектов в кучности, поэтому там задача другая – сразу проверять на столкновение/векторы, а не периодически искать ближайшего


#1747

Всего лишь вопрос о величине кванта времени.


#1748

А можно, всё же, выбрать минимум задач (желательно 1), но при этом максимально подробно их объяснить?


#1749

Например, современное (ООП) осмысление задачи выбора ближайшего цветка.


#1750

Ох уж эта концепция автоматичности, безопасности и повторного использования в .NET – до сих пор многое приходится доделывать через “устаревшие” API, даже работу с вебкамерой… Эх, хоть список одобренных библиотек.

Кстати, пообщался со знакомым учителем информатики (ага - FreePascal/Lazarus и Delphi) и среди прочего он задал действительно интересный вопрос:

А что Вирт, как разработчик “линейки” Паскаля, думает о PascalABC.NEТ?

Никлаус Эмиль Вирт пока жив, в трезвом уме и доброй памяти, контакты его/учеников/коллег можно получить через ETH или FB/LinkedIn… Любое мнение человека такого уровня только в плюс, да и когда ещё такая возможность будет?

Два сообщения подряд не объединяются?


#1751

Нет и слава богу)) А ещё можно редактировать сообщения не 5 мин а целый месяц после написания.


#1752

Имеется откомпилированный проект на ~15МБ, однако упаковка не получается

Есть ли упаковщики для .NET проектов? Спс


#1753

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