Самая близкая точка к данной точке
Вероятно, легче: используйте urllib или urllib2.
>>> import urllib
>>> f = urllib.urlopen('http://google.com')
>>> f.info().gettype()
'text/html'
f.info () является подобным словарю объектом, таким образом, можно сделать f.info () ['тип контента'], и т.д.
http://docs.python.org/library/urllib.html
http://docs.python.org/library/urllib2.html
http://docs.python.org/library/httplib.html
, документы отмечают, что httplib обычно не используется непосредственно.
8 ответов
Не забывайте, что вам не нужно возиться с квадратным корнем.
Если вы просто хотите найти ближайший (а не фактическое расстояние), просто используйте dx ^ 2 + dy ^ 2 , который даст вам квадрат расстояния до каждого элемента, что не менее полезно.
Если у вас нет структуры данных, обертывающей этот список пикселей, вам нужно будет просто протестируйте против них всех.
Если у вас есть некоторая гибкость, есть множество хороших способов снизить рабочую нагрузку. Создайте Quadtree или сохраните отсортированный список пикселей (отсортированный по x и отсортированный по y), чтобы быстрее сузить область поиска.
Поместите точки в дерево KD, после этого будет очень быстро найти ближайшего соседа. Подробнее см. в этой статье в Википедии.
Построение диаграмм Вороного является ветвью вычислительной геометрии . Построение триангуляций Делоне включает аналогичные соображения. Вы можете адаптировать один из следующих алгоритмов Делоне для своих нужд.
- Алгоритмы переворота
- Инкрементальные
- Разделяй и властвуй
- Sweepline
Это называется поиском ближайшего соседа. Дональд Кнут назвал это проблемой почты.
Существует ряд решений: линейный поиск, хеширование с учетом местоположения, файлы векторной аппроксимации и разделение пространства.
Поиск в Google должен помочь.
вы пытаетесь построить диаграмму Вороного это можно сделать за O (n log n), используя развертку плоскости
Я должен согласиться с Дж.К. и Эваном в создании диаграммы Вороного . Это разделит пространство на многоугольники. Каждая точка в K будет иметь многоугольник, описывающий все ближайшие к ней точки. Теперь, когда вы получаете запрос точки, вам нужно найти, в каком многоугольнике она лежит. Эта проблема называется Местоположение точки и может быть решена путем построения трапециевидной карты .
jk уже связан с созданием диаграммы Вороного с использованием алгоритма Фортуны , который требует O (n log n) вычислительных шагов и стоит O (n) пространства.
На этом веб-сайте показано, как создать трапециевидную карту и как выполнять запросы к ней. Вы также можете найти некоторые границы там:
Ожидаемое время создания: O (n log n)
Ожидаемая сложность пространства: O (n)
Но, что наиболее важно, ожидаемое время запроса: O (log n). Это (теоретически) лучше, чем O (√n) kD-дерева.
Мой источник (кроме ссылок выше): Вычислительная геометрия: алгоритмы и приложения , главы шестая и седьмая.
Там вы найдете подробную информацию о двух структурах данных (включая подробные доказательства). Версия Google Книги содержит только часть того, что вам нужно, но других ссылок должно быть достаточно для вашей цели. Просто купите книгу, если вас это интересует (это хорошая книга).
Еще один совет: расстояние всегда больше или равно каждой разности координат и всегда меньше или равно их сумме, т.е.
d >= dx, d >= dy, d <= dx + dy.
Это может помочь вам выполнять сортировку более эффективно.
В зависимости от того, насколько плотно этот рисунок заполнен пикселями, вам может быть лучше просто искать за пределами вашего исходного пикселя.
Я запрограммировал что-то подобное для эмуляции графического терминала. В итоге я запрограммировал шаблон поиска в форме прямоугольной спирали, которая вырастает из центральной точки, и позволял ей расти, пока она во что-то не наткнулась. Это было достаточно быстро для этой цели даже на старом процессоре.