Segment Line Intersection algorithm in Numpy

Question

I have two line segments AB: (A1,B1), (A2,B2) and axis_dx coordinate interval. I should find all points crossed by axis coordinates interval i.e.,axis_dx. I already found those points, BUT, the problem is sometimes the code adds two beginning and ending points coordinates twice as in the example below. How can I fix that problem for all case i.e., for any positions of segment lines..? Thanks for the help in advance.

SImple example: here

import numpy as np

def intrsctd_pnts(A,B, axis_dx):

   N, M = np.shape(A)

   # slope of each link ( straight line)
   delta_x = (A[:, 0] - B[:, 0])
   delta_y = (A[:, 1] - B[:, 1])
   # Each line beginning and ending (min,max) values for intersected points
   lx_min = np.minimum(B[:,0], A[:,0])
   lx_max = np.maximum(B[:,0], A[:,0])
   ly_min = np.minimum(B[:,1], A[:,1])
   ly_max = np.maximum(B[:,1], A[:,1])

   lx_floor = np.ceil(lx_min / axis_dx) * axis_dx
   lx_ceil = np.floor(lx_max / axis_dx) * axis_dx
   ly_floor = np.ceil(ly_min / axis_dx) * axis_dx
   ly_ceil = np.floor(ly_max / axis_dx) * axis_dx

   for i in range(N):
     AB = []
     if delta_x[i]<>0. and delta_y[i]<>0.:
            m = delta_y[i]/delta_x[i]
            b = B[i, 1] - m * B[i, 0]
            # calculate all intersected x coordinates
            x = np.arange(lx_floor[i], lx_ceil[i]+axis_dx, axis_dx)
            y = m * x + b
            AB = zip(x, y)
            # calculate all intersected y coordinates
            y = np.arange(ly_floor[i], ly_ceil[i]+axis_dx, axis_dx)
            #print 'y: ',y
            x = (y - b) / m
            AB.extend(zip(x, y))
     elif delta_x[i]==0. and delta_y[i]<>0.:
            y = np.arange(ly_floor[i], ly_ceil[i]+axis_dx, axis_dx)
            x = B[i,0]*np.ones(len(y))
            AB = zip(x,y)
     elif delta_x[i]<>0. and delta_y[i]==0.:
            x = np.arange(lx_floor[i], lx_ceil[i]+axis_dx, axis_dx)
            y = B[i,1]*np.ones(len(x))
            AB = zip(x,y)

     AB.append((B[i,0], B[i,1]))
     AB.append((A[i,0], A[i,1]))
     AB.sort()
     return AB

# A = (A1,A2)
A = np.array([ [9., 23.], [21., 29.]])  # ,
# B = (B1,B2)
B = np.array([ [24., 35.], [28., 21.]])  # ,
axis_dx = 1.
intrsctd_pnts(A,B, axis_dx)

this function returns number of intersected points crossed by x and y axis in ordered form.. For moredetail , my previous example can be found, but this example is not very correct, but has the same idea.. here — Spider
– Spider, Commented Dec 8, 2013 at 9:27

HYRY · Accepted Answer · 2013-12-08 11:44:53Z

1

Here is the code to remove almost overlapping points, if distance between two consecutive points is less than a threshold, than remove the last one:

r = np.array(intrsctd_pnts(A,B, axis_dx))
idx = np.where(np.sum(np.diff(r, axis=0)**2, -1) < 1e-20)[0]+1
r2 = np.delete(r, idx, axis=0)

answered Dec 8, 2013 at 11:44

HYRY

97.8k28 gold badges197 silver badges192 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Segment Line Intersection algorithm in Numpy

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related