2 개의 세그먼트가 교차하는지 어떻게 확인할 수 있습니까?
다음 데이터가 있습니다.
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
두 줄이 교차하는지 감지하기 위해 Python으로 작은 알고리즘을 작성해야합니다.
답변
선의 방정식은 다음과 같습니다.
f(x) = A*x + b = y
세그먼트의 경우 x가 구간 I에 포함된다는 점을 제외하면 정확히 동일합니다.
두 개의 세그먼트가있는 경우 다음과 같이 정의됩니다.
Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}
잠재적 교차점 (Xa, Ya)의 abcisse Xa는 다음과 같이 정의 된 간격 I1 및 I2 모두에 포함되어야합니다.
I1 = [min(X1,X2), max(X1,X2)]
I2 = [min(X3,X4), max(X3,X4)]
그리고 우리는 Xa가 다음에 포함되어 있다고 말할 수 있습니다.
Ia = [max( min(X1,X2), min(X3,X4) ),
min( max(X1,X2), max(X3,X4) )]
이제이 간격 Ia가 존재하는지 확인해야합니다.
if (max(X1,X2) < min(X3,X4)):
return False # There is no mutual abcisses
그래서, 우리는 두 줄 공식과 상호 간격을 가지고 있습니다. 라인 공식은 다음과 같습니다.
f1(x) = A1*x + b1 = y
f2(x) = A2*x + b2 = y
세그먼트별로 두 점을 얻었으므로 A1, A2, b1 및 b2를 결정할 수 있습니다.
A1 = (Y1-Y2)/(X1-X2) # Pay attention to not dividing by zero
A2 = (Y3-Y4)/(X3-X4) # Pay attention to not dividing by zero
b1 = Y1-A1*X1 = Y2-A1*X2
b2 = Y3-A2*X3 = Y4-A2*X4
세그먼트가 평행 한 경우 A1 == A2 :
if (A1 == A2):
return False # Parallel segments
두 줄에있는 점 (Xa, Ya)은 두 공식 f1과 f2를 모두 확인해야합니다.
Ya = A1 * Xa + b1
Ya = A2 * Xa + b2
A1 * Xa + b1 = A2 * Xa + b2
Xa = (b2 - b1) / (A1 - A2) # Once again, pay attention to not dividing by zero
마지막으로 할 일은 Xa가 Ia에 포함되어 있는지 확인하는 것입니다.
if ( (Xa < max( min(X1,X2), min(X3,X4) )) or
(Xa > min( max(X1,X2), max(X3,X4) )) ):
return False # intersection is out of bound
else:
return True
이 외에도 시작시 제공된 4 개의 포인트 중 2 개가 모든 테스트를 피하기 위해 동일하지 않은지 확인할 수 있습니다.
답변
사용자 @ i_4_got 은 Python에서 매우 효율적인 솔루션 으로이 페이지 를 가리 킵니다 . 편의를 위해 여기에서 재현합니다 (여기에 있으면 행복하게 만들었 기 때문에).
def ccw(A,B,C):
return (C.y-A.y) * (B.x-A.x) > (B.y-A.y) * (C.x-A.x)
# Return true if line segments AB and CD intersect
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
답변
정확하게 계산할 필요는 없습니다. 세그먼트가 교차 위치를 교차 하는지 여부 만 이해 하면됩니다. 이것은 솔루션을 단순화합니다.
아이디어는 하나의 세그먼트를 “앵커”로 취급하고 두 번째 세그먼트를 2 개의 점으로 분리하는 것입니다.
이제 “고정 된”세그먼트 (OnLeft, OnRight 또는 동일 선상)에 대한 각 지점의 상대적 위치를 찾아야합니다.
두 점에 대해 이렇게 한 후 점 중 하나가 OnLeft이고 다른 점이 OnRight인지 확인합니다 (또는 부적절한 교차점도 포함하려는 경우 동일 선상 위치를 포함 ).
그런 다음 앵커 및 분리 된 세그먼트의 역할로 프로세스를 반복해야합니다.
교차점은 점 중 하나가 OnLeft이고 다른 하나가 OnRight 인 경우에만 존재합니다. 가능한 각 사례에 대한 예제 이미지와 함께 자세한 설명 은 이 링크 를 참조하십시오 .
이러한 방법을 구현하는 것은 교차점을 찾는 방법을 실제로 구현하는 것보다 훨씬 쉽습니다 (여러분이 처리해야하는 많은 코너 케이스를 감안할 때).
최신 정보
다음 함수는 아이디어를 설명해야합니다 (출처 : Computational Geometry in C ).
비고 : 이 샘플에서는 정수 사용을 가정합니다. 대신 부동 소수점 표현을 사용하는 경우 (분명히 복잡 할 수 있음) 일부 엡실론 값을 결정하여 “동등”을 나타내야합니다 (대부분 IsCollinear평가 용).
// points "a" and "b" forms the anchored segment.
// point "c" is the evaluated point
bool IsOnLeft(Point a, Point b, Point c)
{
return Area2(a, b, c) > 0;
}
bool IsOnRight(Point a, Point b, Point c)
{
return Area2(a, b, c) < 0;
}
bool IsCollinear(Point a, Point b, Point c)
{
return Area2(a, b, c) == 0;
}
// calculates the triangle's size (formed by the "anchor" segment and additional point)
int Area2(Point a, Point b, Point c)
{
return (b.X - a.X) * (c.Y - a.Y) -
(c.X - a.X) * (b.Y - a.Y);
}
물론 이러한 기능을 사용할 때 각 세그먼트가 다른 세그먼트 “사이”에 있는지 확인해야합니다 (이들은 무한 선이 아니라 유한 세그먼트이기 때문입니다).
또한 이러한 기능을 사용하면 교차로 가 적절 하거나 부적절한 지 여부를 이해할 수 있습니다 .
- Proper : 동일 선상의 점이 없습니다. 세그먼트는 “옆으로”서로 교차합니다.
- 부적절 : 한 세그먼트가 다른 세그먼트에만 “접촉”합니다 (하나 이상의 점이 고정 된 세그먼트와 동일 선상에 있음).
답변
두 세그먼트에 끝점 A, B 및 C, D가 있다고 가정합니다. 교차를 결정하는 수치 적으로 강력한 방법은 네 가지 행렬식의 부호를 확인하는 것입니다.
| Ax-Cx Bx-Cx | | Ax-Dx Bx-Dx |
| Ay-Cy By-Cy | | Ay-Dy By-Dy |
| Cx-Ax Dx-Ax | | Cx-Bx Dx-Bx |
| Cy-Ay Dy-Ay | | Cy-By Dy-By |
교차의 경우 왼쪽에있는 각 행렬식은 오른쪽에있는 것과 반대되는 부호를 가져야하지만 두 선 사이에 관계가있을 필요는 없습니다. 기본적으로 세그먼트의 각 점이 다른 세그먼트에 의해 정의 된 선의 반대편에 있는지 확인하기 위해 다른 세그먼트에 대해 확인합니다.
여기를 참조하십시오 : http://www.cs.cmu.edu/~quake/robust.html
답변
방법을 사용하여 Shapely 라이브러리를 사용 하면 선 세그먼트가 교차하는지 확인하는 것이 매우 쉽습니다 intersects.
from shapely.geometry import LineString
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 0)])
print(line.intersects(other))
# True
line = LineString([(0, 0), (1, 1)])
other = LineString([(0, 1), (1, 2)])
print(line.intersects(other))
# False
답변
Liran 과 Grumdrig의 훌륭한 답변을 바탕으로 닫힌 세그먼트가 교차 하는지 확인하는 완전한 Python 코드가 있습니다. 동일 선상 세그먼트, Y 축에 평행 한 세그먼트, 세그먼트 퇴화 (악마가 자세히 설명 됨)에 대해 작동합니다. 정수 좌표를 가정합니다. 부동 소수점 좌표는 점 동등성 테스트를 수정해야합니다.
def side(a,b,c):
""" Returns a position of the point c relative to the line going through a and b
Points a, b are expected to be different
"""
d = (c[1]-a[1])*(b[0]-a[0]) - (b[1]-a[1])*(c[0]-a[0])
return 1 if d > 0 else (-1 if d < 0 else 0)
def is_point_in_closed_segment(a, b, c):
""" Returns True if c is inside closed segment, False otherwise.
a, b, c are expected to be collinear
"""
if a[0] < b[0]:
return a[0] <= c[0] and c[0] <= b[0]
if b[0] < a[0]:
return b[0] <= c[0] and c[0] <= a[0]
if a[1] < b[1]:
return a[1] <= c[1] and c[1] <= b[1]
if b[1] < a[1]:
return b[1] <= c[1] and c[1] <= a[1]
return a[0] == c[0] and a[1] == c[1]
#
def closed_segment_intersect(a,b,c,d):
""" Verifies if closed segments a, b, c, d do intersect.
"""
if a == b:
return a == c or a == d
if c == d:
return c == a or c == b
s1 = side(a,b,c)
s2 = side(a,b,d)
# All points are collinear
if s1 == 0 and s2 == 0:
return \
is_point_in_closed_segment(a, b, c) or is_point_in_closed_segment(a, b, d) or \
is_point_in_closed_segment(c, d, a) or is_point_in_closed_segment(c, d, b)
# No touching and on the same side
if s1 and s1 == s2:
return False
s1 = side(c,d,a)
s2 = side(c,d,b)
# No touching and on the same side
if s1 and s1 == s2:
return False
return True
답변
다음은 내적을 사용하는 솔루션입니다.
# assumes line segments are stored in the format [(x0,y0),(x1,y1)]
def intersects(s0,s1):
dx0 = s0[1][0]-s0[0][0]
dx1 = s1[1][0]-s1[0][0]
dy0 = s0[1][1]-s0[0][1]
dy1 = s1[1][1]-s1[0][1]
p0 = dy1*(s1[1][0]-s0[0][0]) - dx1*(s1[1][1]-s0[0][1])
p1 = dy1*(s1[1][0]-s0[1][0]) - dx1*(s1[1][1]-s0[1][1])
p2 = dy0*(s0[1][0]-s1[0][0]) - dx0*(s0[1][1]-s1[0][1])
p3 = dy0*(s0[1][0]-s1[1][0]) - dx0*(s0[1][1]-s1[1][1])
return (p0*p1<=0) & (p2*p3<=0)
다음은 Desmos의 시각화입니다 : Line Segment Intersection
