Bowyer-Watson algorithm as described on Wikipedia (https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) doesn't generate any triangles for this valid point list:
p0 = (50, 50), p1 = (150, 50), p2 = (250, 67)
super-triangle is chosen to be:
p3 = (0,0), p4 = (1600,0), p5 = (0, 1200)
When point p2 is inserted, it is exactly outside triangle (p0,p1,p5), so it is not a bad triangle. Therefor it is not removed, and edge (p0,p1) is not part of the polygonal hole and triangle (p0,p1,p2) is thus never created.
If I choose a larger super-triangle it works, but then when p2 moves closer to the line defined by p0 and p1, the same happens.
Is Bowyer-Watson broken by design, or am I doing something wrong?
I think I know what you are after. The pseudo code on Wikipedia just specifies that the initial super triangle should contain all points in its interior. I could not pin down a corresponding statement in Bowyer's original work, but at least Watson's article states explicitly
And while both authors discuss degeneracies in general, it seems that one should rather demand that the vertices of the super triangle (or more generally: simplex) have to be outside all circumcircles of any three given points to begin with (which is hard when any three points are almost collinear). Then again, such a constellation is problematic only if it survives until all points have been treated.
How to solve? Personally, I would use symbolic vertices $(-\infty,-\infty)$, $(0,\infty)$, $(\infty,0)$ as super triangle. One then has to contemplate how to define the circumscribed circle of three vertices when some are infinite (spoiler: the disk becomes a half plane).