Self intersecting polygon

How can I:
A) check if a polygon is self intersecting.
B) Find the index of the intersecting point.

http://stackoverflow.com/questions/4876065/check-if-polygon-is-self-intersecting

http://www.lems.brown.edu/~wq/projects/cs252.html

@Luatee One way I would try is to loop thru the verticies and compare two lines at a time an see if they intersect. That would also give you the intersecting coordinates. Try Google for the formula for intersecting lines. I don’t have time now, but that sounds like an interesting problem to work on.

I have looked at a few algorithms but I don’t need a really complex algorithm for a really complex polygon, I just need to check where the intersections are, something that is quite simple but I haven’t found a straight forward algorithm yet, I know the problem isn’t straightforward but its not difficult.

@Luatee Is this something that you’re after. Tap the screen to create different verticies. If the verticies cause a line to cross another, the intersect point is calculated and plotted. I also plot the x,y coordinates and the point number of each vertex. I keep creating the lines as long as you tap the screen. Restart the program to start another example.


displayMode(FULLSCREEN)

function setup()
    tab={}
    tab1={}
end

function loop()    -- compare all the lines with each other
    tab1={}
    a=#tab
    for b=1,#tab do
        c=#tab
        for d=1,#tab do
            if d~=b then
                calc(a,b,c,d)
            end
            c=d
        end
        a=b
    end
end

function calc(a,b,c,d)    -- calculate intercept point
    x1=tab[a].x
    y1=tab[a].y
    x2=tab[b].x
    y2=tab[b].y
    x3=tab[c].x
    y3=tab[c].y
    x4=tab[d].x
    y4=tab[d].y    
    x12 = x1 - x2
    y12 = y1 - y2    
    x34 = x3 - x4    
    y34 = y3 - y4     
    c = x12 * y34 - y12 * x34  
    if math.abs(c) > 0.01 then
        a = x1 * y2 - y1 * x2
        b = x3 * y4 - y3 * x4
        x = (a * x34 - b * x12) / c
        y = (a * y34 - b * y12) / c    
    end
    if x>math.min(x1,x2) and x<math.max(x1,x2) and
          y>math.min(y1,y2) and y<math.max(y1,y2) and
          x>math.min(x3,x4) and x<math.max(x3,x4) and
          y>math.min(y3,y4) and y<math.max(y3,y4) then
       table.insert(tab1,vec2(x,y))
    end
end

function draw()
    background(40,40,50)
    stroke(255)
    strokeWidth(2)
    i=#tab
    for j=1,#tab do    -- draw lines
        line(tab[j].x,tab[j].y,tab[i].x,tab[i].y)
        text("("..tab[j].x..","..tab[j].y..")",tab[j].x,tab[j].y-20)
        text(j,tab[j].x,tab[j].y-40)
        i=j
    end
    fill(255)
    for a,b in pairs(tab1) do    -- draw intercept point
        ellipse(b.x,b.y,15)
    end
end

function touched(t)
    if t.state==BEGAN then        
        table.insert(tab,vec2(t.x,t.y))
        if #tab>2 then
            loop()            
        end
    end
end