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?

CodePudding user response：

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.

CodePudding user response：

From a comment of yours, I infer that preprocessing the triangles is not an option. So unless the triangles are known to enjoy some special property that can be exploited, you can't avoid an exhaustive comparison of all triangles to the polygon (using the separating axis theorem, among others).