在 Sympy 中迭代相交线段......有更好的方法吗？

Question

好的。我有构成多边形边界的点。我想 (a) 使用 Sympy 的几何模块来确定，从任何一对点之间的所有可能的线段，哪些线段不穿过周边。此结果将是 "edges" 允许在 (b) Networkx 中的 shortest_distance 分析中使用。我的最终目标是通过许多形状重复这个过程，但我在这个例子中只对 1 个形状的坐标进行了硬编码。

import numpy
import networkx as nx
from sympy import geometry
from itertools import combinations
from matplotlib import pyplot as plot
arr_bou = numpy.array([[-542.62545014,  961.34455209],
   [-544.45425379,  961.34455209],
   [-544.45425379,  962.25895392],
   [-547.19745928,  962.25895392],
   [-547.19745928,  963.17335575],
   [-549.02626294,  963.17335575],
   [-549.02626294,  964.08775758],
   [-550.85506659,  964.08775758],
   [-550.85506659,  961.34455209],
   [-552.68387025,  961.34455209],
   [-552.68387025,  962.25895392],
   [-553.59827208,  962.25895392],
   [-553.59827208,  965.91656123],
   [-552.68387025,  965.91656123],
   [-552.68387025,  967.7453649 ],
   [-551.76946842,  967.7453649 ],
   [-551.76946842,  968.65976672],
   [-550.85506659,  968.65976672],
   [-550.85506659,  967.7453649 ],
   [-548.11186111,  967.7453649 ],
   [-548.11186111,  965.91656123],
   [-547.19745928,  965.91656123],
   [-547.19745928,  964.08775758],
   [-546.28305745,  964.08775758],
   [-546.28305745,  965.00215941],
   [-543.53985197,  965.00215941],
   [-543.53985197,  963.17335575],
   [-542.62545014,  963.17335575],
   [-542.62545014,  964.08775758],
   [-540.79664648,  964.08775758],
   [-540.79664648,  963.17335575],
   [-539.88224465,  963.17335575],
   [-539.88224465,  962.25895392],
   [-542.62545014,  962.25895392],
   [-542.62545014,  961.34455209]])

boundXY = []
for i in arr_bou:
    boundXY.append((i[0],i[1]))

points     = [geometry.Point(i) for i in boundXY]
poly       = geometry.Polygon(*points) # use the * first to unpack the points (necessary to avoid errors)


G          = nx.Graph()
positions  = {}                                  # build a dictionary
for i in xrange(len(boundXY)):                   # that contains coordinates
    positions[i] = boundXY[i]                    # of each node on the graph's perimeter
G.add_path(positions.keys())# add nodes to graph w/ boundary edges
G.add_path([min(G.nodes()),max(G.nodes())])    combos_o   = list(combinations(positions.keys(),2))
combos     = [i for i in combos_o if i not in G.edges()]

keepcombos = []
for combo in combos:
    pt1 = positions[combo[0]]
    pt2 = positions[combo[1]]
    line = geometry.Polygon(pt1,pt2)
    # there are 4 polygon sides that do not count as intersections
    # because 2 sides will intersect a point on each end
    test = True
    for side in poly.sides:
        if side.p1 != geometry.Point(pt1) and side.p1 != geometry.Point(pt2):
            if side.p2 != geometry.Point(pt1) and side.p2 != geometry.Point(pt2):
                if geometry.intersection(line,side):
                    test = False
                    break
                else:
                    try:
                        if poly.encloses(line.midpoint):
                            pass
                        else:
                            test = False
                            break
                    except NotImplementedError:
                        pass
    if test == True:
        keepcombos.append(combo)
G.add_edges_from(keepcombos)

我已经将它用于小多边形（14 个顶点），但这需要永远，即使只有 35 个顶点，其他多边形仍然会比这更大。

是否有更有效的方法来查找多边形内的所有节点对？

谢谢！！

Answer 1

如果凸包是定义包含所有其他凸多边形的点集

>>> coords = [[-542.62545014,  961.34455209],
...    [-544.45425379,  961.34455209],
...    [-544.45425379,  962.25895392],
...    [-547.19745928,  962.25895392],

...    [-542.62545014,  962.25895392],
...    [-542.62545014,  961.34455209]]
>>> from sympy import *
>>> pts = [Point(*i) for i in coords]
>>> h = convex_hull(*pts)

那么你只对不在周界上的所有点感兴趣吗？知道这些点后，您是否只想生成这些点的所有成对组合？

inside = [p for p in pts if p not in h.vertices]
from sympy.utilities.iterables import combinations
pairs = combinations(inside, 2)

查看 https://www.desmos.com/calculator/up4k2qkxy9 我发现有几个点似乎落在边缘上，因此也许它们不应包含在 "inside" 点中。但希望您能理解我的回答要点。

Answer 2

我找到了一个解决方案，该解决方案将处理速度提高了大约 13 倍（对于具有 35 个点的多边形（如上面列出的数据），问题代码中的旧方法花了大约 4 小时才能找到其中的所有线段多边形。这个新方法用了 18 分钟。）

上面我遍历了点，并且在每次迭代中分别查看每个边界 ("side") 以查看线条是否相交。我将其更改为将线与整个多边形相交。如果它在里面或在边缘上，它相交的地方应该只有2个点，所以如果相交的长度>2，我把组合扔掉

for combo in combos:
    pt1  = geometry.Point(positions[combo[0]],evaluate=False)
    pt2  = geometry.Point(positions[combo[1]],evaluate=False)
    line = geometry.Polygon(pt1,pt2)
    try:
        if poly.encloses(line.midpoint):
            pass
        else:
            continue
    except NotImplementedError:
        continue
    intersect = geometry.intersection(line,poly)
    if len(intersect)>2:
        continue
    keepcombos.append(combo)

此列表 "keepcombos" 现在包含我希望包含在 Dijkstra 路径分析中的所有行（或 networkx "edges"）

在 Sympy 中迭代相交线段......有更好的方法吗？

iteratively intersecting line segments in Sympy... is there a better way?

python

geometry

networkx

sympy