Эффективный способ найти расстояние между двумя 3D точками

Мой пример:

HEADERS = {"User-Agent" : "Mozilla/5.0 (Windows; U; Windows NT 5.1; ru; rv:1.9.1.5) Gecko/20091102 Firefox/3.5.5",
       "Accept" : "text/html,application/xhtml+xml,application/xml;q=0.9,*/*;q=0.8",
       "Accept-Language" : "ru,en-us;q=0.7,en;q=0.3",
       "Accept-Charset" : "windows-1251,utf-8;q=0.7,*;q=0.7",
       "Accept-Encoding" : "identity, *;q=0",
       "Connection" : "Keep-Alive"}
PROXY=None
timeout=60


def parse_manuf_page_about(page_str_about):
slovar={}
global timeout
socket.setdefaulttimeout(timeout)
if PROXY is not None:
        proxy_handler = urllib2.ProxyHandler( { "http": "http://"+PROXY+"/" } )
        opener = urllib2.build_opener(proxy_handler)
        urllib2.install_opener(opener)
page_request = urllib2.Request(url=page_str_about, headers=HEADERS)
try:
    #print "Page reading ... %s" %page_str
    page_zapr = urllib2.urlopen(url=page_request)
    page=page_zapr.read()
except Exception ,error:
    print str(error)
    res=False
    return res,slovar
soup = BeautifulSoup(page)
select_pod=soup.findAll('div', {"class":"win aboutUs"})

promeg= select_pod[0].findAll("p")[0]
zerro_br= promeg.findAll(text=True)
Company_Info=" ".join(zerro_br).strip(" \t\n")
select =soup.findAll('div', {"class":"win"})
cells_tabl= select[0].findAll("tr")

for yach in cells_tabl:
    text_zag=yach.findAll("th")
    for zn_yach in text_zag:
        if len(zn_yach)>0:
            txt_zn_yach="".join(zn_yach.findAll(text=True)).strip(" \t\n")
        else:
            txt_zn_yach= zn_yach.contents[0].strip(" \t\n")
            #print txt_zn_yach
    text_znach_td=yach.findAll("td")
    for zn_yach_td in text_znach_td:
        if len(zn_yach_td)>0:
            txt_zn_yach_td="".join(zn_yach_td.findAll(text=True)).strip(" \t\n")
        else:
            txt_zn_yach_td= zn_yach.contents[0].strip(" \t\n")
            #print txt_zn_yach_td
    # Делаем замены неугодных символов / Replase browsers char
    if "&nbsp" in txt_zn_yach_td:
        while txt_zn_yach_td.find("nbsp;")>0:
            pos_gavna=txt_zn_yach_td.find(" ")
            txt_zn_yach_td=txt_zn_yach_td[:pos_gavna]+txt_zn_yach_td[pos_gavna+6:]
    if "&quot" in txt_zn_yach_td:
        while txt_zn_yach_td.find("quot;")>0:
            pos_gavna=txt_zn_yach_td.find(""")
            txt_zn_yach_td=txt_zn_yach_td[:pos_gavna]+'"'+txt_zn_yach_td[pos_gavna+6:]
    if "&" in txt_zn_yach_td:
        while txt_zn_yach_td.find("&")>0:
            pos_gavna=txt_zn_yach_td.find("&")
            txt_zn_yach_td=txt_zn_yach_td[:pos_gavna]+'&'+txt_zn_yach_td[pos_gavna+6:]
    slovar[str(txt_zn_yach)]=txt_zn_yach_td
    slovar["Company_Info"]=Company_Info
# разбираем нижнюю таблицу с контактом и вытаскиваем оттуда имя контакта | get name contacts
select_contact=soup.findAll('a', {"class":"member-name"})
for contact_person in select_contact:
    slovar["Contact_Person"]= contact_person.contents[0]
# получаем статус голд партнера по наличию таблички в левом верхнем углу | get Gold status
select_gold_part=soup.findAll('a', {"class":"memberLogo"})
if len(select_gold_part)==0:
    slovar["Gold member"]="N"
else:
    slovar["Gold member"]="Y"
res=True
return res,slovar

Этот код анализирует одну страницу производства на Alibaba.com. Вы можете увидеть его страницу - http://xmxinhuafeng.en.alibaba.com/aboutus.html

Посмотрите на Croquet. Может, их технологии - это то, чего ты хочешь.

http://en.wikipedia.org/wiki/Croquet_project

Обратите внимание, что при использовании sqrt (dx * dx + dy * dy + dz * dz) сумма квадратов может перетекать. ипот (dx, dy) вычисляет расстояние непосредственно без возможности переполнения. Я не уверен в быстром 3d эквиваленте, но ипот (dx, ипот (dy, dz)) выполняет работу и не перетекает.

Q2 ответ: x1 = x2 и y1 = y2 и z1 = z2, если точки совпадают.

Принимая во внимание, что вы храните точки как float / double, вам может потребоваться провести сравнение с помощью некоторого epsilon.

Эта статья может показаться вам интересной:

http://www.codemaestro.com/reviews/9

Она описывает как вычисляли квадратный корень в движке Quake 3, утверждая, что на некоторых процессорах он работал в 4 раза быстрее, чем функция sqrt (). Не уверен, повысит ли это производительность C ++ в настоящее время - но все же интересно прочитать

Что касается вопроса 1, снижение производительности - это вычисление самого квадратного корня. Формула для расчета расстояния с использованием квадратного корня из парных разностей координат такова.

Я настоятельно рекомендую прочитать эту A-M-A-Z-I-N-G реализацию квадратного корня Джона Кармака из программного обеспечения ID, которое он использовал в своем движке в Quake III. Это просто ВОЛШЕБНО.

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

Есть ли лучший способ, если я просто хочу определить, являются ли P и Q на самом деле одними и теми же точками?

Тогда просто сравните координаты напрямую!

bool areEqual(const Point& p1, const Point& p2) {
     return fabs(p1.x - p2.x) < EPSILON &&
            fabs(p1.y - p2.y) < EPSILON &&
            fabs(p1.z - p2.z) < EPSILON;
}

Нет, более эффективного способа вычисления расст. Любое лечение с особыми случаями p.x == q.x и т. Д. Будет в среднем медленнее.

Да, самый быстрый способ узнать, совпадают ли точки p и q, - это просто сравнить x, y, z. Поскольку они являются плавающими, вы не должны проверять ==, но должны допускать некоторую конечную небольшую разницу, которую вы определяете.

Вы можете попробовать использовать расширения SSE. Например, вы можете инициализировать два вектора A(x1,y1,z1) и B(x2,y2,z2):

_m128 A = _mm_set_ps(x1, y1, z1, 0.0f)
_m128 B = _mm_set_ps(x2, y2, z2, 0.0f)

Затем вычислить diff, используя _mm_sub_ps:

__m128 Diff = _mm_sub_ps(A, B)

Затем вычислить sqr от diff:

__m128 Sqr = __mm_mul_ps(Diff, Diff)

И наконец:

__m128 Sum = add_horizontal(Sqr)
__m128 Res = _mm_sqrt_ss(Sum)

Res[0] будет заполнен вашим ответом.

P.S. add_horizontal - место для оптимизации

Нет лучшего способа.

Реализация квадратный_корень может быть оптимизирована.

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

Существуют более быстрые способы получения приблизительного расстояния, но ничего встроенного в стандартные библиотеки. Посмотрите эту статью на FlipCode, в которой рассматривается метод быстрого получения расстояний в 2D. По сути, он сворачивает функцию sqrt в составную линейную функцию, которая может быть быстро вычислена, но не является на 100% точной. Однако на современных машинах в наши дни fpmath работает довольно быстро, так что не оптимизируйте слишком рано, вы можете обнаружить, что вам вполне хватает вашего простого подхода.