Well, you can mark up your triangle mesh. Check the adjacent faces of a shared edge and mark edges as concave, convex or flat. You can also mark concave vertex. A vertex is concave if at least one adjacent edge is concave. When you check the edges, you simply skip over those that are concave.

I don't think that concave edges should be skipped though. In your example image just move the the lover right vertex of the box such that it is exactly coincident with the concave edge and pressing into it. If you ignore the concave edge you can be pushed out of the world. I assume that have wrong contact geometry and I would debug this first.