User Tools

Site Tools


study:algorithmes:computationalgeometry

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
study:algorithmes:computationalgeometry [2013/07/27 07:17]
darklibra 중간 저장
study:algorithmes:computationalgeometry [2019/02/04 14:26] (current)
Line 11: Line 11:
   * 방향 + 크기 = 단위벡터 + 스칼라   * 방향 + 크기 = 단위벡터 + 스칼라
   * 크기와 방향이 같으면 같은 벡터이다.   * 크기와 방향이 같으면 같은 벡터이다.
 +  * 계산기하의 기본적인 도구이다.
  
 ※ 스칼라(Scalar) ※ 스칼라(Scalar)
Line 17: Line 18:
 ==== 표현 ==== ==== 표현 ====
 좌표평면 상에는 화살표를 이용하여 표시 좌표평면 상에는 화살표를 이용하여 표시
 + ※ 기본적으로 {x: y:} 형태를 하나의 벡터로 정의
 ==== 연산 ==== ==== 연산 ====
 <code clojure> <code clojure>
Line 43: Line 44:
  
 (defn v_add (defn v_add
 +  "​벡터들의 합"
   [& vectors]   [& vectors]
    ​(letfn [(v_a [v1 v2] {:x (+ (:x v1) (:x v2)) :y (+ (:y v1) (:y v2))} )]    ​(letfn [(v_a [v1 v2] {:x (+ (:x v1) (:x v2)) :y (+ (:y v1) (:y v2))} )]
Line 50: Line 52:
  
 (defn v_sub (defn v_sub
 +  "​벡터들의 차"
   [& vectors]   [& vectors]
    ​(letfn [(v_a [v1 v2] {:x (- (:x v1) (:x v2)) :y (- (:y v1) (:y v2))} )]    ​(letfn [(v_a [v1 v2] {:x (- (:x v1) (:x v2)) :y (- (:y v1) (:y v2))} )]
Line 94: Line 97:
 </​code>​ </​code>​
 === 덧셈 & 뺄셈 === === 덧셈 & 뺄셈 ===
-  * 평행사변형법에 의해서 ​정의 ​가능+{{:​study:​algorithmes:​vec_add-sub.jpg?​200|}} 
 +평행사변형을 이용하여 덧셈, 뺄셈을 ​정의 ​할 수 있다.
 === 단위벡터 === === 단위벡터 ===
   * 크기가 1인 벡터로 벡터 정의를 이용하여 구할 수 있다.   * 크기가 1인 벡터로 벡터 정의를 이용하여 구할 수 있다.
   * 단위 벡터 = 벡터 / 벡터 크기(스칼라)   * 단위 벡터 = 벡터 / 벡터 크기(스칼라)
 === 내적 === === 내적 ===
 +{{:​study:​algorithmes:​vec_dot.jpg?​200|}}
   * 임의의 두 벡터를 내적하면 스칼라 값이 된다.   * 임의의 두 벡터를 내적하면 스칼라 값이 된다.
   * 사이각, 직각확인,​ 사영에 주로 사용된다.   * 사이각, 직각확인,​ 사영에 주로 사용된다.
 === 외적 === === 외적 ===
 +{{:​study:​algorithmes:​vec_cross.jpg?​200|}}
   * 3차원에서 정의 가능   * 3차원에서 정의 가능
   * 임의의 두 벡터를 외적하면 벡터가 된다.   * 임의의 두 벡터를 외적하면 벡터가 된다.
Line 116: Line 122:
  
 ===== 예비지식 ===== ===== 예비지식 =====
-==== 점/​직선/​선분 ====+==== 점/​직선/​선분 ​표현 ​====
 원점을 기준으로 좌표평면 상의 x, y좌표를 이용하여 표현한다. 원점을 기준으로 좌표평면 상의 x, y좌표를 이용하여 표현한다.
-=== 점 === +   ​* ​점 해당 점을 끝점으로 가지는 벡터로 표현 
-해당 점을 끝점으로 가지는 벡터로 표현 +   * 직선 ​직선 위의 두 점을 이용하여 표현 
-=== 직선 ​=== +   * 선분 ​직선에 포함된 임의의 선분을 이용해서 표현
-직선 위의 두 점을 이용하여 표현 +
-=== 선분 ​=== +
-직선에 포함된 임의의 선분을 이용해서 표현+
  
 ==== 교차/​거리/​면적 ==== ==== 교차/​거리/​면적 ====
Line 186: Line 189:
  
 === 거리 === === 거리 ===
-== 점과 선 ==+== 점과 ​선 == 
 +사영을 이용하여 점과 선 사이 거리를 구한다. 
 +<code clojure>​ 
 +(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))) ) 
 +</​code>​ 
 +== 점과 선분 == 
 +다음 방법을 이용하여 구할 수 있다. 
 +  - 선분을 직선이라 생각하여 점과 선분이 만나는 점을 구한다. 
 +  - 만나는 점이 선분 위에 있으면 두 점 벡터 거리를 구한다. 
 +  - 만나는 점이 선분 위에 없으면 점에서 가장 가까운 선분 위의 점과의 거리를 구한다. 
 +== 선분과 선분 == 
 +두 선분을 이는 가장 가까운 점은 최도한 두 선분 중 하나의 끝점에서 시작 하므로, 이 끝점과 선분의 거리를 구하면 된다.
  
 === 면적 === === 면적 ===
Line 192: Line 214:
  
 ==== 다각형 ==== ==== 다각형 ====
 +=== 종류 ===
 +  * 볼록 다각형 : 모든 내각이 180도 미만인 다각형
 +  * 오목 다각형 : 180도를 넘는 내각을 갖는 다각형
 +  * 단순 다각형 : 다각형의 경계가 교차하지 않는 다각형
 +=== 면적 ===
 +{{:​study:​algorithmes:​poly_area.jpg?​200|}}
 +  - 임의의 점을 구한다. (= q라고 하며, 편의상 원점을 주로 사용한다.)
 +  - 점q에서 다각형의 모든 꼭지점으로 가상의 선을 그어 삼각형을 만든다.
 +  - 다각형에서 만들어진 모든 삼각형을 외적을 사용하여 면적을 구한다.
 +※ 두 벡터의 외적 순서에 부호가 바뀌므로 한쪽 방향 돌아가면서 면적을 구해야 한다.
 +<code clojure>
 +(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))) )
 +</​code>​
 +=== 내부/​외부 판별 ===
 +임의의 점 p에서 오른쪽(혹은 반대 방향으로) 반 직선을 그어 다각형과 만나는 점의 갯수로 내/​외부를 판단한다. 만나는 점 갯수가 짝수이면 외부, 홀수 이면 내부이다.
 +
 +다음 사항에 대한 처리가 필요하다.
 +  * 다각형의 꼭지점과 일직선상에 있는 경우
 +  * 다각형을 이루는 선분과 일직선상에 있는 경우
 +
 +위 사항은 반직선 각도를 계산시에 약간 변경하는 방법으로 해결한다.
 +※단순 다각형만 되는 방법이다.
 +<code clojure>
 +(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)) )
 +</​code>​
 ===== 문제 : 핀볼 시뮬레이션 ===== ===== 문제 : 핀볼 시뮬레이션 =====
 +<code clojure>
 +(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))
 +)
 +</​code>​
 ===== 문제 : 보물섬 ===== ===== 문제 : 보물섬 =====
 +<code clojure>
 +(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)) )
 +</​code>​
 ===== 문제 : 너드인가?​ 너드가 아닌가? ===== ===== 문제 : 너드인가?​ 너드가 아닌가? =====
 +<code clojure>
 +(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)))) )
 +</​code>​
 ===== 참고자료 ===== ===== 참고자료 =====
study/algorithmes/computationalgeometry.txt · Last modified: 2019/02/04 14:26 (external edit)