[F#] 귀갑을 찢는 게으른 설치

내가 관련된 건축 구조 세계에서'구갑비례'라는 단어가 있다.
구체적으로'어떤 다각형의 임의적인 위치에 대해 다각형을 구성하는 변에서 가장 가까운 변에 속하도록 다각형을 각 변의 지배구역으로 분할한다'는 문제다.
계산하면 각 변에 2등분선을 긋지만 다각형이 복잡하면 고민이다.
그래서 이번에 우리는 다각형을 그물 모양으로 나누어 각 변의 거리를 계산하여 구역을 나누는 알고리즘을 게으름 피우게 만들었다.

처리 프로그램

다음 다각형을 고려합니다.

이것을 덮을 수 있는 그물 모양을 만들어라.

망상물의 중심이 다각형 안에 있는 대상만을 대상으로 한다.

각 망상물과 다각형의 각 변의 거리를 계산하여 최소 거리의 변과 같은 색깔로 착색하고 구역을 구분한다.

결과적으로 기하학적 영역의 분할은 약간 힘에 의존했다.

해설

한 걸음 한 걸음 쫓아가면 별일 아니지만, 수학 지식을 많이 잊어버려 고전한다.
아래의 알고리즘을 쓸 수 있다면 간단하게 실현할 수 있다.

어떤 점이 다각형에 포함되었는지 확인

점과 직선의 거리

1과 관련해서는 크로스싱 넘버 알고릿hm이라는 방법을 사용했다.다음은 참조입니다.
https://www.nttpc.co.jp/technology/number_algorithm.html
2 중학교나 고등학교의 수학 문제가 될 것 같아 어렵지 않지만, 나는 거의 기억하지 못하고 고전했다.
최종적으로 다음과 같은 내용을 참고하였다.
https://schoolhmath.blogspot.com/2019/06/blog-post_8.html
먼저 어떤 망상물이 다각형에 포함되는지 판단한다.
실현은 다음과 같다.

(**
    ポリゴンに対して指定の点が内包されるか
*)
let isInternal (points : (float * float) array) (x : float, y : float) = 
    // ポリゴンを構成する点から線分を取得する
    // 最後の線分はインデックス0と接続するため、
    // 剰余算を用いる
    let polyLines =
        [| 0 .. points.Length - 1 |]
        |> Array.map (fun i ->
            let p1 = points.[(i    ) % points.Length]
            let p2 = points.[(i + 1) % points.Length]
            (p1, p2)
        )

    polyLines
    // c点からの(1,0)方向の水平線と
    // ポリゴン各辺の交点を持つ辺のみ抽出する
    |> Array.filter (fun ((x1, y1), (x2, y2)) ->
        let (vx, vy) = (x2 - x1, y2 - y1) 

        // 水平線と交点を持つ=y座標が一致するということなので
        // そのときのベクトル倍率を計算する
        let t  = (y - y1) / vy
        let cx = x1 + t * vx
        let cy = y1 + t * vy

        let minY = [ y1; y2 ] |> List.min
        let maxY = [ y1; y2 ] |> List.max

        x <= cx &&              // 左側で交差する場合は除く
        minY <= y && y <= maxY  // 線分外で交差する場合は除く
    )
    // 交点が奇数なら内側
    |> Array.length
    |> fun count -> count % 2 = 1

점과 직선의 거리를 계산하면 다음과 같다.

(**
    直線ABに対するC点を通る垂線の交点座標
*)
let verticalCrossPoint (pointA : (float * float), pointB : (float * float))
                       (pointC : float * float)  = 
    let (ax, ay) = pointA 
    let (bx, by) = pointB
    let (cx, cy) = pointC
    let (abx, aby) = ((bx - ax), (by - ay))
    let (acx, acy) = ((cx - ax), (cy - ay))
    let t = (abx * acx + aby * acy) / (abx ** 2.0 + aby ** 2.0)
    (ax + t * abx, ay + t * aby)

(**
    直線ABと点Cの距離
*)
let distance (pointA : (float * float), pointB : (float * float))
             (pointC : float * float) = 
    let (cx, cy) = pointC
    let (px, py) = verticalCrossPoint (pointA, pointB) pointC
    ((px - cx) ** 2.0 + (py - cy) ** 2.0) ** 0.5

그리고 이 색깔들을 조합해서 가장 가까운 격자 가장자리에 같은 색을 칠하는 것이 최초로 붙인 그림이다.
그림은 SVG가 다음과 같은 방법으로 만든 것이다.
https://zenn.dev/sos/articles/f1fd992be15091
이번에 우리는 기하학적 계산으로 구역 분할을 시험해 보려고 한다.