Есть массив линий. есть точка. Нужно просчитать расстояние от этой точки до ближайшей прямой. Есть ли возможность найти эту ближайшую прямую, не перебирая все линии?

> Есть ли возможность найти эту ближайшую прямую, не перебирая
> все линии?
>

только если линии уже отсортированы по расстоянию:)

Здесь решается схожая задача (поиск ближайшей точки):
http://www.blackpawn.com/texts/cellular/default.html
см. раздел "Making It Fast".
Лично я, правда, так и не смог проникнуться идеей "2D bastard son of a sphere-tree and a bsp-tree". Помучившись некоторое время, сделал по-своему. Как - уже забыл, сейчас пытаюсь понять заново :) Но кажется, мой метод заточен именно под конкретную задачу с последовательным поиском ближайшей точки для каждого пикселя картинки - учитывает, что у соседних пикселей эта точка скорее всего одна и та же.

Задача может иметь разные методы решения для случаев:
1. Набор линий постоянен, нужно искать ближайшую линию для произвольных точек
2. Набор точек постоянен, линии меняются
3. Одноразово найти

Например, для первого случая - набор линий делит плоскость на кучу многоугольников, и ближайшей к точке, лежащей в многоугольнике, будет одна из линий, его образующих. Можно построить т.н. skeleton - т.е. каждый многоугольник делится на несколько частей, каждая из которых ближе всего к одной из линий. Если раскрасить плоскость, то цвет в данной точке сразу даст номер ближайшей линии.

а можно тупо строить перпендикуляры :)

> Здесь решается схожая задача (поиск ближайшей точки):


Попробую въехать...


> Например, для первого случая....

Именно первый случай...


> а можно тупо строить перпендикуляры :)

улыбнуло.

Спасибо за советы. Вот возник вопрос. если массив не линий, а отрезков. Задача как-нибудь меняется?

если отрезки - то меняется, просто перпендикуляром не отделаешься...

> если отрезки - то меняется, просто перпендикуляром не отделаешься.
> ..

Мне интересно, ты стебешься или реально у тебя телепатор сломался????? :)

Я знаю как найти расстояние от точки до прямой/отрезка. у Меня проблема в другом. Массив отрезков/линий очень большой. есть точка. Нужно из этого массива выбрать одну наиболее близкую. не меря расстояние явно. потом найти расстояние. Либо сделать выборку определенного количества линий и потом уже прогнать цикл уже по этой выборке, а не по всей совокупности линий.

яж сказал - без предварительнйо сортировки по тому самому расстоянию придется все перемерять. либо определять отрезки по зонам, и сначала смотреть в какую зону попала точка, потом смотреть отрезки из это зоны. Алгоритм "палка+веревка" :)
Или есть такой волшебный алгоритм? :)

Для набора отрезков или полилиний есть такой метод, который не избавляет от перебора, но в среднем уменьшает количество вычислений:
Каждый отрезок имеет, понятно, ограничивающий прямоугольник.
Находим расстояние до первого сегмента. Окружность с центром в точке, касающаяся первого сегмента, задает ограничивающий ее квадрат. Далее проверяем только пересечение квадрата и огранич. прямоугольников. Если они пересекаются, то тогда уже проверяем расстояние и при необходимости уменьшаем квадрат.

Можно применить и подход, используемый для нахождения ближайшей к данной точки.
Предварительно делим плоскость на квадратные ячейки, для каждой ячейки находим пересекающиеся с ней отрезки. Далее при поступлении точки проверяем только ее ячейку и соседние с ней.

Вообще мне казалось, что подобная задача рассматривалась в Препарата-Шеймос, но навскидку не нашел...

Так. уже лучше. Буду делить плоскость на зоны. И последний тупой вопрос :)
Можно ли объединить 2 вариантных массива в 1 не перебирая все ячейки?

тоесть ни:
var arr11,arr12,arr2: Variant;

......

arr11:=vararraycreate([1,6547,1,3], varVariant);
arr12:=vararraycreate([6548,10000,1,3], varVariant);
arr2:=vararraycreate([1,10000,1,3], varVariant);

for i:=1 to 10000 do
 if  if i<6548 then
  begin
  arr2[i,1]:=arr11[i,1];
  arr2[i,2]:=arr11[i,2];
  arr2[i,3]:=arr11[i,3];
  end else
  begin
  arr2[i,1]:=arr12[i-6547,1];
  arr2[i,2]:=arr12[i-6547,2];
  arr2[i,3]:=arr12[i-6547,3];
  end;

а как нибудь по другому???
ну не знаю, что-нибудь типа copy?

А зачем вариантные массивы?

Подход с ячейками (зонами) будет хорошо работать, если отрезки невелики по сравнению со всей рабочей областью.

> Подход с ячейками (зонами) будет хорошо работать, если отрезки
> невелики по сравнению со всей рабочей областью.


Они длинной 300-400 точек. рабочее поле 30000*60000 точек.


> А зачем вариантные массивы?


Это из другой оперы, хотя приложение одно и тоже. мне нужно загнать в 1 вариантный массив данные из 4х листов экселя, эти данные обрабатываются, и по ним строятся отрезки.

>Они длинной 300-400 точек. рабочее поле 30000*60000 точек.
О, тогда прекрасно.

А насчет массивов не подскажете?

>А насчет массивов не подскажете?
нет. надо смотреть, есть ли что-то в variants.pas, однако вряд ли это заметно ускорит дело.

Ну почему же? мой тест: (измерял время таймером).

var arr1,arr2: Variant;

......

arr1:=vararraycreate([1,10000,1,3], varVariant);
arr2:=vararraycreate([1,10000,1,3], varVariant);
...ЗАПОЛНЯЕМ МАССИВ 1............

arr2:=arr1 //0,3 sec

for i:=1 to 10000 do
begin
arr2[i,1]:=arr2[i,1];
arr2[i,2]:=arr2[i,2];
arr2[i,3]:=arr2[i,3];
end;

/// 5,6 sec

VarArrayLock + Move?
Хотя лучше, как мне кажется, сразу перегнать всё в обычный, невариантный массив. Данные ведь фактически однотипные, варианты нужны только для импорта из Excel?
Всё-таки варианты - это медленно (5 с для 30000 присвоений -
много, независимо от железа).

> VarArrayLock + Move?

Щас прогуглю. спасибо.

> варианты нужны только для импорта из Excel?

да. дело в том, что вот так:  arr:=excel.workbooks[1].worsheets[1].range[cells[1,1],cells[3578,4]].value
получается быстрей поячечного присваивания. причём в разы.


> сразу перегнать всё в обычный, невариантный массив.


так и делаю, но после того, как загоню все 4 вариантных массива в 1.
потом просто делаю динамический массив, и copy туда все даные. Кстати. назрел еще вопрос: как правильно прибить вариантный массив? я делаю так VarArrayRedim(arr; 0); Это правильно?

И по теме. Незнаю, может кому-то пригодится...
Или кто-то скажет косяки.

Сделал так:

var Zones: array[1..300,1..600] of array of ShortInt;
Lines: array of TMathRect;

Loop

[1]. Загружаем координаты концa отрезкa в Lines.
[2]. По этим координатам проверяем в какие зоны попал отрезок.
[3]. Записываем номер отрезка в эти зоны.

Untril кончились_отрезки=true

Записываем номер отрезка в эти зоны. вот так:

http://www.intuit.ru/department/graphics/rastrgraph/3/3.html
(перед этим дели координаты на 100(ширина, высота зоны))

Только вместо Plot(x,y) :
SetLength(Zones[x,y],High(Zones[x,y])+2);
Zones[x,y][High(Zones[x,y])]:=Номер_отрезка;

Немного медленно это всё происходит, но зато при получении точки количество переборов уменьшилось со 100 - 150 тысяч до 20-25 штук. Да и думаю в процессе загрузки приложения можно потерпеть минутку. Всё равно  подгружаемые файлы размером 30-40 мб, поэтому я думаю пользователь не заметит подвоха. :)

Теперь можно даже анимировать движение точки из одного положения в другое с отображением расстояний до ближайшей прямой!