目指せポリゴンマスター！

仕事柄JavaScriptで座標を扱う処理を多く書いているのですが、この座標とあの座標が重なっていて、こっちもこうだからさぁ大変！みたいな状況に一度は陥るわけなのです。
そんなときに役立つのが、ポリゴンの計算処理をばばんとやってくれるライブラリ。
どうもこいつの存在を知らずに、crossing numberだとかwinding numberは、、、とかよく知りもしないアルゴリズムをググって、ほむほむ、お、そのまま使えそうなコード発見とか最初やってました。
まあ、何が言いたいかというと、自分で処理を書きなぐって頑張るのも大事だけど、素直にライブラリ使った方が（たとえリファレンスが英語しかなくとも）、楽に安全に作れるよねって話です。

※自分自身わかってないところの方が多いので、おいおい勉強していきます。

#なにをつかったのか。
（おそらく界隈では有名だろう）Clipper.jsを使いました。
Angus Johnson's という方がC#でつくり、それが便利なもんでJSに移植されましたよみたいな感じで出回ってきたものだと思います。

自分自身よくわからず書き出してるのですが、とりあえずコード見てもらうのが一番早いかなと思います。

polygonBoolean.js

/**
 * 交差対象のポリゴン座標, 自ポリゴン座標, クリップタイプ
 */
function polygonBoolean(subjectPoints, clipPoints, clipType) {
    var sbjPath = [],
        clpPath = [];
    // clipperでのポリゴンの扱いは浮動小数点を含むとエラーが出やすくなるので整数を返す
    for (var i =0, iL = subjectPoints.length; i < iL; i++) {
        sbjPath[i] = convertPointToPath(subjectPoints[i]);
    }
    for (var j =0, jL = clipPoints.length; j < jL; j++) {
        clpPath[j] = convertPointToPath(clipPoints[j]);
    }
    function convertPointToPath(point) {
        return new ClipperLib.IntPoint(Math.round(point[0]), Math.round(point[1]));
    }

    var cpr = new ClipperLib.Clipper();
    // 自己交差しないポリゴンの計算コストを下げる
    cpr.StrictlySimple = true;
    // clipperオブジェクトにポリゴンのパス(座標)を追加
    cpr.AddPath(sbjPath, ClipperLib.PolyType.ptSubject, true);
    cpr.AddPath(clpPath, ClipperLib.PolyType.ptSubject, true);
    // ポリゴンの塗りつぶされ方を選択
    var sbjFillType = ClipperLib.PolyFillType.pftNonZero;
    var slpFillType = ClipperLib.PolyFillType.pftNonZero;

    var solutionPath = new ClipperLib.Paths();
    // ポリゴンの交差座標がbool演算実行によって生成される
    cpr.Execute(clipType, solutionPath, sbjFillType, clipFillType);
    // 返り値の設定
    return {
        'solutionPath' : solutionPath,
        'subjectPath' : sbjPath,
        'clipPath' : clpPath
    };
}

詳細

• 関数引数について

subjectPoints: 対象ポリゴン座標に対して重複し得るポリゴンの座標
clipPoints: 対象ポリゴンの座標
clipType: クリップタイプ

※クリップタイプは主に4種類あります。
0:交差(デフォルトはこれ), 1:結合, 2:差, 3:排他

• ClipperLib.IntPoint()

subjectPointsやclipPointsに格納された座標配列をClipperライブラリで用いれる座標(オブジェクト)に成形するためのメソッド。
浮動小数点による不正確さが原因でエラーが発生するので、Math.floor()などであらかじめ整数型に直してから使う必要があります。

intPoint.js

var point = new ClipperLib.IntPoint(10,20); // Creates object {"X":10,"Y":20}
var point2 = new ClipperLib.IntPoint(); // Creates object {"X":0,"Y":0}
var point3 = new ClipperLib.IntPoint(point); // Creates clone of point

• ClipperLib.Clipper()

クリッパークラスのインスタンスを作成。
こいつに座標やら設定値をセットすることで、クリップタイプに従ったポリゴン座標をいい感じに算出してくれる。

• StrictlySimple = true

単一ポリゴンが自分自身と交差しないことを示すフラグです(あってる...よね)。
計算されて返されるポリゴンが単一ポリゴンであることを証明するのは、非常に計算コストが高いので、
これを有効にすることで、返されるポリゴンは必ず単一になることを保証しますというフラグです。
デフォルトでは無効になっているので、なくても大丈夫なはずです。

• AddPath()

ClipperオブジェクトにsubjectPointsとclipPointsを追加します。
パス以外の引数は、それぞれが何のパスであるかということと、パスがクローズド(閉じられている)であることを指します。
subjectPointsは線(パスが開いている)でも、ポリゴン(閉じている)でも大丈夫ですが、clipPointsは必ずポリゴン(閉じている)でなければなりません。

• ClipperLib.PolyFillType.pftNonZero

これまじなにいってんのかなぞ。とりあえずおまじないって思っとくことにしました。
とりあえず今回はpftNonZeroでうまくいっているのでわかった時にコメントしていくことにします。

• Execute()

subjectPointsとclipPointsが割り当てられたクリッパーオブジェクトに対して、指定したclipTypeを実行する。

#実行結果

各クリップタイプでの実行結果だけ最後に書いておきます。

使用したポリゴン座標は下記です。

execute.js

subjectRoomPoints = [[0,0], [100,0], [100,100], [0,100]];
clipRoomPoints = [[50,0], [150,0], [150,100], [50,100]];

// clipType = 0 交差
solutionPath:Array(1)
 0:Array(4)
  0:ClipperLib.IntPoint {X: 100, Y: 100}
  1:ClipperLib.IntPoint {X: 50, Y: 100}
  2:ClipperLib.IntPoint {X: 50, Y: 0}
  3:ClipperLib.IntPoint {X: 100, Y: 0}
  length:4

// clipType = 1 結合
solutionPath:Array(1)
 0:Array(4)
  0:ClipperLib.IntPoint {X: 0, Y: 0}
  1:ClipperLib.IntPoint {X: 150, Y: 0}
  2:ClipperLib.IntPoint {X: 150, Y: 100}
  3:ClipperLib.IntPoint {X: 0, Y: 100}
  length:4

// clipType = 2 差
solutionPath:Array(1)
 0:Array(4)
  0:ClipperLib.IntPoint {X: 50, Y: 100}
  1:ClipperLib.IntPoint {X: 0, Y: 100}
  2:ClipperLib.IntPoint {X: 0, Y: 0}
  3:ClipperLib.IntPoint {X: 50, Y: 0}
  length:4

// clipType = 3 排他
solutionPath:Array(2)
 0:Array(4)
  0:ClipperLib.IntPoint {X: 150, Y: 0}
  1:ClipperLib.IntPoint {X: 150, Y: 100}
  2:ClipperLib.IntPoint {X: 100, Y: 100}
  3:ClipperLib.IntPoint {X: 100, Y: 0}
  length:4
 1:Array(4)
  0:ClipperLib.IntPoint {X: 50, Y: 100}
  1:ClipperLib.IntPoint {X: 0, Y: 100}
  2:ClipperLib.IntPoint {X: 0, Y: 0}
  3:ClipperLib.IntPoint {X: 50, Y: 0}
  length:4

#参考

Javascript Clipper