python – 加快选择3个节点的集合,这些节点形成具有给定最小和最大边长的三角形

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 加快选择3个节点的集合,这些节点形成具有给定最小和最大边长的三角形，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4206字，纯文字阅读大概需要7分钟。

内容图文

我有一个大约60个点的列表,我正在从中生成所有可能的大小为3的组合.我正在尝试确定3个点中是否有任何一个在某些距离参数范围内 – 也就是说,每个点都不太接近其他,并且彼此之间并不太远(比如,没有点可以小于10个单位到下一个最近点,并且没有点可以从最远点超过100个单位).

我有代码在这里这样做：

def setPalmCombinations(self):
    # Testing confirms that the range of distances is about 5 - 10 for
    # minimum distance between points, and anywhere from 150 - 200 for max
    # distance between points. 10 and 100 should be reasonable cutoffs.
    minDistance = 10
    maxDistance = 100
    startTime = time.time()
    iter = itertools.combinations(self.handContour, 3)
    def distanceCheck(points):
        A = points[0][0]
        B = points[1][0]
        C = points[2][0]
        AB = np.linalg.norm(A - B)
        if not(minDistance < AB < maxDistance): return None
        BC = np.linalg.norm(B - C)
        if not(minDistance < BC < maxDistance): return None
        CA = np.linalg.norm(C - A)
        if not(minDistance < CA < maxDistance): return None
        return np.array([A, B, C])
    a = [distanceCheck(i) for i in iter]
    print time.time() - startTime

但是,仅生成此可能组合列表大约需要0.4到0.5秒,这太慢了.有没有办法可以优化这个计算(或者从根本上重做算法,这样它不仅仅是一个强力搜索),这样我就可以把时间缩短到实时计算(即每秒30次).

我正在考虑可能生成每个点之间的距离列表,对其进行排序,以及寻找距离截止范围中心的距离的点,但我认为这实际上可能比我现在所做的要慢.

我也试图找出一些更智能的算法,因为这些点最初按照它们如何定义轮廓的顺序存储 – 我应该能够在组合时消除列表中每个点之前和之后的某些点…但是,当我尝试使用Python的默认for循环生成组合时,它最终比简单地使用itertools并生成所有内容更慢.

任何建议表示赞赏.

谢谢！

解决方法:

我首先计算所有点之间的成对距离,过滤掉那些满足你的规格(dist_min和dist_max),然后检查三个这样的节点的组合是否仍然符合标准(因为我只是成对检查 – 一次,因为速度).

import itertools
import numpy as np
from scipy.spatial.distance import pdist, squareform

points = np.random.rand(100,2)  # could be nodes in 3 dimensions too, but you specify a handpalm, so I'm guessing your contour is merely 2D

def palm_combinations(points, dist_min=.0, dist_max=.05):
    dists = pdist(points)
    # This matrix lists the distance between each pair of nodes 
    # (represented by their column and row index, so that the mat[i,j] 
    # represents the distance between points[i,:], points[j,:])
    mat = squareform(dists)  

    mask = (mat > dist_min) & (mat < dist_max)

    two_good_legs = {}  # store all combinations of point indices where "two legs" of the triangles have a distance that matches the spec.
    myinds = []
    for rowind, row in enumerate(mask):
        relevant = row[rowind+1:]  # distance to a point itself is always zero, hence exclude from list
        inds = np.where(relevant)[0] + (rowind+1)
        myinds.append(inds)
        two_good_legs[rowind] = list(itertools.combinations(inds, 2))

    triangles = []
    # The only thing left to do now is to check if the third leg's norm is also within spec.
    for k,v in two_good_legs.items():
        for tup in v:
            if tup[1] in myinds[tup[0]]:
                triangles.append((k, tup[0], tup[1]))
    return triangles

三角形将列出满足您的规格的点内的所有索引.如果你想回到实际坐标,只需得到点[三角形,：].
你可以通过以下方式想象这一切：

import maptlotlib.pyplot as plt
plt.triplot(points[:,0], points[:,1], triangles)
plt.plot(points[:,0], points[:,1], 'ko ')

您的实现之间的时间差异(修改为排除未知[0]索引,请参阅我的评论)显示：

In [12]: %timeit  my_implementation(points, .1, .15)
1 loops, best of 3: 1.58 ms per loop

In [13]: %timeit your_implementation(points, .1, .15)
1 loops, best of 3: 2.32 s per loop

由于点的形状为(100,2),因此我的机器速度增加了1470倍.

你可以稍微提高速度,如果你摆脱了方形的调用,这是根据探查器的瓶颈,并不是绝对必要但它使代码更具可读性(“可读性计数.”cfr.禅宗Python的作者：蒂姆彼得斯).为此,您将进行以下更改：

def palm_combinations(points, dist_min=.0, dist_max=.05):
    dists = pdist(points)
    mask = (dists > dist_min) & (dists < dist_max)
    two_good_legs, myinds, triangles = {}, [], []
    s = points.shape[0]
    ind_u1, ind_un = 0, s - 1
    for rowind in xrange(s-1):
        relevant = mask[ind_u1:ind_un]
        ind_u1 = ind_un
        ind_un += s - 1*(rowind+2)
        inds = np.where(relevant)[0] + (rowind+1)
        myinds.append(inds)
        two_good_legs[rowind] = list(itertools.combinations(inds, 2))
    for k,v in two_good_legs.items():
        for tup in v:
            if tup[1] in myinds[tup[0]]:
                triangles.append((k, tup[0], tup[1]))
    return triangles

但是,对于小型数据集,速度增益不会明显.

内容总结

以上是互联网集市为您收集整理的python – 加快选择3个节点的集合,这些节点形成具有给定最小和最大边长的三角形全部内容，希望文章能够帮你解决python – 加快选择3个节点的集合,这些节点形成具有给定最小和最大边长的三角形所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端