Hatena::Grouptopcoder

zerokugi's contest memo

2015-06-11線分アレンジメントでよく踏むバグ

f:id:zerokugi:20150611093556p:image

交点列挙→重複除去→線分に乗ってる点を列挙してソート繋ぐ

というよくある手法を使うとたまにこうなってしまう

おそらく、距離を元に重複除去した後に、外積を使って点が線分上にあるかを判定しているのが原因なのだけれど、重複除去時にEPSを使わずに比較するべきなのか、それとも交点列挙する時に線分と点の関連付けを行っておくべきなのか

EPSを噛ませずに比較するのは微妙に不安を感じるけど、誤差とか実装量を考えると前者にするべきな気がする。


結論:とりあえず比較する時はEPSつけとけばいいでしょ、という安易な考え方はダメ

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/zerokugi/20150611