복붙노트

[PYTHON] 두 세그먼트가 교차하는지 어떻게 확인할 수 있습니까?

PYTHON

두 세그먼트가 교차하는지 어떻게 확인할 수 있습니까?

2 개의 세그먼트가 교차하는지 어떻게 확인할 수 있습니까?

다음 데이터가 있습니다.

Segment1 [ {x1,y1}, {x2,y2} ]
Segment2 [ {x1,y1}, {x2,y2} ]

파이썬에서 2 라인이 교차하는지 탐지하기 위해 작은 알고리즘을 작성해야합니다.

최신 정보:

해결법

  1. ==============================

    1.선 방정식은 다음과 같습니다.

    선 방정식은 다음과 같습니다.

    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) )) ||
     (Xa > min( max(X1,X2), max(X3,X4) )) )
    return false; // intersection is out of bound
else
    return true;

    이 외에도 시동시 제공되는 4 개의 포인트 중 2 개가 같지 않아 모든 테스트를 피할 수 있는지 확인할 수 있습니다.

  2. ==============================

    2.User @ i_4_got는 파이썬에서 매우 효율적인 솔루션으로이 페이지를 가리 킵니다. 나는 편의성을 위해 여기에 그것을 재현한다.

    User @ i_4_got는 파이썬에서 매우 효율적인 솔루션으로이 페이지를 가리 킵니다. 나는 편의성을 위해 여기에 그것을 재현한다.

    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)
  3. ==============================

    3.세그먼트가 교차하는 곳을 정확히 계산할 필요는 없지만 교차하는 부분 만 이해합니다. 이렇게하면 솔루션이 단순 해집니다.

    세그먼트가 교차하는 곳을 정확히 계산할 필요는 없지만 교차하는 부분 만 이해합니다. 이렇게하면 솔루션이 단순 해집니다.

    아이디어는 하나의 세그먼트를 "앵커"로 처리하고 두 번째 세그먼트를 2 포인트로 분리하는 것입니다. 이제 각 점의 상대적 위치를 "고정 된"세그먼트 (OnLeft, OnRight 또는 Collinear)로 찾아야합니다. 두 지점 모두에 대해 이렇게 한 후 점 중 하나가 OnLeft이고 다른 점이 OnRight인지 확인합니다 (부적절한 교차점도 포함하려는 경우 Collinear 위치를 포함 할 수도 있음).

    그런 다음 앵커 및 분리 된 세그먼트의 역할로 프로세스를 반복해야합니다.

    점 중 하나가 OnLeft이고 다른 하나가 OnRight 인 경우에만 교차가 존재합니다. 가능한 경우 각각에 대한 예제 이미지가있는 자세한 설명은이 링크를 참조하십시오.

    그러한 방법을 구현하는 것은 교차점을 찾는 메소드를 실제로 구현하는 것보다 훨씬 쉽습니다 (많은 코너 케이스도 처리해야합니다).

    최신 정보

    다음 함수는 아이디어를 설명해야합니다 (출처 : C에서의 Computational Geometry). 참고 :이 샘플에서는 정수 사용을 가정합니다. 대신에 부동 소수점 표현을 사용하고 있다면 (분명히 상황을 복잡하게 만들 수 있음) "평등"(주로 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);
}

    물론 이러한 함수를 사용할 때는 각 세그먼트가 다른 세그먼트와 "사이에"있는지 확인해야합니다 (이 세그먼트는 유한 세그먼트이므로 무한한 선이 아닙니다).

    또한,이 기능을 사용하여 적절하거나 부적절한 교차로를 파악할 수 있습니다.

  4. ==============================

    4.두 세그먼트가 종점 A, B 및 C, D를 갖는다 고 가정합니다. 교차점을 결정하는 수치 적으로 강력한 방법은 네 가지 결정 요인의 부호를 확인하는 것입니다.

    두 세그먼트가 종점 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

  5. ==============================

    5.Liran 's와 Grumdrig의 탁월한 해답은 닫힌 세그먼트가 교차하는지 확인하는 완벽한 파이썬 코드입니다. 동일 선상의 세그먼트, 축 Y와 평행 한 세그먼트, 퇴화 된 세그먼트 (악마는 세부 사항)에 대한 작업. 정수 좌표를 가정합니다. 부동 소수점 좌표는 포인트 평등 테스트에 대한 수정이 필요합니다.

    Liran 's와 Grumdrig의 탁월한 해답은 닫힌 세그먼트가 교차하는지 확인하는 완벽한 파이썬 코드입니다. 동일 선상의 세그먼트, 축 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
  6. ==============================

    6.두 개의 선분이 있습니다. 엔드 포인트 A & B에 의해 하나의 세그먼트를 정의하고 엔드 포인트 C & D에 의해 두 번째 세그먼트를 정의하십시오. 세그먼트 경계 내에서 교차해야 함을 나타내는 멋진 트릭이 있습니다. (선 자체가 선분 경계를 넘어 교차 할 수 있으므로 조심해야하며 좋은 선은 평행선을 감시합니다.)

    두 개의 선분이 있습니다. 엔드 포인트 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가 구별되는 것입니까?)

    같은 무한 선을 따라 놓여있는 선분이나 다른 선분 자체에 실제로있는 선분에 대해 걱정할 필요가 있습니다. 좋은 코드는 모든 가능한 문제를 해결할 것입니다.

  7. ==============================

    7.두 점이 선분의 반대쪽에 있는지 확인하는 C 코드가 있습니다. 이 코드를 사용하면 두 세그먼트가 교차하는지 확인할 수 있습니다.

    두 점이 선분의 반대쪽에 있는지 확인하는 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));

    }

  8. ==============================

    8.다음은 닫힌 세그먼트가 교차하는지 여부를 확인하는 또 다른 파이썬 코드입니다. 그것은 http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/에있는 C ++ 코드의 재 작성된 버전입니다. 이 구현은 모든 특수한 경우 (예 : 모든 점 colinear)를 포함합니다.

    다음은 닫힌 세그먼트가 교차하는지 여부를 확인하는 또 다른 파이썬 코드입니다. 그것은 http://www.cdn.geeksforgeeks.org/check-if-two-given-line-segments-intersect/에있는 C ++ 코드의 재 작성된 버전입니다. 이 구현은 모든 특수한 경우 (예 : 모든 점 colinear)를 포함합니다.

    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))
  9. ==============================

    9.세그먼트 AB 및 CD의 경우 CD의 기울기를 찾습니다.

    세그먼트 AB 및 CD의 경우 CD의 기울기를 찾습니다.

    slope=(Dy-Cy)/(Dx-Cx)

    A와 B에 걸쳐 CD를 연장하고 CD까지의 거리를 똑바로 세우십시오.

    dist1=slope*(Cx-Ax)+Ay-Cy
dist2=slope*(Dx-Ax)+Ay-Dy

    반대편에 있는지 확인하십시오.

    return dist1*dist2<0
  10. ==============================

    10.선의 교차점을 찾으려는 언급은 없으므로 문제를 해결하는 것이 더 간단 해집니다. 교차점이 필요한 경우 OMG_peanuts의 대답은 더 빠른 접근 방식입니다. 그러나 선이 교차하는지 여부를 찾고 싶다면 선 방정식 (ax + by + c = 0)을 사용하면됩니다. 접근 방식은 다음과 같습니다.

    선의 교차점을 찾으려는 언급은 없으므로 문제를 해결하는 것이 더 간단 해집니다. 교차점이 필요한 경우 OMG_peanuts의 대답은 더 빠른 접근 방식입니다. 그러나 선이 교차하는지 여부를 찾고 싶다면 선 방정식 (ax + by + c = 0)을 사용하면됩니다. 접근 방식은 다음과 같습니다.

  11. ==============================

    11.좋은 스위프트 솔루션을 제공하겠다고 생각했습니다.

    좋은 스위프트 솔루션을 제공하겠다고 생각했습니다.

    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

}
  12. ==============================

    12.우리는 벡터를 활용하여이를 해결할 수도 있습니다.

    우리는 벡터를 활용하여이를 해결할 수도 있습니다.

    세그먼트를 [시작, 끝]으로 정의합시다. 둘 다 길이가 0이 아닌 두 개의 세그먼트 [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]]

    여기서 p + t * r = u * q에서 t와 u를 계산하여 교차점을 찾을 수 있습니다. 방정식을 조금 가지고 노는 후에, 우리는 얻는다 :

    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
  13. ==============================

    13.데이터가 라인을 정의하는 경우 병렬이 아니라는 것을 증명해야합니다. 이렇게하려면 다음을 계산할 수 있습니다.

    데이터가 라인을 정의하는 경우 병렬이 아니라는 것을 증명해야합니다. 이렇게하려면 다음을 계산할 수 있습니다.

    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)보다 작지 않은지 확인해야합니다.

  14. ==============================

    14.세그먼트에 놓인 선의 교차점을 계산합니다 (기본적으로 선형 방정식 시스템을 푸는 것을 의미 함). 그런 다음 세그먼트의 시작점과 끝점 사이에 있는지 확인합니다.

    세그먼트에 놓인 선의 교차점을 계산합니다 (기본적으로 선형 방정식 시스템을 푸는 것을 의미 함). 그런 다음 세그먼트의 시작점과 끝점 사이에 있는지 확인합니다.

  15. ==============================

    15.이것은 내가 AS3에 대해 가지고있는 것인데, 파이썬에 대해 많이 알지 못하지만 개념은 거기에있다.

    이것은 내가 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();
    }
  16. ==============================

    16.JAVA로 구현되었습니다. 그러나 그것이 서로 선형 라인 (서로 L1 (0,0) (10,10) L2 (1,1) (2,2) 내에 존재하는 선 세그먼트라고도 함)

    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
  17. ==============================

    17.해결되었지만 여전히 파이썬이 아닌 이유는 무엇입니까? :)

    해결되었지만 여전히 파이썬이 아닌 이유는 무엇입니까? :)

    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

    18. from https://stackoverflow.com/questions/3838329/how-can-i-check-if-two-segments-intersect by cc-by-sa and MIT license

'PYTHON' 카테고리의 다른 글

[PYTHON] matplotlib에서 밀도로 채색 된 분산 형 플롯을 만들려면 어떻게해야합니까?  (0) 2018.10.03
[PYTHON] 장고 모델로 csv 데이터를 가져 오는 방법  (0) 2018.10.03
[PYTHON] 파이썬 함수를 피클 링하는 쉬운 방법이 있습니까? 아니면 코드를 직렬화할까요?  (0) 2018.10.03
[PYTHON] 파이썬에서 두 개의 사전 비교하기  (0) 2018.10.03
[PYTHON] HttpResponse를 장고로 스트리밍하는 법  (0) 2018.10.03
,

티스토리툴바