Efficient algorithm to search convex polygons in a 2D space

Question

I have a 2D Space in which there is a convex polygon (in this case the red square) and a large number of triangles. My goal is to select the triangles

• Belonging
• Intersecting
• Surrounding

the red square (For more clarity, the triangles I am searching for are the ones in black).

I am currently using a brute force approach by checking the listed conditions on each triangle.

Is there a more efficient algorithm or any kind of heuristic which can be applied to reduce the time complexity?

Answer 1

Improve efficiency with a pre-filter

As checking orthogonal coordinates are relatively easy (maybe via a quad-tree), consider first a bounding box for each object. Then easy to eliminate objects that could not possibly meet the search criteria. The remaining objects can then use a more time intensive approach.