User Tools

Site Tools


study:algorithmes:computationalgeometry

계산기하(Computational Geometry)

계산기하란?

정의

기하학적 도형을 다루는 알고리즘

※ 기하학(Geometry)

  • Geographie와 Measurement 합성어
  • 도형의 양을 측정, 공간의 수학적 특징

벡터(Vector)

정의 및 특징

  • 방향 + 크기 = 단위벡터 + 스칼라
  • 크기와 방향이 같으면 같은 벡터이다.
  • 계산기하의 기본적인 도구이다.

※ 스칼라(Scalar) 크기만 가지는 양

표현

좌표평면 상에는 화살표를 이용하여 표시 ※ 기본적으로 {x: y:} 형태를 하나의 벡터로 정의

연산

(defn v_iter_compa
   "비교 반복자"
   [fun b f & ss]
   (let [lss (first ss)
         sv (first lss)]
   (if (and (> (count lss) 0) b)
       (v_iter_compa fun (fun f sv) sv (rest lss))
       b)) )
 
(defn v_same?
   "입력된 벡터정보가 같은면 true 아니면 false" 
   [s_vec & vectors]
   (v_iter_compa (fn [x y] (and (= (:x x) (:x y)) (= (:y x) (:y y)))) true s_vec vectors) )
 
(defn v_small? 
   "오른쪽에 있는 벡터를 기준으로 작으면 true, 크면 false"
   [s_vec & vectors]
   (v_iter_compa 
      (fn [x y] (if (not= (:x x) (:x y)) (< (:x x) (:x y)) (< (:y x) (:y y)))) 
      true s_vec vectors) )
 
(defn v_add
  "벡터들의 합"
  [& vectors]
   (letfn [(v_a [v1 v2] {:x (+ (:x v1) (:x v2)) :y (+ (:y v1) (:y v2))} )]
   (if (< (count vectors) 2) 
       (first vectors)
       (reduce v_a vectors))) )
 
(defn v_sub
  "벡터들의 차"
  [& vectors]
   (letfn [(v_a [v1 v2] {:x (- (:x v1) (:x v2)) :y (- (:y v1) (:y v2))} )]
   (if (< (count vectors) 2) 
       (first vectors)
       (reduce v_a vectors))) )
(defn v_n_multi 
  [n vec]
  {:x (* n (:x vec)) :y (* n (:y vec))} )
 
(defn v_norm 
   "벡터 길이, 피타고라스 정리를 이용하여 길이 계산"
   [vec] 
   (Math/hypot (:x vec) (:y vec)) )
 
(defn v_normalize 
   "벡터 단위벡터 반환"
   [vec]
   (let [vec_norm (v_norm vec)]
     {:x (/ (:x vec) vec_norm), :y (/ (:y vec) vec_norm)}) )
 
(defn v_polar 
  "벡터 극각도, x축 양수 방향 부터 벡터가 떨어진 거리."
  [vec] 
  (mod (+ (Math/atan2 (:y vec) (:x vec)) (* 2 PI)) (* 2 PI)) )
 
(defn v_dot 
  "벡터 내적"
  [x y] 
  (+ (* (:x x) (:x y)) (* (:y x) (:y y))))
 
(defn v_project 
  "벡터 사영"
  [x y]
  (let [r (v_normalize y)] 
   (v_n_multi (v_dot r x) r))
)
 
(defn v_cross
  "벡터 외적"
  [x y]
  (- (* (:x x) (:y y)) (* (:x y) (:y x))) )

덧셈 & 뺄셈

평행사변형을 이용하여 덧셈, 뺄셈을 정의 할 수 있다.

단위벡터

  • 크기가 1인 벡터로 벡터 정의를 이용하여 구할 수 있다.
  • 단위 벡터 = 벡터 / 벡터 크기(스칼라)

내적

  • 임의의 두 벡터를 내적하면 스칼라 값이 된다.
  • 사이각, 직각확인, 사영에 주로 사용된다.

외적

  • 3차원에서 정의 가능
  • 임의의 두 벡터를 외적하면 벡터가 된다.
  • 면적, 방향 판별에 주로 사용
(defn ccw 
   "두 벡터 방향 판별.
    벡터 x를 기준으로 양수면 반시계 방향 180도 이내,
    음수면 시계방향으로 180도 이내에 존재."
   ([x y] (v_cross x y))
   ([s x y] (ccw (v_sub x s) (v_sub y s))) )

예비지식

점/직선/선분 표현

원점을 기준으로 좌표평면 상의 x, y좌표를 이용하여 표현한다.

  • 점 : 해당 점을 끝점으로 가지는 벡터로 표현
  • 직선 : 직선 위의 두 점을 이용하여 표현
  • 선분 : 직선에 포함된 임의의 선분을 이용해서 표현

교차/거리/면적

교차

직선과 직선
(defn lineIntersection
   "직선과 직선교차 좌표를 구한다"
   [a b c d] 
   (let [det (v_cross (v_sub b a) (v_sub d c))]
   (if (not= 0 (Math/abs det)) 
    (v_add a (v_n_multi (/ (v_cross (v_sub c a) (v_sub d c)) (double det)) (v_sub b a) )))) )

직선을 점과 방향으로 표현 하면 간편하게 교차 방정식을 구할 수 있다.

선분과 선분
(defn parallelSegements 
   "평행한 두 선분이 한점에서 겹치는지 확인"
   [a b c d]
   (cond (v_small? b a) (parallelSegements b a c d)
         (v_small? d c) (parallelSegements a b d c)
         :else (if (or (not= 0 (ccw a b c)) (v_small? b c) (v_small? d a))
             nil
             (if (v_small? a c) c a)) ) )
 
(defn inBoundingRectangle 
   "점 s가 선분 xy 위에 있는지 확인"
   [s x y] 
   (if (v_small? y x) 
       (inBoundingRectangle s y x) 
       (or (v_same? s x y) (and (v_small? x s) (v_small? s y)))) )
 
(defn segmentIntersection 
  "선분 ab와 cd가 교차 하는지 확인. 일직선 포함."
  [a b c d] 
  (let [v (lineIntersection a b c d)]
    (if (nil? v) 
     (parallelSegements a b c d) 
     (and (inBoundingRectangle v a b) (inBoundingRectangle v c d)))) )

직선과 직선 교차 함수에 다음 두 조건을 추가하면 구할 수 있다.

  • 교점이 두 선분 위에 있는가?
  • 두 선분이 일직선 위에 있을때
(defn segmentIntersects 
  "ccw를 이용한 교차 확인. 교차점 필요 없이 교차 여부만 확인"
  [a b c d]
  (let [ab (* (ccw a b c) (ccw a b d)) 
        cd (* (ccw c d a) (ccw c d b))]
    (if (and (== 0 ab) (== 0 cd)) 
       (let [ra (if (v_small? a b) a b) 
             rb (if (v_small? a b) b a) 
	     rc (if (v_small? c d) c d) 
	     rd (if (v_small? c d) d c)]
	 (not (or (v_small? rb rc) (v_small? rd ra))) ) 
       (and (>= 0 ab) (>= 0 cd)))) )

단순히 교차 여부를 확인 할려면 ccw를 이용하면 좀 더 쉽게 구현 할 수 있다.

거리

점과 직선

사영을 이용하여 점과 선 사이 거리를 구한다.

(defn perpendicularFoot
   "점과 선분 수선의 발" 
   [s x y] 
  (v_add x (v_project (v_sub s x) (v_sub y s))) )
 
(defn pointToLine 
   "점과 직선 사이 거리"
   [s x y] 
   (v_norm (v_sub s (perpendicularFoot s x y))) )
점과 선분

다음 방법을 이용하여 구할 수 있다.

  1. 선분을 직선이라 생각하여 점과 선분이 만나는 점을 구한다.
  2. 만나는 점이 선분 위에 있으면 두 점 벡터 거리를 구한다.
  3. 만나는 점이 선분 위에 없으면 점에서 가장 가까운 선분 위의 점과의 거리를 구한다.
선분과 선분

두 선분을 이는 가장 가까운 점은 최도한 두 선분 중 하나의 끝점에서 시작 하므로, 이 끝점과 선분의 거리를 구하면 된다.

면적

두 벡터를 외적하여 2로 나누면 면적이 된다.

다각형

종류

  • 볼록 다각형 : 모든 내각이 180도 미만인 다각형
  • 오목 다각형 : 180도를 넘는 내각을 갖는 다각형
  • 단순 다각형 : 다각형의 경계가 교차하지 않는 다각형

면적

  1. 임의의 점을 구한다. (= q라고 하며, 편의상 원점을 주로 사용한다.)
  2. 점q에서 다각형의 모든 꼭지점으로 가상의 선을 그어 삼각형을 만든다.
  3. 다각형에서 만들어진 모든 삼각형을 외적을 사용하여 면적을 구한다.

※ 두 벡터의 외적 순서에 부호가 바뀌므로 한쪽 방향 돌아가면서 면적을 구해야 한다.

(defn area 
   "다각형 면적 계산"
   [& vec]
   (defn iter-area [av f & vec]
      (let [lvec (first vec)
            fv (first lvec)]
       (cond (= (count lvec) 0) (Math/abs (/ av 2.0))
             (= (count lvec) 1) (iter-area (+ av (v_cross fv f)) f (rest lvec))
             :else (iter-area (+ av (v_cross fv (first (rest lvec)))) f (rest lvec)))))
   (if (> (count vec) 2) 
      (Math/abs (iter-area 0 (first vec) vec))) )

내부/외부 판별

임의의 점 p에서 오른쪽(혹은 반대 방향으로) 반 직선을 그어 다각형과 만나는 점의 갯수로 내/외부를 판단한다. 만나는 점 갯수가 짝수이면 외부, 홀수 이면 내부이다.

다음 사항에 대한 처리가 필요하다.

  • 다각형의 꼭지점과 일직선상에 있는 경우
  • 다각형을 이루는 선분과 일직선상에 있는 경우

위 사항은 반직선 각도를 계산시에 약간 변경하는 방법으로 해결한다. ※단순 다각형만 되는 방법이다.

(defn inside? 
  "점p가 다각형 내부/외부 판별. 단 단순다각형일 경우만 가능"
  [p & vec]
  (let [cross-count (fn [cross x y] 
                        (let [at (+ (/ (* (- (:x y) (:x x)) (- (:y p) (:y x))) 
                                       (- (:y y) (:x y))) (:x x))]
                         (if (and (not= (> (:y p) (:y x)) (> (:y p) (:y y))) 
                                  (< (:x p) at)) 
                             (inc cross)
                             cross)))
        let-inside? (fn [x y] (conj {:cross (cross-count (:cross x 0) x y)} y))] 
  (if (even? (:cross (let-inside? (reduce let-inside? vec) (first vec)) 0))
      false 
      true)) )

문제 : 핀볼 시뮬레이션

(defn solve2 
   "핀볼-2차 방정식을 푼다"
   [a b c]
   (let [d  (- (* b b) (* 4 a c))]
        (cond (= 0 d) (/ (- b) (* 2 a))
              (< 0 d) (sort (for [o [+ -]] (/ (o (- b) (Math/sqrt d)) (* 2 a)))))))
 
(defn hit-circle 
   "핀볼 시뮬레이션 충돌 확인"
   [here dir center radius]
   (let [a (v_dot dir dir)
         b (* 2 (v_dot dir (v_sub here center)))
         c (- (- (+ (v_dot center center) (v_dot here here)) (* 2 (v_dot here center))) 
              (* radius radius) )
         sol (first (solve2 a b c))]
       (if (or (nil? sol) (> 0 sol)) 
           INFTY
           sol)) )
 
(defn reflect
  "핀볼 시뮬레이션 반사처리"
  [v_dir v_center v_contact]
  (v_normalize (v_sub v_dir (v_n_multi 2 (v_project v_dir (v_sub v_contact v_center))))) )
 
"핀볼 자료"
(def center [{:x 22 :y 40} {:x 61 :y 26} {:x 19 :y 78} {:x 51 :y 86} {:x 84 :y 57}])
(def radius [12 20 21 7 15])
 
(defn iter_pinball_simulate
  "핀볼 시뮬레이터 반복자"
  [here dir hit_count result max_hit_count]
   (if (< hit_count max_hit_count)
       (let [cands (sort-by :time < (for [x (range 0 (count center))]
                 {:circle x :time (hit-circle here dir (center x) (+ 1 (radius x)))} ))
            cand (first cands)]
        (if (or (nil? cand) (= INFTY (:time cand)))
            result
            (let [contact (v_add (v_n_multi (:time cand) dir) here)]
               (recur contact (reflect dir (center (:circle cand)) contact) (inc hit_count) (conj result (:circle cand))  max_hit_count))))
        result))
 
(defn pinball_simulate
  "핀볼 시뮬레이션"
  [here dir]
  (reverse (iter_pinball_simulate here (v_normalize dir) 0 () 100))
)

문제 : 보물섬

(defn cut-poly
  "반평면과 단순 다각형의 교집합을 구한다. 반평면은 벡터 a에서 b로 가는직선 왼쪽이다. p는 vectors이다."
  [p a b] 
  (let [poly-size (count p)
       cal-index (vec (take (+ 1 poly-size) (cycle (range poly-size))))
       inside (vec (for [x (range poly-size)] (>= (ccw a b (p x)) 0)))]
     (for [i (range poly-size)]
       (conj (lineIntersection (p (cal-index i)) (p (cal-index (+ 1 i))) a b )
             (if (inside i) (p i)))
      )) )
 
(defn intersection
   "보물섬 문제"
   [vectors x1 y1 x2 y2]
   (let [a {:x x1 :y y1}
         b {:x x1 :y y2}
         c {:x x2 :y y2}
         d {:x x1 :y y2}]
        (cut-poly (cut-poly (cut-poly (cut-poly vectors a b) b c) c d) d a)) )

문제 : 너드인가? 너드가 아닌가?

(defn fn-left
   "가장 왼쪽에 있는 위치를 찾는다."
   [v vecs]
   (let [in-fn (fn [x y] 
                   (let [cross (ccw v x y)
                         dist (- (v_norm (v_sub x v)) (v_norm (v_sub y v)))]
                     (if (or (= 0 cross) (and (= 0 cross) (> 0 dist)))
                         x
                         y)))]
        (reduce in-fn vecs)) )
 
(defn left-wrap
   "단순 다각형 포장"
   [vecs]
   (let [pivot (reduce (fn [x y] (if (and (< (:x x) (:x y)) (< (:y x) (:y y))) x y)) vecs)
         store (pivot)] 
        (loop [ph pivot next (fn-left pivot vecs)]
              (if (= pivot next)
                  store
                  (do (conj store next)
                      (recur next (fn-left next vecs)))))) )
(defn polygonIntersects
   "두 다각형 교차 확인. 확인 필요"
   [poly-p poly-g] 
   (let [count-g (count poly-g)
         index-g (vec (take (+ 1 count-g) (cycle (range count-g)))) 
         in-fn (fn [p1 p2]
                   (let [b (:result p1 true)]
                        (for [n (range count-g)] )))]
        (:result (in-fn (reduce in-fn poly-p) (:first poly-p)))) )

참고자료

study/algorithmes/computationalgeometry.txt · Last modified: 2019/02/04 14:26 (external edit)