For practical data, a faster approach is usually to triangulate without validation, then just measure if triangulation is valid afterwards (which is simply comparing the sum of triangle areas with polygon area)