Python に導入されている外部ライブラリ scipy には scipy.spatial.HalfspaceIntersection が実装されているので、これを利用すると比較的簡単に実装できます。

実装例 (Python, 269 ms)