私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「共通部分は何角形？」（CodeIQ）を参照してください。
【概要】
三角形が2つあります。
2つの三角形のどちらにも含まれる領域（共通部分）が何角形になるのかを計算して下さい。
【入出力】
入力は
(2,3)(6,1)(4,5)/(1,5)(7,2)(7,6) (2,2)(5,2)(4,4)/(9,3)(1,5)(5,1) (2,1)(3,2)(2,3)/(11,12)(4,7)(14,13)
こんな感じです。
三角形のペアが空白区切りで並んでいます。
ペアはスラッシュ区切りになっています。() 内に、頂点のx座標y座標がコンマ区切りで並んでいます。
出力は、2つの三角形の重なり合った部分が何角形であるかを、区切り文字なしでつなげたものです。
ただし、多角形にならない場合（共有部分がない、線分になる、など）は、数字ではなく-として下さい。
先程の例だと
最初の組(2,3)(6,1)(4,5)/(1,5)(7,2)(7,6)は、3角形。
二番目の組(2,2)(5,2)(4,4)/(9,3)(1,5)(5,1)は、4角形。
最後の組(2,1)(3,2)(2,3)/(11,12)(4,7)(14,13)は、多角形になりません。
ということで、34-を出力すれば正解となります。
末尾の改行はあってもなくても構いません。
【例】
入力 出力 (2,3)(6,1)(4,5)/(1,5)(7,2)(7,6) (2,2)(5,2)(4,4)/(9,3)(1,5)(5,1) (2,1)(3,2)(2,3)/(11,12)(4,7)(14,13)34-(1,5)(8,5)(3,10)/(3,1)(7,9)(3,7) (1,2)(7,2)(4,5)/(4,1)(7,4)(1,4)56
【補足】
座標は、いずれも正の整数で、百万を超えることはありません。
ひとつの入力に含まれる 三角形の組は 10組以下です。
いずれの三角形も、ゼロより大きな面積を持ちます。
不正な入力に対処する必要はありません。
Rubyで解答しています。
#!/usr/bin/ruby
# 入力値のパース
# [a,b,c]を返す
def parse(param)
ret = []
md = param.match(/\(([0-9]+,[0-9]+)\)\(([0-9]+,[0-9]+)\)\(([0-9]+,[0-9]+)\)/)
for i in 1..3
v = md[i].split(",").map{|a| a.to_i}
ret << v
end
return ret
end
# 三角形の座標を取得する
def getTriangle(params)
ret = []
for triangle in params.split("/")
points = parse(triangle)
ret << points
end
return ret
end
# ベクトルの差
def sub_vector(x, y)
return [x[0]-y[0], x[1]-y[1]]
end
# 外積
def cross(x, y)
return (x[0] * y[1]) - (x[1] * y[0])
end
# 頂点にある場合以外のチェック
# 引数はそれぞれ外積の結果
# 外積のいずれかが0の場合は辺上にある
# 全部が同じ方向を向いているなら内側にある
# どれかが違う方向なら外側にある
# 三角形が点を含んでいる場合2を返す。それ以外は0を返す
def check(c1, c2, c3)
if (c1 == 0) || (c2 == 0) || (c3 == 0) then
is_b = 1
for c in [c1, c2, c3]
if c == 0 then next
elsif c > 0 then is_b *= 1
else is_b *= -1
end
end
if is_b == 1 then return 2
else return 0
end
elsif (c1 > 0 && c2 > 0 && c3 > 0) || (c1 < 0 && c2 < 0 && c3 < 0) then return 2
else return 0
end
end
# 三角形の中に点があるかを判定する
# 辺上にある場合は内側にあるとみなす
# 内側にある場合は2を、頂点にある場合は1を、何でもない場合は0を返す
# （注意）2つの三角形の頂点の包含関係を求めた場合、2倍の数が帰ることになる
def isPointInTriangle(triangle, q)
a = triangle[0]
b = triangle[1]
c = triangle[2]
# 頂点にあるかチェック
if (a == q) || (b == q) || (c == q) then
return 1
end
ab = sub_vector(b, a)
bc = sub_vector(c, b)
ca = sub_vector(a, c)
bq = sub_vector(q, b)
cq = sub_vector(q, c)
aq = sub_vector(q, c)
c1 = cross(ab, bq)
c2 = cross(bc, cq)
c3 = cross(ca, aq)
return check(c1, c2, c3)
end
# 三角形1の内側にある三角形2の頂点、三角形2の内側にある三角形1の頂点の数を返す
def getInTrianglePoints(triangle1, triangle2)
ret = 0
for t in triangle1
ret += isPointInTriangle(triangle2, t)
end
for t in triangle2
ret += isPointInTriangle(triangle1, t)
end
return ret
end
# 線分同士が交わっているかをチェックする
# 交わっている場合は1、それ以外は0を返す
# 一方が他方を突き抜けていない場合は交差していないとみなす
def isCrossed(p1, p2, p3, p4)
if ((p1[0] - p2[0]) * (p3[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p3[0])) * ((p1[0] - p2[0]) * (p4[1] - p1[1]) + (p1[1] - p2[1]) * (p1[0] - p4[0])) < 0 then
if ((p3[0]- p4[0]) * (p1[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p1[0])) * ((p3[0] - p4[0]) * (p2[1] - p3[1]) + (p3[1] - p4[1]) * (p3[0] - p2[0])) < 0 then
return 1
end
end
return 0
end
# 線分同士の交点の数を求める
# 引数は2つの三角形の座標
def getCrossPoints(tri1, tri2)
# 三角形1の線分
lines1 = [[tri1[0], tri1[1]], [tri1[1], tri1[2]], [tri1[2], tri1[0]]]
# 三角形2の線分
lines2 = [[tri2[0], tri2[1]], [tri2[1], tri2[2]], [tri2[2], tri2[0]]]
ret = 0
#それぞれの線分の交点を求める
for l1 in lines1
for l2 in lines2
# 三角形1の線分と三角形2の点の関係
ret += isCrossed(l1[0], l1[1], l2[0], l2[1])
end
end
return ret
end
# 結果の文字列を取得する
def getResultStr(v)
if v < 3 then return "-"
else return v.to_s
end
end
# 問題を解く
def solve(line)
ret = []
for params in line.split
triangles = getTriangle(params)
crs_p = getCrossPoints(triangles[0], triangles[1])
in_p = getInTrianglePoints(triangles[0], triangles[1])
# printf("crs_p=%d, in_p=%d\n", crs_p, in_p)
ret << getResultStr(crs_p + in_p/2)
end
return ret
end
# main
# main
while line = gets
line.strip!
if line.empty? then next end
puts solve(line).join("")
end
三角形と点の関係の続きの問題ですが、★★★だけあって格段に難しいです。
問題は2つの三角形が重なる部分をどうやって認識するかです。
結論から言うと、辺の交点と外側の三角形に包含される他方の三角形の頂点が作る領域が囲まれる範囲になります。
なので、交点の数と外側の三角形に囲まれる他方の三角形の頂点の数を数えれば答えになります。
注意点は次の2点です。
・交点と包含される頂点を二重にカウントしないこと。
・互いに包含する場合（頂点が重なる場合）を考慮すること。
入力値の1グループの片方（(2,3)(6,1)(4,5)）をパースして頂点座標を配列として返します。正規表現で簡単に取り出せるので正規表現で数字だけを抜き出して数値に変換して返します。
入力値の1グループ（(2,3)(6,1)(4,5)/(1,5)(7,2)(7,6)）をパースして2つの三角形の頂点座標を配列として返します。
「ベクトルの差」コメントしていますが、座標からベクトルを求めます。
特に説明は必要ないでしょう。
ベクトルの外積を求めて返します。
これもやっていることは一目瞭然なので説明は不要でしょう。
頂点と重ならない場合の点と三角形の位置をチェックします。
点Pが頂点に一致している場合は先にチェック済みなのでここではチェックしません。
入力値はベクトルABとBP、BCとCP、CAとAPそれぞれの外積です（Pは他方の三角形の任意の頂点）。
基本的に前回の問題の同名関数と同じなので詳細は省略します。
包含関係は線上に点がある場合は包含されると判断します。
ポイントは点が包含される場合は1ではなく2を返すことです。isPointInTriangle()と関係するのですが、頂点が一致している場合、二重にカウントされるため2倍の値を返しておいて後で1/2にするためです。こうしておけば重なっている頂点に関する処理を省くことができます。
三角形と任意の点（他方の三角形の頂点）との包含関係をチェックします。
基本的に前回の問題のsolve()と同じなので詳細は省略します。
頂点と点が重なっている場合、1を返します。それ以外の場合はcheck()の結果を返します。
こうすると三角形ABCとDEF相互の包含関係を調べて得られる一方の三角形に包含される他方の頂点の数はisPointInTriangle()の結果の1/2になります。
例えば三角形ABCとDEFの頂点AとDが同じ座標、他は包含関係なしとします。三角形ABCに対して点DEFを調べた場合Dは三角形ABCに包含されると判定されます。反対に三角形DEFに対して点ABCを調べた場合Aも三角形DEFに包含されると判定されます。結果二重にカウントされてしまうのですが、頂点が重なる場合だけ半分のカウントとしておくと二重にカウントされた場合に正しい結果になる仕組みになります。
三角形ABCとDEF相互に他方の頂点を包含しているかをチェックします。
結果は実際に包含する数の2倍になります。
線分同士が交わっているかをチェックします。
引数は線分XYの座標（p1, p2）と線分WZの座標（p3, p4）です。
ロジックはhttp://www5d.biglobe.ne.jp/~tomoya03/shtml/algorithm/Intersection.htmを参考にしました。これは直線XYと線分WZ、線分XYと直線WZが交わるかをチェックし、両方に交わっている場合は1、それ以外は0を返すというロジックになっています。結構長くなるので詳細はリンク先を参照してください。
線上に末端の座標がある場合は交差していないと判断します。三角形の包含関係で線上、及び、頂点が重なっている場合を包含と判断するのでこちらでは線上に末端が重なる場合は交わっていないとしなければ二重にカウントしてしまうことになります。
返り値は交差している場合が1、していない場合が0です。
三角形ABCと三角形DEFの各辺が交差しているかをチェックします。
単純にABに対してDE、EF、FDが、BCに対してDE、EF、FDが、CBに対してDE、EF、FDが重なっているかをチェックします。isCrossed()でチェックしますが、isCrossed()の返り値が2つの線分の交点の数なのでそれを積算すれば結果になります。
答えは2つの三角形の辺の交点の数と包含される頂点の数の合計ですが2以下の場合多角形を作れないので"-"を表示しなければなりません。その処理を行うだけです。
問題を解きます。
入力値を空白文字で分割して1組ごとにループします。
1組の三角形の座標をgetTriangle()で取得します。
三角形の各辺の交点の数をgetCrossPoints()で取得します。
一方の三角形に包含される他方の三角形の頂点の数をgetInTrianglePoints()で取得します。
getCrossPoints()の結果とgetInTrianglePoints()の結果の1/2が重なる部分の図形の頂点の数になるのでそれをgetResultStr()で出力文字列に変換して結果に加えます。
結果は配列なのでjoin()して出力すれば答えになります。
頑張ればできるタイプの問題ですが、かなり苦労しました。
ドロー系の画像ソフトだと図形同士のANDとかOR、NORができるので一般的なアルゴリズムがあるんじゃないか？ と思って調べたのですが（日本語だけです）見つからず、自分で考えました。図形同士のANDとかOR、NORのアルゴリズムはドロー系の画像ソフト屋さんの秘伝か何か何でしょうか？
できてしまえば理屈は難しくないのですが、やっている時は三角形の位置関係を気にせず、座標の順番にも依存せず、点の重複も考慮した上でうまくやる方法を考えるのに苦労しました。実際には点の重複以外は特にきにする必要はなかったわけですが。