Python程序，以检测一维线段相交 [英] Python program to detect intersection of one-dimensional line segments

问题描述

予有四种颜色的＆mdash线段;粉红色，绿色，橙色，红色＆mdash;如在下面的图

I have line segments of four colors—pink, green, orange, red—as in the figure below.

作为一个例子，第一粉段具有开始和结束位置（5258,5422）

As an example, the first pink segment has start and end position (5258,5422).

中的坐标存储在该词典的元组：

The coordinates are stored in this dictionary of tuples:

mycoord = { 'pink'  :[(5258,5422), (5479,5864)],
            'green' :[(5425,5450)],
            'orange':[(5266,5770)],
            'red'   :[(5258,5864)] }

我想要做的是让所有可能的交叉点开始和结束的值作为该图所示：

What I want to do is to get all the possible intersections' start and end values as shown in this figure:

因此​​，所需的答案将是：

Thus, the desired answer would be:

sect1/pink-red        : 5258,5266
sect2/pink-orange-red : 5266,5422
sect3/orange-red      : 5422,5425
sect4/green-orange-red: 5425,5450
sect5/orange-red      : 5450,5479
sect6/pink-orange-red : 5479,5770
sect7/pink-red        : 5770,5864

请注意，我想preserve颜色指示剂的每个交叉点（如的粉红色）。我怎样才能做到这一点与Python？

Note that I want to preserve the color indicator for each intersection (e.g., pink-red). How can I achieve this with Python?

推荐答案

我建议你进行如下操作。

I suggest that you proceed as follows.

• 排序端点，记住每个人的颜色，无论是左（开）或右（关闭）终结点。

• Sort the endpoints, remembering each one's color and whether it's a left (opening) or right (closing) endpoint.

迭代端点，跟踪开放跨距与映射每种颜色与该颜色的开放跨距数的散列。增量当您打开给定的颜色，递减的跨度，当你关闭一个跨度。拆下色当他们的计数为零。对于每一个不同的终端，把所有打开跨度的颜色在该点为一组。

Iterate over the endpoints, keeping track of open spans with a hash that maps each color to the number of open spans of that color. Increment when you open a span of a given color, decrement when you close a span. Remove colors when their count reaches zero. For each distinct endpoint, put the colors of all open spans at that point into a set.

遍历连续对不同的端点。这些构成了跨度你感兴趣的左，右端点。对于每一个端点，你知道，是活跃在该点的颜色。该组颜色是跨度期间活性是href="https://docs.python.org/3/library/stdtypes.html#set" rel="nofollow">设置相交的的

Iterate over consecutive pairs of distinct endpoints. These form the left and right endpoints of the spans that interest you. For each endpoint, you know the colors that are active at that point. The set of colors that are active during the span is the set intersection of the colors that are active at the left end and the colors that are active at the right end.

注意：如果颜色的两个端点之间的交叉点是空的，你已经找到跨度之间的差距，所以你知道，它应该被忽略。您可能还喜欢跳跨度只有一种颜色。下面的实现没有。您可以轻松地将其更改为跳过单色跨度修改这一行：

Note: If the intersection of colors between two endpoints is empty, you've found a gap between spans, so you know that it should be skipped. You might also like to skip spans with only one color. The implementation below does not. You can easily change it to skip single-color spans by modifying this line:

  if len(colors) > 0:

这样记载：

  if len(colors) > 1:

如果你有兴趣看跨度之间的间隙，你可以在阈值更改为 1 或完全消除的条件。

If you're interested in seeing the gaps between spans, you can change the threshold to -1 or remove the condition altogether.

执行：

mycoord = { 'pink'  :[(5258,5422), (5479,5864)],
            'green' :[(5425,5450)],
            'orange':[(5266,5770)],
            'red'   :[(5258,5864)] }

# Sort the endpoints. Remember their color and whether they open or close.
points = []
for color, spans in mycoord.items():
  for open, close in spans:
    points.append((open, 'open', color))
    points.append((close, 'close', color))
points.sort()

# Iterate over the endpoints. Keep track of open spans. Mark intersections.
active_spans = {}
intersections = []
for point, kind, color in points:
  if len(intersections) != 0 and intersections[-1][0] == point:
    intersections[-1][1].add(color)
  else:
    color_set = set([color] + list(active_spans.keys()))
    intersections.append((point, color_set))
  if kind == 'close':
    active_spans[color] -= 1
    if active_spans[color] == 0:
      del active_spans[color]
  else:
    active_spans[color] = active_spans.setdefault(color, 0) + 1

# Iterate over consecutive pairs of unique intersections. Intersect the color sets.
tab_width = sum(map(len, mycoord)) + len(mycoord) 
count = 0
for i in range(1, len(intersections)):
  a, b = intersections[i - 1], intersections[i]
  colors = sorted(a[1] & b[1])
  if len(colors) > 0:
    count += 1
    print('sect{0}/{1:<{2}}: {3},{4}'.format(count, '-'.join(colors), tab_width,
        a[0], b[0]))

结果：

sect1/pink-red              : 5258,5266
sect2/orange-pink-red       : 5266,5422
sect3/orange-red            : 5422,5425
sect4/green-orange-red      : 5425,5450
sect5/orange-red            : 5450,5479
sect6/orange-pink-red       : 5479,5770
sect7/pink-red              : 5770,5864

这篇关于Python程序，以检测一维线段相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！