기하문제 팁: 직선-직선 교점 구하기 등

  • pjsdream2001
    pjsdream2001

    안녕하세요^^

    기하문제 푸는데 도움이 될만한 내용들을 작성해봤는데, 이번에 월파 나가는 친구들한테 물어봤는데 대부분 모르는 내용이라고 하더라구요. 그 친구들 포함해서 알고스팟분들과도 공유해보고 싶어서 글을 쓰게 되었습니다.

    알려드리고 싶은 내용은 Homogeneous Coordinate System 입니다.
    연습하시면 각종 수식(직선-직선 교점 등)을 손으로 계산하지 않고도 쉽게 구할 수 있을 것입니다.

    글 내용이 도움이 됐으면 좋겠습니다.
    중복이면 알려주세요!!

    #1. 내적의 의미

    엄밀한 정의에 의하면 dot product는 내적의 한 종류인걸로 알고잇습니다. 그런데 습관적으로 dot product를 내적이라고 쓰게 되네요.
    내적의 의미를 어떻게 해석하느냐는 개인 취향인것 같습니다. 저는 "내적 = 특정 방향으로 측정한 거리" 라고 해석하는데, 이렇게 해석하면 기하문제를 직관적으로 생각하기 쉬운 것 같습니다.

    특히 벡터 v가 unit vector 즉 |v| = 1 이면, 내적은 v방향으로의 거리와 같아져서, 직관적으로 내적의 의미를 해석하는데 도움이 됩니다.

    #2. 직선 ax + by + c = 0 의 의미

    저는 직선 표현을 항상 ax + by + c = 0 의 꼴로 사용합니다. 큰 장점 두가지를 꼽자면

    • 표현하지 못하는 직선이 없습니다. 따라서 코딩할 때 예외처리가 줄어듭니다. (예를들어 y = ax + b 꼴의 직선은 y축에 평행한 직선을 표현하지 못합니다.)
    • 반평면 표현이 쉽습니다. 등호(=)를 부등호(< 또는 >)로 바꾸면 됩니다.

    #3. 두 점을 지나는 직선

    두 점 (x1, y1)과 (x2, y2)가 주어졌을 때, 두 점을 지나는 직선 ax + by + c = 0 을 구하는 방법입니다.

    #4. 두 직선의 교점

    #5. 점과 직선의 표현

    이렇게 triplet으로 점과 직선을 표현하는 것을 Homogeneous Coordinate System 이라고 합니다.

    #6. 회전변환과 평행이동

    원래 2차원 점의 평행이동은 linear transformation이 아닙니다. 원점을 원점으로 보내지 않기 때문인데요. 이 문제점을 해결하는 것이 Homogeneous Coordinate System 입니다.
    Homogeneous Coordinate System 에서는 2차원 점을 3차원으로 표현합니다. 변환행렬도 3x3으로 나타내면, 평행이동마저 linear transformation이 됩니다.

    #7. 코드

    저는 점과 직선을 표현하는 자료구조를 이렇게 짭니다.

    struct point {
    double x, y, z;
    point(double x, double y, double z = 1.) : x(x), y(y), z(z) {}

    // 마지막 성분을 1로 바꿈
    point projection() { return point(x/z, y/z); }

    // 외적
    point operator * (point& rhs) { return point( y * rhs.z - z * rhs.y, z * rhs.x - x * rhs.z, x * rhs.y - y * rhs.x ); }
};

// 두 점을 지나는 직선
point l = p1 * p2;

// 두 직선의 교점
point p = l1 * l2;
if (p.z != 0) p = p.projection();

    8년 전
11개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    좋은 글 감사합니다! 잘 정리된 것 같아요


    8년 전 link
  • pjsdream2001
    pjsdream2001

    kcm님이 학교 동아리에 올린 글을 보고 처음 배웠습니다 꾸벅


    8년 전 link
  • riceluxs1t
    riceluxs1t

    좋은글 감사합니다


    8년 전 link
  • JongMan
    JongMan

    와 멋져요~


    8년 전 link
  • Beginner
    Beginner

    좋은 글 감사해요 :)


    8년 전 link
  • rlatkddn212
    rlatkddn212

    와 손글씨가 친근하고 좋아용 ㅎ.ㅎ


    8년 전 link
  • rlatkddn212
    rlatkddn212

    이제 보고 있는데 오른쪽이 조금 짤렸네용..


    8년 전 link
  • veckal
    veckal

    감사합니다!


    8년 전 link
  • chaos.kite
    chaos.kite

    좋은 글 감사합니다.
    그런데 크롬 브라우져에서 그림 오른쪽이 조금 짤려보이는데 복사해서 그림판에서 보니 다 보이네요... ^^


    8년 전 link
  • sugardoll87
    sugardoll87

    두번째 그림이 잘못된것 같아요. ax+by+c=0에서 는 normal vector가 아니라 directional vector(직선이 뻗어 있는 방향과 동일)이지 않나요?


    8년 전 link
  • sugardoll87
    sugardoll87

    ax+by+c = 0이 평면이라면 (a,b)가 normal vector가 맞지만, 직선인 경우는 다른 것 같습니다


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.