I'm reading a book on Computational Geometry ('CG in C' by Joseph O'Rourke). It is quite enlightening but there is one thing I feel like I have to ask about when it comes to triangulation of a polygon. In the process of producing a potential diagonal s, O'Rourke describes a method with the following steps (if indeed I understood it correctly):
- We make a line segment s between vertices $v_i$ and $v_{i+2}$ (sectioning off the possible "ear" $v_{i+1}$).
- We test s against all edges e in the polygon except those that are incident to vertex $v_i$ and vertex $v_{i+2}$.
- If there is no intersection (the union of the segment and all tested edges is the zero union), s is a diagonal candidate.
This seems straightforward enough. However O'Rourke, to my confusion, also writes that "If no such edge e intersects s, then s might be a diagonal. The reason we cannot reach a positive conclusion immediately is that it is possible that one of the edges incident to an endpoint of s might be collinear with s, and this would not be detected."
My question, thus, is how one of the edges incident to an endpoint of s can be collinear with s in any other way than the joining point (the vertex that is one of the constituent points of s - obviously they have to be collinear in that point) and this would go undetected?
If one of the edges incident to s shared more points with s than one, wouldn't that mean that it would force another edge (edge $v_{i-1}$, sort of) to share a point with s as well, and thus disqualify s from being a diagonal by means of the initial intersection tests?
Or do we mean.. perhaps... that the edge between $v_i$ and $v_{i+1}$ could be coinciding with s? So we have to check against a sort of degenerate case where three consecutive vertices are on the same y (or x) coord?
Input appreciated.