Testing whether a polygon is weakly simple

Question

I'm unable to come up with an algorithm to detect weakly simple polygons (i.e. polygons where the sides are allowed to touch but not cross over). Currently I am just checking for intersections between every side - here is the function I call for all non-adjacent sides. This way, only simple polygons are allowed (no touching at all). Polygons are vectors of points.

bool linesIntersect(const point &a1, const point &a2, const point &b1, const point &b2) {
    // Solve intersection of parametric lines using inverse matrix
    // The equation of the parametric lines are line1 = (a2 - a1)*s + a1
    // and line2 = (b2 - b1)*t + b1, where a1, a2, etc. are vectors.
    // Two equations can be produced from the two components, and these
    // this system of two equations can be solved for s and t
    // If the parameters s and t are between 0 and 1, it means that the lines intersect
    float x21 = a2.x - a1.x, x43 = b2.x - b1.x, x31 = b1.x - a1.x,
        y21 = a2.y - a1.y, y43 = b2.y - b1.y, y31 = b1.y - a1.y;
    float determinant = x43*y21 - x21*y43;
    if(determinant == 0.) return false;

    float s = float(x43*y31 - x31*y43)/determinant;
    float t = float(x21*y31 - x31*y21)/determinant; 

    if(s <= 1. && s >= 0. && t <= 1. && t >= 0.) return true; // lines intersect
    return false;
}

Using s < 1. && s > 0. && t < 1. && t > 0. does not work because it accepts some complex polygons as simple.

The first figure in this question shows a couple of examples. Below is a typical weakly simple polygon that the program would be dealing with.

I would prefer pseudocode since the math jargon in the aforementioned question (1) scares me and I don't think I have the knowledge to implement any complex algorithm. I am using Boost.Polygon for something else if there's something in there, but I didn't find anything.

EDIT:

Here is how I use the function. checkPts is a vector<point> with an assumed side from the last point to the first.

// Check for self-intersecting polygons
for(int i = 0; i < checkPts.size() - 2; ++i) {
    for(int j = i + 2; j < checkPts.size() - 2; ++j) {
        if(linesIntersect(checkPts[i], checkPts[i+1], checkPts[j], checkPts[j+1])) error("self-intersecting polygon");
    }
}

Answer 1

I am not sure I get it, because you seem to already have a solution. Just call lineIntersects on every pair of non-adjacent edges.

If two edges have no common points, then lineIntersects returns false, which is expected.

If two edges cross each other, lineIntersects returns true, and thus, you know that the polygon is not weakly simple.

If two edges touch, like in the picture, then the determinant that you compute in linesIntersects is 0 (i.e : the lines are parallel). lineIntersects returns false. Which is what you want (you allow edges to touch)

Of course, there is always the tricky part where operations on float leads to rounding errors, but for me, the math in your function is correct. (and should definitely work on the example in the picture)

Edit : A more "mathematical" approach. Two edges either have 0 points in common, 1 point in common, or an infinite number of points in common (they "touch"). Being weakly simple just means that for any two pair of edges, you are not allowed to have the "1 point in common" case. Thus, you need a function that finds out when you have exactly 1 point in common. My claim is that lineIntersects already does it

Edit 2 : I forgot to explain that having 1 point in common is not always a problem. But only if the common point between the two edges is at an endpoint of one of the two edges. Then we should "allow" it (return false). But this does not change my answer because in lineIntersects, we compute s < 1. && s > 0. && t < 1. && t > 0. and not s <= 1. && s >= 0. && t <= 1. && t >= 0.. So we already "allow" this case.