[알고리즘2] Collinear Point 구현 - 실습

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Collinear Points

4개 이상 점 연결하는 maximal한 직선을 모두 찾는 코드이다.

N개 점의 (x, y) 좌표가 입력으로 주어졌을 때, 4개 이상 점을 연결하는 maximal한 직선을 모두 찾으면 된다.

 

▶Collinear Points 탐지방법

하나하나 비교하면서 하는 Brute Force방식을 사용할 수 있다.

하지만 시간 복잡도 측면에서 좋지 못한 코드가 된다.

 

정렬을 활용한 더 효율적인 방법을 사용하면 된다.

각 점 p에 대해, p가 다른 모든 점과 이루는 기울기를 계산해, 기울기를 key로 정렬한다.

정렬 결과에서 3개 이상의 인접한 점이 같은 기울기를 갖는다면 이들은 collinear이다.

 

N개의 점 각각에 대해 다른 모든 점을 정렬(~NlogN)하므로 ~N^2 * logN이 된다.

 

 

▶프로그램 구현 조건

입력 points : xy 좌표계에 속한 점의 list

     points는 tuple (x, y)의 리스트임 (예: [(3, 2), (4, -1), (0, 0), (-2, 2)])

     points에 속한 점은 모두 좌표가 서로 다름 x/y 값 둘 다 일치하는 점은 입력으로 주어지지 않는다.

반환 값: 4개 이상 (≥ 4) 점 연결하는 maximal한 직선 모두 리스트에 담아 반환한다.

     양 끝이 p, q인 직선(p < q)은 양 끝점 좌표를 4-tuple (px, py, qx, qy) 형식으로 나타낸다.

     이때 두 점 중 더 작은 점이 p, 더 큰 점이 q이다.

     두 점의 대소 관계 따질 때는 x좌표 먼저 비교하고, x좌표 같으면 y좌표 비교한다.

     둘 이상 직선을 반환할 때는 px 작은 직선 먼저 반환하며, px 같다면 py→qx→qy 순으로 비교한다.

정렬 위해서는 sorted() 혹은 list.sort() 함수 활용한다.

 

def collinearPoints(points):
    def check(a, b):
        if b[1] - a[1] == 0:
            return 0
        elif b[0] - a[0] == 0:
            return float('inf')
        else:
            return (b[1] - a[1]) / (b[0] - a[0])

    answer = []
    points.sort(key=lambda x: (x[0], x[1]))
    for i in range(len(points)):
        li = []
        for j in range(len(points)):
            if i != j:
                li.append([points[j][0], points[j][1], check(points[i], points[j])])
        li.sort(key=lambda x: x[2])
        cnt = 0
        cur = li[0][2]
        for j in range(1, len(li)):
            if li[j][2] == cur:
                cnt += 1
                if j == len(li) - 1 and cnt >= 2:
                    ans = [[points[i][0], points[i][1]], [li[j][0], li[j][1]], [li[j - cnt][0], li[j - cnt][1]]]
                    ans.sort(key=lambda x: (x[0], x[1]))
                    ans2 = (ans[0][0], ans[0][1], ans[2][0], ans[2][1])
                    if ans2 not in answer:
                        answer.append(ans2)
            else:
                if cnt >= 2:
                    # j번째는 동일하지 않기때문에 j-1
                    ans = [[points[i][0], points[i][1]], [li[j - 1][0], li[j - 1][1]], [li[j - 1 - cnt][0], li[j - 1 - cnt][1]]]
                    ans.sort(key=lambda x: (x[0], x[1]))
                    ans2 = (ans[0][0], ans[0][1], ans[2][0], ans[2][1])
                    if ans2 not in answer:
                        answer.append(ans2)
                cnt = 0
                cur = li[j][2]

    return answer


if __name__ == "__main__":
    print(collinearPoints([(19000, 10000), (18000, 10000), (32000, 10000), (21000, 10000), (1234, 5678), (14000, 10000)]))
    print(collinearPoints([(10000, 0), (0, 10000), (3000, 7000), (7000, 3000), (20000, 21000), (3000, 4000), (14000, 15000), (6000, 7000)]))
    print(collinearPoints([(0, 0), (1, 1), (3, 3), (4, 4), (6, 6), (7, 7), (9, 9)]))
    print(collinearPoints([(1, 0), (2, 0), (3, 0), (4, 0), (5, 0), (6, 0), (8, 0)]))
    print(collinearPoints([(7,0), (14,0), (22,0), (27,0), (31,0), (42,0)]))
    print(collinearPoints([(12446, 18993), (12798, 19345), (12834, 19381), (12870, 19417), (12906, 19453), (12942, 19489)]))
    print(collinearPoints([(1, 1), (2, 2), (3, 3), (4, 4), (2, 0), (3, -1), (4, -2), (0, 1), (-1, 1), (-2, 1), (-3, 1), (2, 1), (3, 1), (4, 1), (5, 1)]))