두 세그먼트가 교차하는지 어떻게 확인할 수 있습니까?
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) )) ||
(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
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
두 개의 선분이 있습니다. 끝점 A와 B로 한 세그먼트를 정의하고 끝점 C와 D로 두 번째 세그먼트를 정의합니다. 세그먼트 경계 내에서 교차해야한다는 것을 보여주는 좋은 방법이 있습니다. (선 자체가 세그먼트 경계를 넘어 교차 할 수 있으므로주의해야합니다. 좋은 코드는 평행선도 감시합니다.)
요령은 점 A와 B가 선 CD의 반대편에 있고 점 C와 D가 선 AB의 반대편에 있어야한다는 것을 테스트하는 것입니다.
이것은 숙제이므로 명시적인 해결책을주지 않겠습니다. 그러나 선의 어느 쪽이 포인트인지 확인하는 간단한 테스트는 내적을 사용하는 것입니다. 따라서 주어진 선 CD에 대해 해당 선에 대한 법선 벡터를 계산합니다 (N_C라고 부릅니다.) 이제 다음 두 결과의 부호를 테스트하기 만하면됩니다.
dot(A-C,N_C)
과
dot(B-C,N_C)
이러한 결과에 반대 부호가있는 경우 A와 B는 선 CD의 반대편입니다. 이제 다른 라인 AB에 대해 동일한 테스트를 수행하십시오. 그것은 법선 벡터 N_A를 가지고 있습니다. 징후 비교
dot(C-A,N_A)
과
dot(D-A,N_A)
법선 벡터를 계산하는 방법을 알아 내기 위해 맡기겠습니다. (2 차원에서는 사소한 일이지만 코드에서 A와 B가 서로 다른 점인지에 대해 걱정할까요? 마찬가지로 C와 D가 서로 다른가요?)
동일한 무한 선을 따라 놓이는 선분 또는 한 점이 실제로 다른 선분 자체에 속하는지 여전히 걱정할 필요가 있습니다. 좋은 코드는 가능한 모든 문제를 해결합니다.
다음은 두 점이 선분의 반대편에 있는지 확인하는 C 코드입니다. 이 코드를 사용하면 두 세그먼트가 교차하는지 확인할 수 있습니다.
// true if points p1, p2 lie on the opposite sides of segment s1--s2
bool oppositeSide (Point2f s1, Point2f s2, Point2f p1, Point2f p2) {
//calculate normal to the segment
Point2f vec = s1-s2;
Point2f normal(vec.y, -vec.x); // no need to normalize
// vectors to the points
Point2f v1 = p1-s1;
Point2f v2 = p2-s1;
// compare signs of the projections of v1, v2 onto the normal
float proj1 = v1.dot(normal);
float proj2 = v2.dot(normal);
if (proj1==0 || proj2==0)
cout<<"collinear points"<<endl;
return(SIGN(proj1) != SIGN(proj2));
}
닫힌 세그먼트가 교차하는지 확인하는 또 다른 파이썬 코드가 있습니다. http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ 에있는 C ++ 코드의 재 작성된 버전입니다 . 이 구현은 모든 특수한 경우 (예 : 동일 선상에있는 모든 점)를 다룹니다.
def on_segment(p, q, r):
'''Given three colinear points p, q, r, the function checks if
point q lies on line segment "pr"
'''
if (q[0] <= max(p[0], r[0]) and q[0] >= min(p[0], r[0]) and
q[1] <= max(p[1], r[1]) and q[1] >= min(p[1], r[1])):
return True
return False
def orientation(p, q, r):
'''Find orientation of ordered triplet (p, q, r).
The function returns following values
0 --> p, q and r are colinear
1 --> Clockwise
2 --> Counterclockwise
'''
val = ((q[1] - p[1]) * (r[0] - q[0]) -
(q[0] - p[0]) * (r[1] - q[1]))
if val == 0:
return 0 # colinear
elif val > 0:
return 1 # clockwise
else:
return 2 # counter-clockwise
def do_intersect(p1, q1, p2, q2):
'''Main function to check whether the closed line segments p1 - q1 and p2
- q2 intersect'''
o1 = orientation(p1, q1, p2)
o2 = orientation(p1, q1, q2)
o3 = orientation(p2, q2, p1)
o4 = orientation(p2, q2, q1)
# General case
if (o1 != o2 and o3 != o4):
return True
# Special Cases
# p1, q1 and p2 are colinear and p2 lies on segment p1q1
if (o1 == 0 and on_segment(p1, p2, q1)):
return True
# p1, q1 and p2 are colinear and q2 lies on segment p1q1
if (o2 == 0 and on_segment(p1, q2, q1)):
return True
# p2, q2 and p1 are colinear and p1 lies on segment p2q2
if (o3 == 0 and on_segment(p2, p1, q2)):
return True
# p2, q2 and q1 are colinear and q1 lies on segment p2q2
if (o4 == 0 and on_segment(p2, q1, q2)):
return True
return False # Doesn't fall in any of the above cases
다음은 작동하는지 확인하는 테스트 기능입니다.
import matplotlib.pyplot as plt
def test_intersect_func():
p1 = (1, 1)
q1 = (10, 1)
p2 = (1, 2)
q2 = (10, 2)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (10, 0)
q1 = (0, 10)
p2 = (0, 0)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (-5, -5)
q1 = (0, 0)
p2 = (1, 1)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
p1 = (0, 0)
q1 = (1, 1)
p2 = (1, 1)
q2 = (10, 10)
fig, ax = plt.subplots()
ax.plot([p1[0], q1[0]], [p1[1], q1[1]], 'x-')
ax.plot([p2[0], q2[0]], [p2[1], q2[1]], 'x-')
print(do_intersect(p1, q1, p2, q2))
방법을 사용하여 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
세그먼트 AB 및 CD의 경우 CD의 기울기를 찾습니다.
slope=(Dy-Cy)/(Dx-Cx)
CD를 A와 B 위로 확장하고 CD까지 똑바로 올라갑니다.
dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy
그들이 반대편에 있는지 확인하십시오
return dist1*dist2<0
선의 교차점을 찾고 싶다는 말을하지 않기 때문에 문제 해결이 더 간단 해집니다. 교차점이 필요하다면 OMG_peanuts 의 답 이 더 빠른 접근입니다. 그러나 선이 교차하는지 여부를 확인하려면 선 방정식 (ax + by + c = 0)을 사용하면됩니다. 접근 방식은 다음과 같습니다.
세그먼트 1과 세그먼트 2의 두 선분으로 시작하겠습니다.
segment1 = [[x1,y1], [x2,y2]] segment2 = [[x3,y3], [x4,y4]]두 개의 선 세그먼트가 길이가 0이 아닌 선과 별개의 세그먼트인지 확인합니다.
여기서부터는 두 세그먼트가 길이가 0이 아니고 구별된다고 가정합니다. 각 선분에 대해 선의 기울기를 계산 한 다음 ax + by + c = 0의 형태로 직선의 방정식을 얻습니다. 이제 두 점에 대해 f = ax + by + c 값을 계산합니다. 다른 선분 (다른 선분에 대해서도이 과정을 반복하십시오).
a2 = (y3-y4)/(x3-x4); b1 = -1; b2 = -1; c1 = y1 - a1*x1; c2 = y3 - a2*x3; // using the sign function from numpy f1_1 = sign(a1*x3 + b1*y3 + c1); f1_2 = sign(a1*x4 + b1*y4 + c1); f2_1 = sign(a2*x1 + b2*y1 + c2); f2_2 = sign(a2*x2 + b2*y2 + c2);이제 남은 것은 다른 경우뿐입니다. 어떤 점에 대해 f = 0이면 두 선이 한 점에 닿습니다. f1_1과 f1_2가 같거나 f2_1과 f2_2가 같으면 선이 교차하지 않습니다. f1_1과 f1_2가 같지 않고 f2_1과 f2_2가 같지 않으면 선 세그먼트가 교차합니다. 접하는 선을 "교차"로 간주할지 여부에 따라 조건을 조정할 수 있습니다.
벡터를 사용하여이 문제를 해결할 수도 있습니다.
세그먼트를 [start, end]. 이 개 같은 세그먼트를 감안 [A, B]하고 [C, D]모두 제로가 아닌 길이를 가지고, 우리는 우리가 세 벡터를 얻을 수 있도록 엔드 포인트 중 하나가 기준점으로 사용하도록 선택할 수 있습니다 :
x = 0
y = 1
p = A-C = [C[x]-A[x], C[y]-A[y]]
q = B-A = [B[x]-A[x], B[y]-A[y]]
r = D-C = [D[x]-C[x], D[y]-C[y]]
거기에서 우리는에서 t와 u를 계산하여 교차점을 찾을 수 있습니다 p + t*r = u*q. 방정식을 조금 가지고 놀아 보면 다음과 같은 결과를 얻게됩니다.
t = (q[y]*p[x] - q[x]*p[y])/(q[x]*r[y] - q[y]*r[x])
u = (p[x] + t*r[x])/q[x]
따라서 기능은 다음과 같습니다.
def intersects(a, b):
p = [b[0][0]-a[0][0], b[0][1]-a[0][1]]
q = [a[1][0]-a[0][0], a[1][1]-a[0][1]]
r = [b[1][0]-b[0][0], b[1][1]-b[0][1]]
t = (q[1]*p[0] - q[0]*p[1])/(q[0]*r[1] - q[1]*r[0]) \
if (q[0]*r[1] - q[1]*r[0]) != 0 \
else (q[1]*p[0] - q[0]*p[1])
u = (p[0] + t*r[0])/q[0] \
if q[0] != 0 \
else (p[1] + t*r[1])/q[1]
return t >= 0 and t <= 1 and u >= 0 and u <= 1
데이터가 선을 정의하는 경우 평행하지 않다는 것을 증명해야합니다. 이를 위해 다음을 계산할 수 있습니다.
alpha = float(y2 - y1) / (x2 - x1).
이 계수가 Line1과 Line2에 대해 같으면 선이 평행하다는 것을 의미합니다. 그렇지 않은 경우 교차한다는 의미입니다.
만약 그것들이 평행하다면 당신은 그것들이 같지 않다는 것을 증명해야합니다. 이를 위해
beta = y1 - alpha*x1
베타가 Line1과 Line2에 대해 같으면 선이 같기 때문에 교차한다는 의미입니다.
세그먼트 인 경우 각 라인에 대해 위에서 설명한대로 알파와 베타를 계산해야합니다. 그런 다음 (beta1-beta2) / (alpha1-alpha2)가 Min (x1_line1, x2_line1)보다 크고 Max (x1_line1, x2_line1)보다 작은 지 확인해야합니다.
세그먼트에 놓인 선의 교차점을 계산 한 다음 (기본적으로 선형 방정식 시스템을 해결하는 것을 의미 함) 세그먼트의 시작점과 끝점 사이에 있는지 확인합니다.
이것은 내가 AS3에 대해 얻은 것입니다. 파이썬에 대해 많이 모르지만 개념이 있습니다.
public function getIntersectingPointF($A:Point, $B:Point, $C:Point, $D:Point):Number {
var A:Point = $A.clone();
var B:Point = $B.clone();
var C:Point = $C.clone();
var D:Point = $D.clone();
var f_ab:Number = (D.x - C.x) * (A.y - C.y) - (D.y - C.y) * (A.x - C.x);
// are lines parallel
if (f_ab == 0) { return Infinity };
var f_cd:Number = (B.x - A.x) * (A.y - C.y) - (B.y - A.y) * (A.x - C.x);
var f_d:Number = (D.y - C.y) * (B.x - A.x) - (D.x - C.x) * (B.y - A.y);
var f1:Number = f_ab/f_d
var f2:Number = f_cd / f_d
if (f1 == Infinity || f1 <= 0 || f1 >= 1) { return Infinity };
if (f2 == Infinity || f2 <= 0 || f2 >= 1) { return Infinity };
return f1;
}
public function getIntersectingPoint($A:Point, $B:Point, $C:Point, $D:Point):Point
{
var f:Number = getIntersectingPointF($A, $B, $C, $D);
if (f == Infinity || f <= 0 || f >= 1) { return null };
var retPoint:Point = Point.interpolate($A, $B, 1 - f);
return retPoint.clone();
}
JAVA에서 구현되었습니다. 그러나 동일 선상 선 (일명 서로간에 존재하는 선분 L1 (0,0) (10,10) L2 (1,1) (2,2))에서는 작동하지 않는 것 같습니다.
public class TestCode
{
public class Point
{
public double x = 0;
public double y = 0;
public Point(){}
}
public class Line
{
public Point p1, p2;
public Line( double x1, double y1, double x2, double y2)
{
p1 = new Point();
p2 = new Point();
p1.x = x1;
p1.y = y1;
p2.x = x2;
p2.y = y2;
}
}
//line segments
private static Line s1;
private static Line s2;
public TestCode()
{
s1 = new Line(0,0,0,10);
s2 = new Line(-1,0,0,10);
}
public TestCode(double x1, double y1,
double x2, double y2,
double x3, double y3,
double x4, double y4)
{
s1 = new Line(x1,y1, x2,y2);
s2 = new Line(x3,y3, x4,y4);
}
public static void main(String args[])
{
TestCode code = null;
////////////////////////////
code = new TestCode(0,0,0,10,
0,1,0,5);
if( intersect(code) )
{ System.out.println( "OK COLINEAR: INTERSECTS" ); }
else
{ System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,0,10,
0,1,0,10);
if( intersect(code) )
{ System.out.println( "OK COLINEAR: INTERSECTS" ); }
else
{ System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,10,0,
5,0,15,0);
if( intersect(code) )
{ System.out.println( "OK COLINEAR: INTERSECTS" ); }
else
{ System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,10,0,
0,0,15,0);
if( intersect(code) )
{ System.out.println( "OK COLINEAR: INTERSECTS" ); }
else
{ System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,10,10,
1,1,5,5);
if( intersect(code) )
{ System.out.println( "OK COLINEAR: INTERSECTS" ); }
else
{ System.out.println( "ERROR COLINEAR: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,0,10,
-1,-1,0,10);
if( intersect(code) )
{ System.out.println( "OK SLOPE END: INTERSECTS" ); }
else
{ System.out.println( "ERROR SLOPE END: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(-10,-10,10,10,
-10,10,10,-10);
if( intersect(code) )
{ System.out.println( "OK SLOPE Intersect(0,0): INTERSECTS" ); }
else
{ System.out.println( "ERROR SLOPE Intersect(0,0): DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(-10,-10,10,10,
-3,-2,50,-2);
if( intersect(code) )
{ System.out.println( "OK SLOPE Line2 VERTIAL: INTERSECTS" ); }
else
{ System.out.println( "ERROR SLOPE Line2 VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(-10,-10,10,10,
50,-2,-3,-2);
if( intersect(code) )
{ System.out.println( "OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS" ); }
else
{ System.out.println( "ERROR SLOPE Line2 (reversed) VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,0,10,
1,0,1,10);
if( intersect(code) )
{ System.out.println( "ERROR PARALLEL VERTICAL: INTERSECTS" ); }
else
{ System.out.println( "OK PARALLEL VERTICAL: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,2,10,2,
0,10,10,10);
if( intersect(code) )
{ System.out.println( "ERROR PARALLEL HORIZONTAL: INTERSECTS" ); }
else
{ System.out.println( "OK PARALLEL HORIZONTAL: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,10,5,13.75,
0,18.75,10,15);
if( intersect(code) )
{ System.out.println( "ERROR PARALLEL SLOPE=.75: INTERSECTS" ); }
else
{ System.out.println( "OK PARALLEL SLOPE=.75: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,1,1,
2,-1,2,10);
if( intersect(code) )
{ System.out.println( "ERROR SEPERATE SEGMENTS: INTERSECTS" ); }
else
{ System.out.println( "OK SEPERATE SEGMENTS: DO NOT INTERSECT" ); }
////////////////////////////
code = new TestCode(0,0,1,1,
-1,-10,-5,10);
if( intersect(code) )
{ System.out.println( "ERROR SEPERATE SEGMENTS 2: INTERSECTS" ); }
else
{ System.out.println( "OK SEPERATE SEGMENTS 2: DO NOT INTERSECT" ); }
}
public static boolean intersect( TestCode code )
{
return intersect( code.s1, code.s2);
}
public static boolean intersect( Line line1, Line line2 )
{
double i1min = Math.min(line1.p1.x, line1.p2.x);
double i1max = Math.max(line1.p1.x, line1.p2.x);
double i2min = Math.min(line2.p1.x, line2.p2.x);
double i2max = Math.max(line2.p1.x, line2.p2.x);
double iamax = Math.max(i1min, i2min);
double iamin = Math.min(i1max, i2max);
if( Math.max(line1.p1.x, line1.p2.x) < Math.min(line2.p1.x, line2.p2.x) )
return false;
double m1 = (line1.p2.y - line1.p1.y) / (line1.p2.x - line1.p1.x );
double m2 = (line2.p2.y - line2.p1.y) / (line2.p2.x - line2.p1.x );
if( m1 == m2 )
return false;
//b1 = line1[0][1] - m1 * line1[0][0]
//b2 = line2[0][1] - m2 * line2[0][0]
double b1 = line1.p1.y - m1 * line1.p1.x;
double b2 = line2.p1.y - m2 * line2.p1.x;
double x1 = (b2 - b1) / (m1 - m2);
if( (x1 < Math.max(i1min, i2min)) || (x1 > Math.min(i1max, i2max)) )
return false;
return true;
}
}
지금까지의 출력은
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
ERROR COLINEAR: DO NOT INTERSECT
OK SLOPE END: INTERSECTS
OK SLOPE Intersect(0,0): INTERSECTS
OK SLOPE Line2 VERTIAL: INTERSECTS
OK SLOPE Line2 (reversed) VERTIAL: INTERSECTS
OK PARALLEL VERTICAL: DO NOT INTERSECT
OK PARALLEL HORIZONTAL: DO NOT INTERSECT
OK PARALLEL SLOPE=.75: DO NOT INTERSECT
OK SEPERATE SEGMENTS: DO NOT INTERSECT
OK SEPERATE SEGMENTS 2: DO NOT INTERSECT
좋은 Swift 솔루션을 제공 할 것이라고 생각했습니다.
struct Pt {
var x: Double
var y: Double
}
struct LineSegment {
var p1: Pt
var p2: Pt
}
func doLineSegmentsIntersect(ls1: LineSegment, ls2: LineSegment) -> Bool {
if (ls1.p2.x-ls1.p1.x == 0) { //handle vertical segment1
if (ls2.p2.x-ls2.p1.x == 0) {
//both lines are vertical and parallel
return false
}
let x = ls1.p1.x
let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
let c2 = ls2.p1.y-slope2*ls2.p1.x
let y = x*slope2+c2 // y intersection point
return (y > ls1.p1.y && x < ls1.p2.y) || (y > ls1.p2.y && y < ls1.p1.y) // check if y is between y1,y2 in segment1
}
if (ls2.p2.x-ls2.p1.x == 0) { //handle vertical segment2
let x = ls2.p1.x
let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
let c1 = ls1.p1.y-slope1*ls1.p1.x
let y = x*slope1+c1 // y intersection point
return (y > ls2.p1.y && x < ls2.p2.y) || (y > ls2.p2.y && y < ls2.p1.y) // validate that y is between y1,y2 in segment2
}
let slope1 = (ls1.p2.y-ls1.p1.y)/(ls1.p2.x-ls1.p1.x)
let slope2 = (ls2.p2.y-ls2.p1.y)/(ls2.p2.x-ls2.p1.x)
if (slope1 == slope2) { //segments are parallel
return false
}
let c1 = ls1.p1.y-slope1*ls1.p1.x
let c2 = ls2.p1.y-slope2*ls2.p1.x
let x = (c2-c1)/(slope1-slope2)
return (((x > ls1.p1.x && x < ls1.p2.x) || (x > ls1.p2.x && x < ls1.p1.x)) &&
((x > ls2.p1.x && x < ls2.p2.x) || (x > ls2.p2.x && x < ls2.p1.x)))
//validate that x is between x1,x2 in both segments
}
This is my way of checking for line crossing and where the intersection occurs. Lets use x1 through x4 and y1 through y4
Segment1 = {(X1, Y1), (X2, Y2)}
Segment2 = {(X3, Y3), (X4, Y4)}
Then we need some vectors to represent them
dx1 = X2 - X1
dx2 = X4 - X4
dy1 = Y2 - Y1
dy2 = Y4 - Y3
Now we look at the determinant
det = dx1 * dy2 - dx2 * dy1
If the determinant is 0.0, then the line segments are parallel. This could mean they overlap. If they overlap just at endpoints, then there is one intersection solution. Otherwise there will be infinite solutions. With infinitely many solutions, what do say is your point of intersection? So it's an interesting special case. If you know ahead of time that the lines can't overlap then you can just check if det == 0.0 and if so just say they don't intersect and be done. Otherwise, lets continue on
dx3 = X3 - X1
dy3 = Y3 - Y1
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
Now, if det, det1 and det2 are all zero, then your lines are co-linear and could overlap. If det is zero but either det1 or det2 are not, then they are not co-linear, but are parallel, so there is no intersection. So what's left now if det is zero is a 1D problem instead of 2D. We will need to check one of two ways, depending if dx1 is zero or not (so we can avoid division by zero). If dx1 is zero then just do the same logic with y values rather than x below.
s = X3 / dx1
t = X4 / dx1
This computes two scalers, such that if we scale the vector (dx1, dy1) by s we get point (x3, y3), and by t we get (x4, y4). So if either s or t is between 0.0 and 1.0, then point 3 or 4 lies on our first line. Negative would mean the point is behind the start of our vector, while > 1.0 means it is further ahead of the end of our vector. 0.0 means it is at (x1, y1) and 1.0 means it is at (x2, y2). If both s and t are < 0.0 or both are > 1.0, then they don't intersect. And that handles the parallel lines special case.
Now, if det != 0.0 then
s = det1 / det
t = det2 / det
if (s < 0.0 || s > 1.0 || t < 0.0 || t > 1.0)
return false // no intersect
This is similar to what we were doing above really. Now if we pass the above test, then our line segments intersect, and we can calculate the intersection quite easily like so:
Ix = X1 + t * dx1
Iy = Y1 + t * dy1
If you want to dig deeper into what the math is doing, look into Cramer's Rule.
해결되었지만 여전히 python ... :)
def islineintersect(line1, line2):
i1 = [min(line1[0][0], line1[1][0]), max(line1[0][0], line1[1][0])]
i2 = [min(line2[0][0], line2[1][0]), max(line2[0][0], line2[1][0])]
ia = [max(i1[0], i2[0]), min(i1[1], i2[1])]
if max(line1[0][0], line1[1][0]) < min(line2[0][0], line2[1][0]):
return False
m1 = (line1[1][1] - line1[0][1]) * 1. / (line1[1][0] - line1[0][0]) * 1.
m2 = (line2[1][1] - line2[0][1]) * 1. / (line2[1][0] - line2[0][0]) * 1.
if m1 == m2:
return False
b1 = line1[0][1] - m1 * line1[0][0]
b2 = line2[0][1] - m2 * line2[0][0]
x1 = (b2 - b1) / (m1 - m2)
if (x1 < max(i1[0], i2[0])) or (x1 > min(i1[1], i2[1])):
return False
return True
이:
print islineintersect([(15, 20), (100, 200)], [(210, 5), (23, 119)])
산출:
True
이:
print islineintersect([(15, 20), (100, 200)], [(-1, -5), (-5, -5)])
산출:
False
참고 URL : https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect
'developer tip' 카테고리의 다른 글
| 와일드 카드 하위 도메인 및 정적 하위 도메인 용 가상 호스트 (0) | 2020.11.10 |
|---|---|
| 함수 선언과 프로토 타입을위한 대체 (K & R) C 구문 (0) | 2020.11.10 |
| SQL Server Management Studio 2008에서 만든 트리거를 볼 수 없습니다. (0) | 2020.11.10 |
| 열을 null로 만들기위한 Rails 마이그레이션 => true (0) | 2020.11.10 |
| 고유하지 않은 열의 날짜별로 Pandas DataFrame 항목을 그룹화하는 방법 (0) | 2020.11.10 |