<commit_before>// JavaScript Document
/// <reference path="http://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js" />


// ドロネー三角形分割関数
// 引数 inputPoints: 入力点の座標 [[x1,y1],[x2,y2],....]
// 引数 ymax, ymin, xmax, xmin: 入力点が含まれる領域の最大・最小座標
// 引数 constraint: 閉境界を構成する点のＩＤ[pointID1, pointID2,.... ] 
//                  ※閉境界であるため最後の要素は先頭の要素と一致するようにする
//                    一致しない場合，先頭要素と最後の要素をつなぐ辺も拘束される．
//                  ※省略可能 undefinedで渡されたら拘束なしとみなす
// 返り値：
//    オブジェクト
//    points: 点の座標リスト (inputPointsに加えて点群を内包する大きい三角形の頂点を含む)
//    head: ドロネー三角形クラスの連結リストの先頭への参照
function mcdt(inputPoints, constraint) {

	// 入力点がない場合、強制終了
	if(inputPoints.length<3) {
		return null;
	}

	var points=mcdt.clone(inputPoints);	// 点の数 x 2(x,y)
	var cst=mcdt.clone(constraint);		// 閉境界 cst[0]=cst[length-1] となるようにする
	if(cst[0]!=cst[cst.length-1]) {
		cst.push(cst[0]);
	}


	// STEP1: スーパートライアングルの作成
	// すべての点を内包する
	// 大きい三角形(superTriangle)の頂点を追加
	var superTri=mcdt.getSuperTriangle(points);
	points.push(superTri[0]);
	points.push(superTri[1]);
	points.push(superTri[2]);
	var l=points.length;
	var head=new DelaunayTriangle(points, [l-3, l-2, l-1]);


	// STEP2: 点の逐次追加
	// まず点を内包する三角形をローソン探査法で探し
	// その後、スワッピングアルゴリズムを用いて分割
	var resultTri=head;
	for(var i=0; i<points.length-3; ++i) {
		resultTri=DelaunayTriangle.lawsonTriangleDetection(points, resultTri, points[i]);
		resultTri.addPoint(i, points, cst);
	}

	// STEP3: 辺と閉境界との交差判定
	var resultCrossTri=mcdt.getCrossTriConstraint(points, head, cst);
	var crossConstraint=resultCrossTri.crossConstraint;
	var crossTri=resultCrossTri.crossTri;

	// STEP4: 交差解消
	// 交差三角形の頂点を抽出する
	var rmVtx=mcdt.extractVerticesFromTri(crossTri);
	var resultULV=mcdt.getUpperAndLowerVtx(points, cst, crossConstraint, rmVtx);
	var upperVtx=resultULV.upperVtx;
	var lowerVtx=resultULV.lowerVtx;


	if(crossConstraint!=null) {
		// upperVtx, lowerVtxを辺中点にたいして反時計回りになるように並べ替え
		var midpoint=mcdt.mul(0.5, mcdt.add(points[cst[crossConstraint+1]], points[cst[crossConstraint]]));
		function ccw(val1, val2) {
			th1=Math.atan2(points[val1][1]-midpoint[1], points[val1][0]-midpoint[0]);
			th2=Math.atan2(points[val2][1]-midpoint[1], points[val2][0]-midpoint[0]);
			return th2-th1;
		}
		upperVtx.sort(ccw);
		lowerVtx.sort(ccw);

		var upperResult=mcdt.innerTriangulation(points, upperVtx);
		var upperHead=upperResult.head;
		var tail=mcdt.getTail(head);
		tail.next=upperHead;
		upperHead.prev=tail;

		var lowerResult=mcdt.innerTriangulation(points, lowerVtx);
		var lowerHead=lowerResult.head;
		tail=mcdt.getTail(head);
		tail.next=lowerHead;
		lowerHead.prev=tail;

	}


	// 交差三角形を削除する
	for(var j=0; j<crossTri.length; ++j) {
		head=crossTri[j].remove(head);
	}
	// 新しい三角形を追加する


	// スーパートライアングルの削除
	head=mcdt.removeSuperTriangle(head, points);

	// 三角形接続リストの作成
	var conn=[];
	for(var tri=head; tri!=null; tri=tri.next) {
		conn.push(tri.vertexID);
	}

	return {
		points: inputPoints,
		head: head,
		crossConstraint: crossConstraint,
		crossTris: [crossTri],
		connectivity: conn,
		rmVtx: rmVtx,
		upperVtx: upperVtx,
		lowerVtx: lowerVtx
	};
}


mcdt.getTail=function (head) {
	var tail=head;
	while(1) {
		if(tail.next==null) {
			break;
		} else {
			tail=tail.next;
		}
	}
	return tail;
}

mcdt.innerTriangulation=function (points, innerVtx) {

	var innerPoints=new Array(innerVtx.length);
	for(var i=0; i<innerPoints.length; ++i) {
		innerPoints[i]=mcdt.clone(points[innerVtx[i]]);
	}
	var constraint=new Array(innerVtx.length);
	for(var i=0; i<innerVtx.length; ++i) {
		constraint[i]=i;
	}

	var cst=mcdt.clone(constraint);		// 閉境界 cst[0]=cst[length-1] となるようにする
	if(cst[0]!=cst[cst.length-1]) {
		cst.push(cst[0]);
	}
	// STEP1: スーパートライアングルの作成
	var superTri=mcdt.getSuperTriangle(innerPoints);
	innerPoints.push(superTri[0]);
	innerPoints.push(superTri[1]);
	innerPoints.push(superTri[2]);
	var l=innerPoints.length;
	var head=new DelaunayTriangle(innerPoints, [l-3, l-2, l-1]);
	// STEP2: 点の逐次追加
	var resultTri=head;
	for(var i=0; i<innerPoints.length-3; ++i) {
		resultTri=DelaunayTriangle.lawsonTriangleDetection(innerPoints, resultTri, innerPoints[i]);
		resultTri.addPoint(i, innerPoints, cst);
	}
	// スーパートライアングルの削除
	head=mcdt.removeSuperTriangle(head, innerPoints);

	// 親ドロネーの頂点インデックスに書き換える
	for(var tri=head; tri!=null; tri=tri.next) {
		for(var i=0; i<3; ++i) {
			tri.vertexID[i]=innerVtx[tri.vertexID[i]];
		}
	}

	// 三角形接続リストの作成
	var conn=[];
	for(var tri=head; tri!=null; tri=tri.next) {
		conn.push(tri.vertexID);
	}
	return {
		points: innerPoints,
		head: head,
		connectivity: conn,
	};
}

// crossConstraint番目のcstで定義される辺ベクトルで
// 頂点群vtxを分割し，upperVtx, lowerVtxに分ける
// 辺ベクトル上の頂点は両方に含まれる
mcdt.getUpperAndLowerVtx=function(points, cst, crossConstraint, vtx){<commit_msg>Fix little syntax errors<commit_after>// JavaScript Document
/// <reference path="http://ajax.googleapis.com/ajax/libs/jquery/1/jquery.min.js" />


// ドロネー三角形分割関数
// 引数 inputPoints: 入力点の座標 [[x1,y1],[x2,y2],....]
// 引数 ymax, ymin, xmax, xmin: 入力点が含まれる領域の最大・最小座標
// 引数 constraint: 閉境界を構成する点のＩＤ[pointID1, pointID2,.... ] 
//                  ※閉境界であるため最後の要素は先頭の要素と一致するようにする
//                    一致しない場合，先頭要素と最後の要素をつなぐ辺も拘束される．
//                  ※省略可能 undefinedで渡されたら拘束なしとみなす
// 返り値：
//    オブジェクト
//    points: 点の座標リスト (inputPointsに加えて点群を内包する大きい三角形の頂点を含む)
//    head: ドロネー三角形クラスの連結リストの先頭への参照
function mcdt(inputPoints, constraint) {

	// 入力点がない場合、強制終了
	if(inputPoints.length<3) {
		return null;
	}

	var points=mcdt.clone(inputPoints);	// 点の数 x 2(x,y)
	var cst=mcdt.clone(constraint);		// 閉境界 cst[0]=cst[length-1] となるようにする
	if(cst[0]!=cst[cst.length-1]) {
		cst.push(cst[0]);
	}


	// STEP1: スーパートライアングルの作成
	// すべての点を内包する
	// 大きい三角形(superTriangle)の頂点を追加
	var superTri=mcdt.getSuperTriangle(points);
	points.push(superTri[0]);
	points.push(superTri[1]);
	points.push(superTri[2]);
	var l=points.length;
	var head=new DelaunayTriangle(points, [l-3, l-2, l-1]);


	// STEP2: 点の逐次追加
	// まず点を内包する三角形をローソン探査法で探し
	// その後、スワッピングアルゴリズムを用いて分割
	var resultTri=head;
	for(var i=0; i<points.length-3; ++i) {
		resultTri=DelaunayTriangle.lawsonTriangleDetection(points, resultTri, points[i]);
		resultTri.addPoint(i, points, cst);
	}

	// STEP3: 辺と閉境界との交差判定
	var resultCrossTri=mcdt.getCrossTriConstraint(points, head, cst);
	var crossConstraint=resultCrossTri.crossConstraint;
	var crossTri=resultCrossTri.crossTri;

	// STEP4: 交差解消
	// 交差三角形の頂点を抽出する
	var rmVtx=mcdt.extractVerticesFromTri(crossTri);
	var resultULV=mcdt.getUpperAndLowerVtx(points, cst, crossConstraint, rmVtx);
	var upperVtx=resultULV.upperVtx;
	var lowerVtx=resultULV.lowerVtx;


	if(crossConstraint!=null) {
		// upperVtx, lowerVtxを辺中点にたいして反時計回りになるように並べ替え
		var midpoint=mcdt.mul(0.5, mcdt.add(points[cst[crossConstraint+1]], points[cst[crossConstraint]]));
		var ccw = function(val1, val2) {
			th1=Math.atan2(points[val1][1]-midpoint[1], points[val1][0]-midpoint[0]);
			th2=Math.atan2(points[val2][1]-midpoint[1], points[val2][0]-midpoint[0]);
			return th2-th1;
		}
		upperVtx.sort(ccw);
		lowerVtx.sort(ccw);

		var upperResult=mcdt.innerTriangulation(points, upperVtx);
		var upperHead=upperResult.head;
		var tail=mcdt.getTail(head);
		tail.next=upperHead;
		upperHead.prev=tail;

		var lowerResult=mcdt.innerTriangulation(points, lowerVtx);
		var lowerHead=lowerResult.head;
		tail=mcdt.getTail(head);
		tail.next=lowerHead;
		lowerHead.prev=tail;

	}


	// 交差三角形を削除する
	for(var j=0; j<crossTri.length; ++j) {
		head=crossTri[j].remove(head);
	}
	// 新しい三角形を追加する


	// スーパートライアングルの削除
	head=mcdt.removeSuperTriangle(head, points);

	// 三角形接続リストの作成
	var conn=[];
	for(var tri=head; tri!=null; tri=tri.next) {
		conn.push(tri.vertexID);
	}

	return {
		points: inputPoints,
		head: head,
		crossConstraint: crossConstraint,
		crossTris: [crossTri],
		connectivity: conn,
		rmVtx: rmVtx,
		upperVtx: upperVtx,
		lowerVtx: lowerVtx
	};
}


mcdt.getTail=function (head) {
	var tail=head;
	while(1) {
		if(tail.next==null) {
			break;
		} else {
			tail=tail.next;
		}
	}
	return tail;
}

mcdt.innerTriangulation=function (points, innerVtx) {

	var innerPoints=new Array(innerVtx.length);
	for(var i=0; i<innerPoints.length; ++i) {
		innerPoints[i]=mcdt.clone(points[innerVtx[i]]);
	}
	var constraint=new Array(innerVtx.length);
	for(var i=0; i<innerVtx.length; ++i) {
		constraint[i]=i;
	}

	var cst=mcdt.clone(constraint);		// 閉境界 cst[0]=cst[length-1] となるようにする
	if(cst[0]!=cst[cst.length-1]) {
		cst.push(cst[0]);
	}
	// STEP1: スーパートライアングルの作成
	var superTri=mcdt.getSuperTriangle(innerPoints);
	innerPoints.push(superTri[0]);
	innerPoints.push(superTri[1]);
	innerPoints.push(superTri[2]);
	var l=innerPoints.length;
	var head=new DelaunayTriangle(innerPoints, [l-3, l-2, l-1]);
	// STEP2: 点の逐次追加
	var resultTri=head;
	for(var i=0; i<innerPoints.length-3; ++i) {
		resultTri=DelaunayTriangle.lawsonTriangleDetection(innerPoints, resultTri, innerPoints[i]);
		resultTri.addPoint(i, innerPoints, cst);
	}
	// スーパートライアングルの削除
	head=mcdt.removeSuperTriangle(head, innerPoints);

	// 親ドロネーの頂点インデックスに書き換える
	for(var tri=head; tri!=null; tri=tri.next) {
		for(var i=0; i<3; ++i) {
			tri.vertexID[i]=innerVtx[tri.vertexID[i]];
		}
	}

	// 三角形接続リストの作成
	var conn=[];
	for(var tri=head; tri!=null; tri=tri.next) {
		conn.push(tri.vertexID);
	}
	return {
		points: innerPoints,
		head: head,
		connectivity: conn
	};
}

// crossConstraint番目のcstで定義される辺ベクトルで
// 頂点群vtxを分割し，upperVtx, lowerVtxに分ける
// 辺ベクトル上の頂点は両方に含まれる
mcdt.getUpperAndLowerVtx=function(points, cst, crossConstraint, vtx){
{'fraction_non_alphanumeric': 0.1556403731976251, 'fraction_numerical': 0.014843087362171332, 'mean_word_length': 4.662064825930372, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2794959', 'n_tokens_mistral': 4847, 'n_tokens_neox': 4754, 'n_words': 561}