# Self intersecting polygon

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

@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

``````