Dividing a polygon into triangles is easy if the polygon is convex. Doing the same for a concave polygon is also simple, but only if certain critical points can be identified. In the end, I think the bounding regions and triangles will be faster, but only if you can pre-create the triangles, and I can't think of an easy general case way to do this.

However, both techniques can be melded. If you determine bounding regions for the polygons, you will be able to quickly determine which polygons (and hence, which set of line segments) need to be checked using si-'s method.