lines intersection

Posted by Alessandro on Mar 05, 2009

hi to all,

i'm new to python and nodebox, but i figured out how to detect intersections between segments (maybe there is a faster way with compound paths).
The code is inspired by a similar one for Processing: http://workshop.evolutionzone.com/2007/09/10/code-2d-line-intersection/

class Point:
	def __init__(self,x,y):
		self.x = x
		self.y = y
	def set(self,x,y):
		self.x = x
		self.y = y	
	
 
 
def intersect(A, B, C, D):
 
   if A.x != B.x:                # if s is not vertical
      b1 = (B.y - A.y) / float(B.x - A.x)
      if C.x != D.x:             # if t is not vertical
         b2 = (D.y - C.y) / float(D.x - C.x)
         a1 = A.y - (b1 * A.x)
         a2 = C.y - (b2 * C.x)
         if b1 == b2:                # if lines are parallel (slopes match)
            return(0)
         xi = -(a1-a2)/float(b1-b2)
         yi = a1 + (b1 * xi)
      else:
         xi = C.x
         a1 = A.y - (b1 * A.x)
         yi = a1 + (b1 * xi)
   else:
      xi = A.x
      if C.x != D.x:            # if t is not vertical
         b2 = (D.y - C.y) / float(D.x - C.x)
         a2 = C.x - (b2 * C.y)
         yi = a2 + (b2 * xi)
      else:
         return(0)
   # Here is the actual intersection test!
   if (A.x-xi)*(xi-B.x) >= 0 and \
   (A.y-yi)*(yi-B.y) >= 0 and \
   (C.x-xi)*(xi-D.x) >= 0 and \
   (C.y-yi)*(yi-D.y) >= 0:
      return((float(xi), float(yi)))  # Return the intersection point.
   else:
      return(0)
      
size(500,500)
num = 8
r = 8
 
p = []
for i in range(num*2):
	p.append(i)
	p[i] = Point(0,0)
for i in range(num):
	if(random(100)>50):
         p[i*2].set(0,random(HEIGHT))
         p[i*2+1].set(WIDTH,random(HEIGHT))	
	else:
         p[i*2].set(random(WIDTH),0)
         p[i*2+1].set(random(WIDTH), HEIGHT)
 
    		
 
background(1)
for j in range(num):
	strokewidth(1.0)
	stroke(0)
	fill(1,0,0)
 
	autoclosepath(False)
	beginpath(p[j*2].x,p[j*2].y)
	lineto(p[j*2+1].x,p[j*2+1].y)
	path = endpath(draw=True)
 
    	
	for i in range(num):
		if(i!=j):
			if(intersect(p[i*2],p[i*2+1], p[j*2],p[j*2+1])):
				x = intersect(p[i*2],p[i*2+1], p[j*2],p[j*2+1])[0]
				y = intersect(p[i*2],p[i*2+1], p[j*2],p[j*2+1])[1]
				oval(x-r/2,y-r/2,r,r)
				#print intersect(p[i*2],p[i*2+1], p[j*2],p[j*2+1])

now, i ask if there is a way to detect all polygons resulting from my intersections.
can you help me?