for flooders
:: Главная :: Решения :: Статьи :: Сайт М. Дроздова :: Файловый архив :: Книга по VFP 9 :: Русский Help Online :: OFF-LINE Форум
   Л и с о в о д ы   в с е х   с т р а н,  о б ъ е д и н я й т е с ь !!!  

Список Форумов  :: Игры Разума
   :: Помощь сайту :: 

Re: Поиск ближайшей точки
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата: 04.03.10 11:38:29ОтветитьЦитировать
Караул какой-то... Может я немного упустил перетекание темы в другое русло, но задача решается одим простым запросом:
  
  clear      
            
  rand(-1)      
  create cursor points (PointId i, coordX i, coordY i, ds b)      
  for lnRow=1 to 10^5  
  	insert into points values (lnRow, rnd(), rnd(), 0)      
  endfor      
  replace all ds with sqrt(coordX^2+coordY^2)      
    
  myX = -10  
  myY = 1  
    
  SELECT PointId, ABS(coordX - myX) + ABS(CoordY - myY) sum1, ds  FROM points ORDER BY 2  
    
  FUNCTION rnd      
  RETURN 2000000*(rand()-.5)

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


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.




Исправлено: Влад Колосов, 04.03.10 11:38
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата: 04.03.10 11:50:03ОтветитьЦитировать
Э! При равных суммах длин некорректно вычисляет...


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.




Исправлено: Влад Колосов, 04.03.10 11:50
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
medstrax

Сообщений: 4474
Дата: 04.03.10 17:54:31ОтветитьЦитировать
Помимо упомянутой книги по выч. геометрии(весьма старой) рекомендую ознакомиться с en.wikipedia.org, там описана задача в более общем варианте
и есть ссылки на различные способы решения.
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
leonid

Сообщений: 2594
Откуда: Рига
Дата: 04.03.10 21:29:16ОтветитьЦитировать
medstrax
Помимо упомянутой книги по выч. геометрии(весьма старой) рекомендую ознакомиться с en.wikipedia.org, там описана задача в более общем варианте
и есть ссылки на различные способы решения.

Теория очень хорошая вещь. И приведенные в википедии ссылки вне всякого сомнения крайне поучительны. В первую очередь это, конечно, касается Кнута. Его я настоятельно рекомендую почитать (хотя бы попробовать - он довольно сложный) всем, кто хочет повысить свой уровень, как програмист. Но я все-таки хочу подчеркнуть одну особенность данной задачи, которая накладывает на применение к ней теории весьма большую специфику. Дело в том, что решать ее надо на фоксе, а фокс - интерпретатор. Давным давно, еще на Basic-е, столкнулся с тем, что некоторые теоретически оптимальные алгоритмы дают неважную скорость, в то время, как более грубые, но с использованием встроенных функций, работают значительно лучше. Ясно дело, встроенные функции прогоняют циклы на ассемблере, а это намного быстрее, чем самый оптимальный цикл, прогнанный интерпретатором. Если посмотреть эту ветку сначала, видно что главный вопрос был в том, как пристроить к данной задаче Рашмор, поскольку это то, что обычно дает в фоксе максимальное приращение скорости. Именно из-за Рашмора появились два квадрата с отношением сторон sqrt(2). Это связано с тем, что Рашмор позволяет оптимизировать проверку наличия точки в произвольном квадрате, и в то же время не может оптимизировать проверку наличия точки в произвольном круге. Уверен, что подобных квадратов нет ни в одной из приведенных в википедии ссылок. Хотя в остальном полученный метод похож на какой-то из методов из википедиевских ссылок (извиняюсь, не очень подробно посмотрел). Кстати, метод хеширования из приведенных ссылок может очень хорошо показать себя в случае, если точки распределены не равномерно, а скоплениями.
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата: 05.03.10 08:28:16ОтветитьЦитировать
Любопытно, что вычисление квадратного корня не приводит к замедлению выполнения, т.е.

SELECT top 1 PointId, ABS(coordX - myX) + ABS(CoordY - myY) sum1, ds FROM points ORDER BY 2
и
SELECT top 1 PointId, SQRT((coordX - myX)^2 + (CoordY - myY)^2) test_value, ds FROM points ORDER BY 2
отрабатывают одинаково. Я брал 10^5 значение, приблизительно 0.6 секунды время выполнения.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 05.03.10 11:08:26ОтветитьЦитировать
Любопытная задача однако.
Применений в принципе много может быть. Когда-то вроде тоже натыкался на необходимость выборки одновременно по двум полям, чего не позволяет например команда LOOKUP(). А казалось бы, ну что им стоило добавить туда возможность такой выборки.

Тоже пришла мысль - выбирать в несколько этапов:

1) пошагово расширяем квадрат поиска до первого попадания в него точки,
2) поскольку при этом первой попасть туда может и более далекая точка - войдя через диагональ квадрата, и не попасть более близкая, но только-только приблизившаяся к ребру - среди нескольких точек, уже ограниченных этим кругом с радиусом, равным расстоянию до найденной точки, ищем минимум расстояния,
3) позиционируем запись в таблице на найденные координаты - получаем номер точки.

Алгоритм вроде верный. Но над реализацией особо не стал размышлять - попытался сделать "стандартными" командами. И как оказалось зря. Если на маленьких таблицах все работает отлично, то на огромных - получаются явные тормоза. Ну правда не знаю как учесть тот фактор, что у меня на компе даже само создание таких таблиц занимает минуты, видимо из-за ограничений по памяти и процессору. Не у всех же под рукой двухъядерные и прочие. Люди и на селеронах-1.8 с 512 мб сидят.

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


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 05.03.10 11:10:58ОтветитьЦитировать
Да, собственно вот и сама эта программка вселенной.

  
  CLOSE TABLES  
  PUBLIC lnPointX, lnPointY, lnCount, lnMinRadius, lnMinPointId  
  lnPointX = 310  
  lnPointY = 250  
  lnCount = 500  
  CLEAR  
  ?'немного подождите, создается таблица '+LTRIM(STR(lnCount))+' точек...'  
  CREATE CURSOR points (PoindId i, coordX i, coordY i)    
  FOR i=1 TO lnCount  
  	INSERT INTO points VALUES (i, INT(lnCount*RAND()),INT(lnCount*RAND()))    
  ENDFOR  
    
 * с символьными переменными типа C и их функциями фокс вроде работает быстрее,   
 * чем с числами (N) поэтому и решил попробовать использовать именно их:  
  INDEX ON STR(coordX)+STR(coordY) TAG temp  
  SET INDEX TO  
 * но похоже индексация в с этими командами вообще не сильно ускоряет поиск  
  CLEAR  
    
  lnStart = SECONDS()    
    
 *  
 * собственно сам поиск (к сожалению эти команды при выборке из больших таблиц тормозят)  
 *  
  d = 0  
  DO WHILE .T.  
 	* грубый поиск в пошагово расширяемом от главной точки квадрате:  
  	LOCATE FOR BETWEEN(STR(coordX),STR(lnPointX-d),STR(lnPointX+d)) ;  
  					AND BETWEEN(STR(coordY),STR(lnPointY-d),STR(lnPointY+d))  
  	IF FOUND()  
 		* первая найденная точка:  
  		lnRadius2 = (coordX-lnPointX)*(coordX-lnPointX)+(coordY-lnPointY)*(coordY-lnPointY)  
 		* ограничение области окружностью для более уточненного поиска:  
 		* (кажется функция возведения в степень работает медленнее, чем просто умножение)  
  		SET FILTER TO (coordX-lnPointX)*(coordX-lnPointX)+(coordY-lnPointY)*(coordY-lnPointY) = lnRadius2   
 		* вычисление минимума внутри круга:  
  		CALCULATE MIN((coordX-lnPointX)*(coordX-lnPointX)+(coordY-lnPointY)*(coordY-lnPointY)) TO lnMinRadius2  
 		* позиционирование записи:  
  		LOCATE FOR (coordX-lnPointX)*(coordX-lnPointX)+(coordY-lnPointY)*(coordY-lnPointY) = lnMinRadius2  
  		EXIT  
  	ENDIF  
  	d = d + 1  
  ENDDO  
 *  
 * конец поиска  
 *  
    
  lnStop = SECONDS() - m.lnStart   
    
 * строка вывода:  
  lnMinPointId = PoindId  
  lnMinRadius=SQRT(lnMinRadius2)  
  cTextOut = 'найдено за: ' + RTRIM(STR(lnStop,12,9),0,'0') + ;  
  ' сек.,   мин.расстояние: ' + LTRIM(STR(lnMinRadius)) + ;  
  ', точка: '+ LTRIM(STR(PoindId))  
    
 * но хотелось понаблюдать и как все будет выглядеть визуально, что при слишком   
 * уж большом количестве на такой небольшой форме показалось явно неподходящим:  
    
  IF lnCount > 500  
  	CLEAR  
  	? cTextOut   
  	RETURN  
  ENDIF   
    
 * ELSE:  
 * а вот рисовалка для отображения точек мне однако понравилась  
 * чем-то напоминает солнце и звезды во вселеной   
 *  
  PUBLIC o1  
  o1 = CREATEOBJECT("frm1")    
  o1.Caption = cTextOut  
  o1.Show()  
    
  DEFINE CLASS frm1 as form  
  	KeyPreview = .T.  
  	AutoCenter = .T.  
  	Height=lnCount   
  	Width=lnCount   
  	BackColor = RGB(0,0,0)  
    
  	ADD OBJECT lbl AS label WITH ;  
  		Caption = '', ;  
  		ForeColor = RGB(255,255,255), ;  
  		BackStyle = 0, ;  
  		Top = 0, ;  
  		Left = lnCount-180, ;  
  		Height = 30, ;  
  		Width = 250  
    
  	PROCEDURE Init  
  	LOCAL lni  
  		WITH thisform  
 		* круг обнаружения - серым:  
  		.ForeColor = RGB(128,128,128)  
  		.Circle(lnMinRadius+2,lnPointX,lnPointY)  
 		* если не отключить фильтр - будет лишь круг с одной/несколькоми точками  
  		SET FILTER TO  
 		* все точки на форме - белым:  
  		.ForeColor = RGB(255,255,255)  
  		lni = 1  
  		SCAN  
  			.PSet(coordX,coordY)  
  			lni = lni + 1  
  		ENDSCAN  
 		* основную точку - в желтый:  
  		.ForeColor = RGB(255,255,0)  
  		.PSet(lnPointX,lnPointY)  
 		* ближайшую к ней - в голубой:  
  		LOCATE FOR PoindId = lnMinPointId  
  		.ForeColor = RGB(0,255,255)  
  		.PSet(coordX, coordY)  
  		ENDWITH  
  	ENDPROC  
    
 	* для проверки можно смотреть мышкой расстояния до звезд  
 	* но т.к. каждая "точка" на самом деле = 4 точкам, и ее координаты определяются  
 	* левым верхним углом этого квадратика, то расстояние получается показать +/- 1  
  	PROCEDURE MouseMove  
  	LPARAMETERS nButton, nShift, nXCoord, nYCoord  
  		WITH thisform  
  		.lbl.Caption = 'расстояние до солнца:  ' + ;  
  				LTRIM(STR(SQRT((nXCoord-lnPointX)^2+(nYCoord-lnPointY)^2)))  
  		IF INLIST(.Point(nXCoord, nYCoord), RGB(255,255,255), RGB(0,255,255), RGB(255,255,128))  
  			LOCATE FOR BETWEEN(coordX, nXCoord-1, nXCoord+1) AND BETWEEN(coordY, nYCoord-1, nYCoord+1)  
  			.lbl.Caption = .lbl.Caption + CHR(13) + 'точка: '+ LTRIM(STR(PoindId))  
  		ENDIF   
  		ENDWITH  
  	ENDPROC  
    
 	* ну это - чтобы все убиралось "легким движением руки"  
  	PROCEDURE KeyPress  
  	LPARAMETERS nKeyCode, nShiftAltCtrl  
  		thisform.Release()  
  	ENDPROC  
    
  ENDDEFINE


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 05.03.10 11:21:40ОтветитьЦитировать
Интересно бывает наблюдать за различными ситуациями распределения - если закрывать окошко любой клавишей, а запускать, например расположив мышку над кнопкой run.
Получается как бы наблюдать вселенную со всеми удобствами, работая всего лишь легкими движениями двух пальцев.



------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата: 05.03.10 11:41:37ОтветитьЦитировать
Влад Колосов
Я брал 10^5 значение, приблизительно 0.6 секунды время выполнения.
Проблема была именно в скорости.
Тут простой селект отстаёт ~ в 1000 раз.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
pasha_usue

Сообщений: 3043
Откуда: Е-бург
Дата: 05.03.10 12:27:01ОтветитьЦитировать
Crispy
Интересно бывает наблюдать за различными ситуациями распределения - если закрывать окошко любой клавишей, а запускать, например расположив мышку над кнопкой run.
Получается как бы наблюдать вселенную со всеми удобствами, работая всего лишь легкими движениями двух пальцев.
Ctrl+E рулит
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата: 05.03.10 14:52:47ОтветитьЦитировать
И какое же решение приято к эксплуатации?


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
sphinx

Сообщений: 22883
Откуда: Каменск-Уральски
Дата: 05.03.10 19:58:56ОтветитьЦитировать
Влад Колосов
И какое же решение приято к эксплуатации?

Да, присоединяюсь к вопросу. Какое именно решение устроило? (особо не вникал в проблему, но слежу за темой, ибо интересно)


------------------
"Вы поступили правильно, мой друг, но, боюсь, совершили ошибку"..."(с)
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Igor Korolyov

Сообщений: 32376
Дата: 05.03.10 20:40:19ОтветитьЦитировать
Влад, всё собственно говоря крутилось вокруг того как избежать полного перебора, при этом наиболее простым и быстрым способом, а ты снова здорово
Если бы речь шла про C/C++ или там Oracle - то очевидно что решение было бы наверное другим, но мы то про фокс толкуем...
Вариант с ABS заведомо некорректный, о чём тут уже тут писали - т.к. расстояние от нуля до точки (2, 2) реально меньше (примерно 2.83) чем расстояние до точки (0,3) которое даёт ровно 3 - тогда как по твоему выходит что вторая ближе. В любом случае, вопрос будет прежде всего в том чтобы как-то подсунуть индекс, чтобы отбор НЕ проходил по всем точкам - что-то мне сомнительно что вариант с ABS(X-A)+ABS(Y-B) может быть оптимизирован в принципе... А если его "развернуть" чтобы ушёл модуль, то получим... ровно тот-же "квадрат" поиска Он один не позволит найти решение, зато позволит отсеять большую часть точек и потом среди оставшихся искать полным перебором - используя квадраты/корни.
Переход к полярной системе координат так-же ничего не даёт, как ты не выбирай начальную точку - а расстояние по полярной системе, или перевод исходной системы в новую, где начало совпадает с искомой точкой всё одно потребует обработки всей таблицы, и никак это не оптимизировать...
Вот алгоритмы предварительного разбиения всего множества на области и последующее оперирование именно в рамках одного (ну или нескольких ближайших) подмножества - это да - это разумно и хорошо - но IMHO чересчур уж сложно в реализации, да и не факт что даст выигрыш для любых распределений, скажем для равномерного (ну получится тупо мозаика из равномерно распределённых равноразмерных пятиугольников, или скажем квадратов - спрашивается на кой было стараться, если тот-же эффект дают банальные 2 индекса по X и Y плюс описанный выше механизм поиска). Но для "специфической" задачи (или скажем "особенности распределения точек") такое решение может оказаться более чем уместным - это без сомнений.


------------------
WBR, Igor
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
medstrax

Сообщений: 4474
Дата: 06.03.10 20:53:11ОтветитьЦитировать
Кто нибудь пробовал реализовать на фоксе упомянутые алгоритмы? При всем уважении к leonid'у
хотелось бы увидеть конкретные цифры на различных массивах точек. На просто рандомном массиве
и на каких-то конкретно подобранных вариантах. К примеру все множество точек лежит на одной прямой. Тут диаграммы Вороного явно не рулят, в другие алгосы не особо пока вник.
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата: 09.03.10 08:27:44ОтветитьЦитировать
Влад Колосов
И какое же решение приято к эксплуатации?
Слегка облегчённый вариант Игоря.
Время поиска в 10^6 ~ 0.003 секунды против 1.5 секунд постого скана, что вполне устраивает.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 26.03.10 07:38:00ОтветитьЦитировать
Goodwin
Влад Колосов
И какое же решение приято к эксплуатации?
Слегка облегчённый вариант Игоря.
Время поиска в 10^6 ~ 0.003 секунды против 1.5 секунд постого скана, что вполне устраивает.

И еще одна идея на днях пришла, но не обобщенно-теоретическая, а чисто для практического использования. Что позволит возможно и еще дополнительно ускорить нахождение нужной точки как минимум на порядок. Возможно и на несколько порядков.
Суть данного улучшения в том, что если по условию допустимо любое предварительное преобразование и обработка таблицы еще до самих вычислений, в том числе и с созданием индекса, то можно значительно намного упростить их. Сведя все по сути к элементарным вещам.
Для чего достаточно лишь завести в таблице дополнительное поле, в которое вычислить заранее расстояние каждой точки (x,y) от нулевой точки. Т.е. нечто вроде SQRT(x^2+y^2). Возможно еще проще (для дальнейших вычислений) будет записать туда не корень, а непосредственно саму эту сумму квадратов координат.
Тогда сам поиск ближайшей точки вместо сложного двумерного поиска, как во всех вышеописанных вариантах, будет сведен всего лишь к поиску по одной переменной. Что при дополнительном индексировании по ней можно уже будет осуществить явно намного более проще. И естественно во сколько-то раз быстрее.


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)




Исправлено: Crispy, 26.03.10 07:38
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Goodwin
Автор

Сообщений: 3539
Откуда: Омск
Дата: 26.03.10 08:08:15ОтветитьЦитировать
Этот вариант предлагал PaulWist.
На второй странице есть реализация.


------------------
Что мы знаем о лисе?
Ничего. И то не все.
(С)Б. Заходер
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 26.03.10 09:20:23ОтветитьЦитировать
Goodwin
Этот вариант предлагал PaulWist.
На второй странице есть реализация.
Пересмотрел внимательно несколько раз, но так и не нашел.
Возможно мы о разных вещах говорим?
Я имел в виду добавление нового поля в таблицу, равного сумме квадратов x и y, чтобы осуществлять затем поиск не по вычисляемому выражению функции x,y, а по этому уже заранее вычисленному полю.
Т.е. задача сводится всего лишь к поиску ближайшего значения по одному-единственному индексированному полю. Всего лишь элементарный LOCATE или SEEK! Ну в смысле чуть посложнее, но всего лишь поиск ближайшего единственного числа к числу "расстояния точки"=x^2+y^2.

Насколько я понимаю во всех приводившихся выше вариантах идет вычисление как раз по двум переменным x и y, используя понятие точки. Здесь же само понятие точки можно даже и не использовать - используется всего лишь число "расстояние точки до 0".
Еще и еще смотрю и упорно не вижу, где PaulWist (или кто-либо еще) говорит об единственном поле. Везде вроде обсуждают поиск в квадрате и т.п.
Или я что-то все-таки пропустил?

Как бы вместо использования плоскости и двух координат - переходим к вычислению на прямой.


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)




Исправлено: Crispy, 26.03.10 09:23
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Mitchman
[Модератор]

Сообщений: 9482
Откуда: Николаев
Дата: 26.03.10 09:45:00ОтветитьЦитировать
не годится такое решение - или с очень ограниченными условиями бо для огромного числа разных XY будет одинаковым сумма их квадратов

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


------------------
а будни - это попросту антракт
Ratings: 0 negative/0 positive

Re: Поиск ближайшей точки
Crispy

Сообщений: 13751
Дата: 26.03.10 10:27:49ОтветитьЦитировать
А блин. Точно! Нужно же еще и направление - вектор же.



------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)




Исправлено: Crispy, 26.03.10 10:32
Ratings: 0 negative/0 positive



Извините, только зарегистрированные пользователи могут писать в этом форуме.

On-line: 79 finskl Божья_коровка  and Guests: 77


© 2000-2019 Fox Club 
Яндекс.Метрика