반응형
두 세그먼트가 교차하는지 확인하려면 어떻게 해야 합니까?
두 개의 세그먼트가 교차하는지 확인하려면 어떻게 해야 합니까?
다음과 같은 데이터가 있습니다.
Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]
두 선이 교차하는지 감지하기 위해 파이썬으로 작은 알고리즘을 작성해야 합니다.
사용자 @i_4_는 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)
선의 방정식은 다음과 같습니다.
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
세그먼트별로 2점을 얻었기 때문에 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개가 동일하지 않은지 확인하여 모든 테스트를 피할 수 있습니다.
세그먼트가 정확히 교차하는 위치를 계산할 필요는 없지만, 세그먼트가 교차하는지 여부만 이해할 수 있습니다.이렇게 하면 솔루션이 단순해집니다.
이 개념은 한 세그먼트를 "앵커"로 처리하고 두 번째 세그먼트를 두 개의 포인트로 분리하는 것입니다.
이제 "고정" 세그먼트에 대한 각 점의 상대적 위치를 찾아야 합니다(왼쪽, 오른쪽 또는 동일선).
두 점 모두에 대해 이 작업을 수행한 후 점 중 하나가 왼쪽에 있고 다른 점이 오른쪽에 있는지 확인합니다(잘못된 교차점도 포함하려면 공선 위치도 포함).
그런 다음 앵커 및 분리된 세그먼트의 역할을 사용하여 공정을 반복해야 합니다.
교차점은 점 중 하나가 왼쪽에 있고 다른 점이 오른쪽에 있는 경우에만 존재합니다.가능한 각 사례에 대한 예제 이미지와 함께 자세한 설명을 보려면 이 링크를 참조하십시오.
이러한 방법을 구현하는 것은 교차점을 찾는 방법을 실제로 구현하는 것보다 훨씬 쉬울 것입니다(또한 처리해야 할 많은 코너 사례를 고려할 때).
갱신하다
다음 기능은 아이디어를 설명해야 합니다(출처:계산 지오메트리(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);
}
물론 이러한 기능을 사용할 때는 각 세그먼트가 다른 세그먼트 사이에 있는지 확인해야 합니다(이 세그먼트는 유한 세그먼트이며 무한선이 아니기 때문에).
또한 이러한 기능을 사용하면 적절한 교차점이 있는지 또는 부적절한 교차점이 있는지 파악할 수 있습니다.
- 적합: 공선 점이 없습니다.세그먼트는 "옆에서 옆으로" 서로 교차합니다.
- 부적절:한 세그먼트만 다른 세그먼트에 "접촉"합니다(점 중 하나 이상이 고정된 세그먼트와 동일선상에 있음).
두 세그먼트에 끝점 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/ ~https/https.https
Shapely 라이브러리를 사용하면 다음 방법을 사용하여 선 세그먼트가 교차하는지 쉽게 확인할 수 있습니다.
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
도트 제품을 사용하는 솔루션은 다음과 같습니다.
# 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의 시각화는 다음과 같습니다.선 세그먼트 교차점
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
이것이 저의 교차로와 교차로가 어디에서 발생하는지 확인하는 방법입니다.x1 ~ x4 및 y1 ~ y4를 사용합니다.
Segment1 = ((X1, Y1), (X2, Y2))
Segment2 = ((X3, Y3), (X4, Y4))
그럼 우리는 그들을 표현할 벡터가 필요합니다.
dx1 = X2 - X1
dx2 = X4 - X3
dy1 = Y2 - Y1
dy2 = Y4 - Y3
이제 우리는 결정적인 요인을 것입니다.
det = dx1 * dy2 - dx2 * dy1
행렬식이 0.0이면 선분이 평행합니다.이것은 그들이 겹친다는 것을 의미할 수 있습니다.끝점에서만 겹치면 교차 솔루션이 하나 있습니다.그렇지 않으면 무한한 해결책이 있을 것입니다.무한히 많은 솔루션을 사용할 때 교차점은 무엇이라고 생각하십니까?그래서 이것은 흥미로운 특별한 경우입니다.라인이 겹칠 수 없다는 것을 미리 알고 있다면, 그냥 확인할 수 있습니다.det == 0.0그리고 만약 그렇다면 그들이 교차하지 않고 끝난다고 말하세요.아니면 계속 진행하도록.
dx3 = X1 - X3
dy3 = Y1 - Y3
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
이제 det, det1 및 det2가 모두 0이면 선이 동일한 선형이므로 겹칠 수 있습니다.det가 0이지만 det1 또는 det2가 아닌 경우에는 동일선형이 아니라 평행이므로 교차점이 없습니다.그래서 만약 det이 0이라면 이제 남은 것은 2D가 아닌 1D 문제입니다.dx1이 0인지 아닌지에 따라 두 가지 방법 중 하나를 확인해야 합니다(0으로 나눗셈을 피할 수 있습니다).dx1이 0이면 아래의 x가 아닌 y 값으로 동일한 논리를 수행합니다.
s = X3 / dx1
t = X4 / dx1
이것은 벡터(dx1, dy1)를 점(x3, y3)만큼 확장하고 점(x4, y4)만큼 확장하는 두 개의 스케일러를 계산합니다.따라서 sort 중 하나가 0.0과 1.0 사이라면 3점 또는 4점이 첫 번째 선에 있습니다.마이너스는 점이 벡터의 시작 뒤에 있다는 것을 의미하는 반면, 1.0 이상은 벡터의 끝보다 더 앞에 있다는 것을 의미합니다.0.0은 (x1, y1)에 있음을 의미하고 1.0은 (x2, y2)에 있음을 의미합니다.s와 t가 모두 < 0.0이거나 둘 다 > 1.0이면 교차하지 않습니다.그리고 그것은 평행선의 특수한 경우를 처리합니다.
자, 만약에det != 0.0그리고나서
s = det1 / det
t = det2 / det
if s < 0.0 or s > 1.0 or t < 0.0 or t > 1.0:
return false # no intersect
이것은 우리가 위에서 실제로 했던 것과 비슷합니다.위의 테스트를 통과하면 선분이 교차하고 교차점을 쉽게 계산할 수 있습니다.
Ix = X1 + t * dx1
Iy = Y1 + t * dy1
만약 여러분이 수학이 무엇을 하고 있는지 더 깊이 파고들고 싶다면, Cramer's Rule을 들여다보세요.
편집: 두 개의 오류를 수정했으므로 지금 수정해야 합니다.나는 지금 이것을 위한 실제 코드를 작성할 수 있을 만큼 충분히 파이썬을 배웠습니다.일부 특수한 경우를 제외하고는 작동하지만 일부 특수한 경우는 올바르게 처리합니다.특별한 사건들은 처리하기가 정말 어려워지고 저는 그것에 충분한 시간을 소비했고 앞으로 나아가길 원합니다.만약 누군가가 더 나은 것을 요구한다면, 그들은 적어도 그것을 개선하기 위해 좋은 출발점을 가지고 있습니다.
import math
def line_intersection(line1, line2):
x1, x2, x3, x4 = line1[0][0], line1[1][0], line2[0][0], line2[1][0]
y1, y2, y3, y4 = line1[0][1], line1[1][1], line2[0][1], line2[1][1]
dx1 = x2 - x1
dx2 = x4 - x3
dy1 = y2 - y1
dy2 = y4 - y3
dx3 = x1 - x3
dy3 = y1 - y3
det = dx1 * dy2 - dx2 * dy1
det1 = dx1 * dy3 - dx3 * dy1
det2 = dx2 * dy3 - dx3 * dy2
if det == 0.0: # lines are parallel
if det1 != 0.0 or det2 != 0.0: # lines are not co-linear
return None # so no solution
if dx1:
if x1 < x3 < x2 or x1 > x3 > x2:
return math.inf # infinitely many solutions
else:
if y1 < y3 < y2 or y1 > y3 > y2:
return math.inf # infinitely many solutions
if line1[0] == line2[0] or line1[1] == line2[0]:
return line2[0]
elif line1[0] == line2[1] or line1[1] == line2[1]:
return line2[1]
return None # no intersection
s = det1 / det
t = det2 / det
if 0.0 < s < 1.0 and 0.0 < t < 1.0:
return x1 + t * dx1, y1 + t * dy1
print("one intersection")
print(line_intersection(((0.0,0.0), (6.0,6.0)),((0.0,9.0), (9.0,0.0))))
print(line_intersection(((-2, -2), (2, 2)), ((2, -2), (-2, 2))))
print(line_intersection(((0.5, 0.5), (1.5, 0.5)), ((1.0, 0.0), (1.0, 2.0))))
print(line_intersection(((0, -1), (0, 0)), ((0, 0), (0, 1))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (1, 0))))
print()
print("no intersection")
print(line_intersection(((-1, -1), (0, 0)), ((2, -4), (2, 4))))
print(line_intersection(((0.0,0.0), (0.0,9.0)),((9.0,0.0), (9.0,99.0))))
print(line_intersection(((0, 0), (1, 1)), ((1, 0), (2, 1))))
print(line_intersection(((-1, 1), (0, 1)), ((0, 0), (1, 0))))
print(line_intersection(((1, -1), (1, 0)), ((0, 0), (0, -1))))
print()
print("infinite intersection")
print(line_intersection(((-1, -1), (1, 1)), ((0, 0), (2, 2))))
print(line_intersection(((-1, 0), (1, 0)), ((0, 0), (2, 0))))
print(line_intersection(((0, -1), (0, 1)), ((0, 0), (0, 2))))
print(line_intersection(((-1, 0), (0, 0)), ((0, 0), (-1, 0))))
print(line_intersection(((1, 0), (0, 0)), ((0, 0), (1, 0))))
닫힌 세그먼트가 교차하는지 확인하는 또 다른 파이썬 코드가 있습니다.이것은 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))
두 개의 선분이 있습니다.하나의 세그먼트를 끝점 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-d에서, 그것은 사소한 것이지만, 당신의 코드는 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));
}
조지의 대답은 지금까지 실행하기에 가장 깨끗한 것입니다.브릭스보의 예는 간단하기도 하지만, 공선성에 문제가 있었기 때문에 이것을 추적해야 했습니다.
테스트 코드:
#!/usr/bin/python
#
# Notes on intersection:
#
# https://bryceboe.com/2006/10/23/line-segment-intersection-algorithm/
#
# https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect
from shapely.geometry import LineString
class Point:
def __init__(self,x,y):
self.x = x
self.y = y
def ccw(A,B,C):
return (C.y-A.y)*(B.x-A.x) > (B.y-A.y)*(C.x-A.x)
def intersect(A,B,C,D):
return ccw(A,C,D) != ccw(B,C,D) and ccw(A,B,C) != ccw(A,B,D)
def ShapelyIntersect(A,B,C,D):
return LineString([(A.x,A.y),(B.x,B.y)]).intersects(LineString([(C.x,C.y),(D.x,D.y)]))
a = Point(0,0)
b = Point(0,1)
c = Point(1,1)
d = Point(1,0)
'''
Test points:
b(0,1) c(1,1)
a(0,0) d(1,0)
'''
# F
print(intersect(a,b,c,d))
# T
print(intersect(a,c,b,d))
print(intersect(b,d,a,c))
print(intersect(d,b,a,c))
# F
print(intersect(a,d,b,c))
# same end point cases:
print("same end points")
# F - not intersected
print(intersect(a,b,a,d))
# T - This shows as intersected
print(intersect(b,a,a,d))
# F - this does not
print(intersect(b,a,d,a))
# F - this does not
print(intersect(a,b,d,a))
print("same end points, using shapely")
# T
print(ShapelyIntersect(a,b,a,d))
# T
print(ShapelyIntersect(b,a,a,d))
# T
print(ShapelyIntersect(b,a,d,a))
# T
print(ShapelyIntersect(a,b,d,a))
세그먼트 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의 답변은 더 빠른 접근 방식입니다.그러나 선이 교차하는지 여부만 확인하려면 선 방정식(축 + x + c = 0)을 사용하면 됩니다.접근 방식은 다음과 같습니다.
세그먼트 1과 세그먼트 2의 두 개의 라인 세그먼트로 시작하겠습니다.
segment1 = [[x1,y1], [x2,y2]] segment2 = [[x3,y3], [x4,y4]]두 개의 선 세그먼트가 0이 아닌 선과 구별되는 세그먼트인지 확인합니다.
이때부터, 저는 두 세그먼트가 0이 아닌 길이이고 구별된다고 가정합니다.각 선분에 대해 선의 기울기를 계산한 다음 축 + x + c = 0의 형태로 선의 방정식을 구합니다.이제 다른 라인 세그먼트의 두 점에 대해 f = ax + x + 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]0이 길이를 가지고 을, 는 기준점으로 중 의 벡터를 수 : 다 길 이 이 0 아 닌 경 우 사 로 으 할 용 기 점 끝 준 둘 있 다 수 니 점 습 얻 중 을 벡 세 의 를 터 개 여 하 택 나 를 하 선 가 : ▁vectors ▁that ▁to ▁three , 둘 다 ▁we ▁one ▁have 있 니 ▁so 습 ▁non
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
위의 솔루션 중 하나가 너무 잘 작동해서 wxPython을 사용하여 완전한 데모 프로그램을 작성하기로 결정했습니다.당신은 이 프로그램을 다음과 같이 실행할 수 있어야 합니다: 파이썬 "당신의 파일 이름"
# Click on the window to draw a line.
# The program will tell you if this and the other line intersect.
import wx
class Point:
def __init__(self, newX, newY):
self.x = newX
self.y = newY
app = wx.App()
frame = wx.Frame(None, wx.ID_ANY, "Main")
p1 = Point(90,200)
p2 = Point(150,80)
mp = Point(0,0) # mouse point
highestX = 0
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)
def is_intersection(p1, p2, p3, p4):
return intersect(p1, p2, p3, p4)
def drawIntersection(pc):
mp2 = Point(highestX, mp.y)
if is_intersection(p1, p2, mp, mp2):
pc.DrawText("intersection", 10, 10)
else:
pc.DrawText("no intersection", 10, 10)
def do_paint(evt):
pc = wx.PaintDC(frame)
pc.DrawLine(p1.x, p1.y, p2.x, p2.y)
pc.DrawLine(mp.x, mp.y, highestX, mp.y)
drawIntersection(pc)
def do_left_mouse(evt):
global mp, highestX
point = evt.GetPosition()
mp = Point(point[0], point[1])
highestX = frame.Size[0]
frame.Refresh()
frame.Bind(wx.EVT_PAINT, do_paint)
frame.Bind(wx.EVT_LEFT_DOWN, do_left_mouse)
frame.Show()
app.MainLoop()
OMG_Peanuts 솔루션을 사용하여 SQL로 번역했습니다.(HANA 스칼라 함수)
OMG_땅콩 덕분에 잘 작동합니다.저는 둥근 지구를 사용하고 있지만, 거리가 작아서 괜찮은 것 같습니다.
FUNCTION GA_INTERSECT" ( IN LAT_A1 DOUBLE,
IN LONG_A1 DOUBLE,
IN LAT_A2 DOUBLE,
IN LONG_A2 DOUBLE,
IN LAT_B1 DOUBLE,
IN LONG_B1 DOUBLE,
IN LAT_B2 DOUBLE,
IN LONG_B2 DOUBLE)
RETURNS RET_DOESINTERSECT DOUBLE
LANGUAGE SQLSCRIPT
SQL SECURITY INVOKER AS
BEGIN
DECLARE MA DOUBLE;
DECLARE MB DOUBLE;
DECLARE BA DOUBLE;
DECLARE BB DOUBLE;
DECLARE XA DOUBLE;
DECLARE MAX_MIN_X DOUBLE;
DECLARE MIN_MAX_X DOUBLE;
DECLARE DOESINTERSECT INTEGER;
SELECT 1 INTO DOESINTERSECT FROM DUMMY;
IF LAT_A2-LAT_A1 != 0 AND LAT_B2-LAT_B1 != 0 THEN
SELECT (LONG_A2 - LONG_A1)/(LAT_A2 - LAT_A1) INTO MA FROM DUMMY;
SELECT (LONG_B2 - LONG_B1)/(LAT_B2 - LAT_B1) INTO MB FROM DUMMY;
IF MA = MB THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
END IF;
SELECT LONG_A1-MA*LAT_A1 INTO BA FROM DUMMY;
SELECT LONG_B1-MB*LAT_B1 INTO BB FROM DUMMY;
SELECT (BB - BA) / (MA - MB) INTO XA FROM DUMMY;
-- Max of Mins
IF LAT_A1 < LAT_A2 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 > LAT_B1 THEN -- MAX(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 > LAT_B2 THEN -- MAX(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 < LAT_A1 THEN -- MIN(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 < LAT_B2 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 > LAT_B1 THEN -- MAX(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MAX_MIN_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 < LAT_B1 THEN -- MIN(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 > LAT_B2 THEN -- MAX(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MAX_MIN_X FROM DUMMY;
ELSE -- MAX(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MAX_MIN_X FROM DUMMY;
END IF;
END IF;
END IF;
-- Min of Max
IF LAT_A1 > LAT_A2 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A1
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A1 < LAT_B1 THEN -- MIN(LAT_A1, LAT_B1) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A1 < LAT_B2 THEN -- MIN(LAT_A1, LAT_B2) = LAT_A1
SELECT LAT_A1 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A1, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
ELSEIF LAT_A2 > LAT_A1 THEN -- MAX(LAT_A1, LAT_A2) = LAT_A2
IF LAT_B1 > LAT_B2 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B1
IF LAT_A2 < LAT_B1 THEN -- MIN(LAT_A2, LAT_B1) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B1) = LAT_B1
SELECT LAT_B1 INTO MIN_MAX_X FROM DUMMY;
END IF;
ELSEIF LAT_B2 > LAT_B1 THEN -- MAX(LAT_B1, LAT_B2) = LAT_B2
IF LAT_A2 < LAT_B2 THEN -- MIN(LAT_A2, LAT_B2) = LAT_A2
SELECT LAT_A2 INTO MIN_MAX_X FROM DUMMY;
ELSE -- MIN(LAT_A2, LAT_B2) = LAT_B2
SELECT LAT_B2 INTO MIN_MAX_X FROM DUMMY;
END IF;
END IF;
END IF;
IF XA < MAX_MIN_X OR
XA > MIN_MAX_X THEN
SELECT 0 INTO DOESINTERSECT FROM DUMMY;
END IF;
RET_DOESINTERSECT := :DOESINTERSECT;
END;
오래된 스레드를 파내고 그룸드리그의 코드를 수정하는 것...
template <typename T>
struct Point {
T x;
T y;
Point(T x_, T y_) : x(x_), y(y_) {};
};
template <typename T>
inline T CrossProduct(const Point<T>& pt1, const Point<T>& pt2, const Point<T>& pt3)
{
// nb: watch out for overflow
return ((pt2.x - pt1.x) * (pt3.y - pt2.y) - (pt2.y - pt1.y) * (pt3.x - pt2.x));
}
template <typename T>
bool SegmentsIntersect(const Point<T>& a, const Point<T>& b,
const Point<T>& c, const Point<T>& d)
{
return
CrossProduct(a, c, d) * CrossProduct(b, c, d) < 0 &&
CrossProduct(c, a, b) * CrossProduct(d, a, b) < 0;
}
if (SegmentsIntersect(Point<int>(50, 0), Point<int>(50, 100),
Point<int>(0, 50), Point<int>(100, 50)))
std::cout << "it works!" << std::endl;
만약 누군가 C와 같은 속도를 하고 싶다면, 당신은 여러 줄의 교차점을 찾아 이 코드를 사용할 수 있습니다.numba그리고.python
메모
엡실론 인수는 선 거리에 비례해야 합니다.또한, 수입품들은 그저.import numba그리고.import numpy as np
@numba.njit('float64[:,::1], float64[::1], float64', fastmath=True)
def nb_isBetween(line_ab, c, epsilon):
"""
:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param c: point to check like --> np.array([731362.47087528, 9746708.78767337])
:param epsilon:
:return: check if points is on line or not netween point a and b
"""
a, b = line_ab
a_x, a_y = a
b_x, b_y = b
c_x, c_y = c
crossproduct = (c_y - a_y) * (b_x - a_x) - (c_x - a_x) * (b_y - a_y)
# compare versus epsilon for floating point values, or != 0 if using integers
if abs(crossproduct) > epsilon:
return False
dotproduct = (c_x - a_x) * (b_x - a_x) + (c_y - a_y) * (b_y - a_y)
if dotproduct < 0:
return False
squaredlengthba = (b_x - a_x) * (b_x - a_x) + (b_y - a_y) * (b_y - a_y)
if dotproduct > squaredlengthba:
return False
return True
@numba.njit('float64[:,::1], float64[:,::1]', fastmath=True)
def nb_get_line_intersect(line_ab, line_cd):
"""
:param line_ab: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:param line_cd: like --> np.array([[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]])
:return: get point of intersection, if the points in on line ab or cd returns the point if not retunrs 0
"""
A, B = line_ab
C, D = line_cd
# a1x + b1y = c1
a1 = B[1] - A[1]
b1 = A[0] - B[0]
c1 = a1 * (A[0]) + b1 * (A[1])
# a2x + b2y = c2
a2 = D[1] - C[1]
b2 = C[0] - D[0]
c2 = a2 * (C[0]) + b2 * (C[1])
# determinant
det = a1 * b2 - a2 * b1
# parallel line
if det == 0:
return np.array([np.nan, np.nan])
# intersect point(x,y)
x = ((b2 * c1) - (b1 * c2)) / det
y = ((a1 * c2) - (a2 * c1)) / det
#check if x and y area in the line segment interval
if nb_isBetween(line_ab, np.array([x, y]), epsilon=0.001) and nb_isBetween(line_cd, np.array([x, y]), epsilon=0.001):
return np.array([x, y])
else:
return np.array([np.nan, np.nan])
@numba.njit('float64[:, :, ::1], float64[:, :, ::1]', parallel=True, fastmath=True)
def nb_get_line_intersect(m_ramales_lines, interference_lines):
"""
:param m_ramales_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:param interference_lines: like --> np.array([[[731362.47087528, 9746708.78767337], [731297.282, 9746727.286]] , [[731297.282, 9746727.286], [ 731290.048, 9746724.403]]])
:return: m_ramales_lines x interference_lines x 2
"""
#empty matrix to fill
m_ramales_interference = np.empty(shape=(len(m_ramales_lines), len(interference_lines), 2))
for pos1 in range(len(m_ramales_lines)):
line_ab = m_ramales_lines[pos1]
for pos2 in numba.prange(len(interference_lines)):
# interference line
line_cd = interference_lines[pos2].T
# get crossing point
cross_point = nb_get_line_intersect(line_ab.copy(), line_cd.copy())
#fill 2D array
m_ramales_interference[pos1, pos2] = cross_point
return m_ramales_interference
데이터가 선을 정의하는 경우에는 평행하지 않음을 증명하기만 하면 됩니다.이를 위해 계산할 수 있습니다.
alpha = float(y2 - y1) / (x2 - x1).
이 계수가 선 1과 선 2 모두에 대해 같으면 선이 평행하다는 것을 의미합니다.그렇지 않다면, 그것은 그들이 교차할 것이라는 것을 의미합니다.
만약 그것들이 평행하다면 당신은 그것들이 같지 않다는 것을 증명해야 합니다.이를 위해, 당신은 계산합니다.
beta = y1 - alpha*x1
1호선과 2호선에 대한 베타가 같으면 선이 동일한 상태에서 교차한다는 의미입니다.
세그먼트인 경우에도 각 라인에 대해 위에서 설명한 대로 알파 및 베타를 계산해야 합니다.그런 다음 (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();
}
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
}
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
해결되었지만 파이썬으로 해결되지 않은 이유는 무엇입니까...:)
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
반응형
'source' 카테고리의 다른 글
| Excel VBA:수식을 사용하여 여러 셀 자동 채우기 (0) | 2023.07.18 |
|---|---|
| Python에서 문자열과 정수 연결 (0) | 2023.07.18 |
| Python에서 네임스페이스 패키지를 만들려면 어떻게 해야 합니까? (0) | 2023.07.18 |
| 눈금 레이블 값은 숨기지만 축 레이블은 유지 (0) | 2023.07.18 |
| 기존 정보를 보존하면서 다른 유형 및 메시지로 예외 다시 발생 (0) | 2023.07.13 |