介绍：
我有一个垂直段S我想在平面上移动（左 --> 右），并找到与水平线的交点。
问题 ：
我遇到的问题如下：如果垂直线段与多条水平线相交，结果我会得到多个交叉点，如下图所示。我想要的是只有 1 个交叉点。或者以另一种方式，多个交叉点，应该组合成一个组。8个交叉点应视为1 个。
作为先验信息，我有每条水平线的起点和终点。我在想我是否可以通过使用扫描算法来移动线，但我真的不知道如何为事件建模
目标是得到如下结果，如下图所示：
垂直和水平线段相交（线扫描）
计算科学
算法
C++
计算几何
2021-12-11 20:32:26
1个回答
我把这个 python 脚本和我在网上找到的各种代码放在一起，
- https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect?rq=1，这里有很多很好的答案，这个来自 Kris。
所以基本上，
- 创建线段的输入列表
- 创建测试线的输入列表（图中的红线）。
- 遍历每条线的交点
- 创建一个包含所有交点的集合。
我已经重新创建了您的图表并使用它来测试交集代码。它使图中的两个交点正确。
C 和 C++ 具有这些数据结构的等价物，您也可以在 C 中编写交集算法（相当简单）。
from __future__ import division
# Thanks to @Kris for the intersection algorithm in python
# https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect
def find_intersection( p0, p1, p2, p3 ) :
s10_x = p1[0] - p0[0]
s10_y = p1[1] - p0[1]
s32_x = p3[0] - p2[0]
s32_y = p3[1] - p2[1]
denom = s10_x * s32_y - s32_x * s10_y
if denom == 0 : return None # collinear
denom_is_positive = denom > 0
s02_x = p0[0] - p2[0]
s02_y = p0[1] - p2[1]
s_numer = s10_x * s02_y - s10_y * s02_x
if (s_numer < 0) == denom_is_positive : return None # no collision
t_numer = s32_x * s02_y - s32_y * s02_x
if (t_numer < 0) == denom_is_positive : return None # no collision
if (s_numer > denom) == denom_is_positive or (t_numer > denom) == denom_is_positive : return None # no collision
# collision detected
t = t_numer / denom
intersection_point = [ p0[0] + (t * s10_x), p0[1] + (t * s10_y) ]
return intersection_point
# Create input data.
# black lines
line_segments = [[(1,4), (4,4)], [(2,3), (5,3)], [(3,2), (6,2)], [(6.5, 1), (7,1)], [(7.5, 0), (8.5,0)]]
# red lines
test_segments = [[(4.5,0), (4.5,4.5)], [(6.25, 0), (6.25, 4.5)]]
# Check all lines for intersections
intersections = set()
for test_segment in test_segments:
for line_segment in line_segments:
p0, p1 = test_segment[0], test_segment[1]
p2, p3 = line_segment[0], line_segment[1]
result = find_intersection(p0, p1, p2, p3)
if result is not None:
intersections.add(tuple(result))
print intersections
其它你可能感兴趣的问题