如何在2D图上找到自交点的数量? [英] How to find number of self intersection points on 2D plot?

问题描述

我有两个numpy数组 x 和 y :

  x = [-256.70946838 -188.26946838 -83.86946838 29.81053162 131.89053162213.67053162 271.09053162 315.17053162 310.53053162 296.03053162252.53053162 184.67053162 82.59053162 -33.40946838 -139.54946838-213.78946838 -271.20946838 -317.02946838 -310.64946838 -298.46946838-256.70946838]y = [9.71224758e-02 -3.19097822e-02 -4.80388145e-02 6.48644113e-02-3.19097822e-02 9.71224758e-02 -1.57807500e-02 6.48644113e-02-4.02877524e-01 -1.93200105e-01 6.48644113e-02 1.64773146e-023.48282294e-04 -1.44813008e-01 6.48644113e-02 -1.57807500e-023.48282294e-04 -8.02968790e-02 2.10025702e-01 1.77767637e-019.71224758e-02] 

当我使用绘图命令时:

  plt.plot(x，y)plt.show() 

下图将是输出:

现在，我想基于 x 和 y 数组找到自相交的数量，在此图中它等于 6 ，我不知道如何找到它.

感谢您的帮助.

解决方案

只需找到

这是Wikipedia公式的直接实现，可以确定是否需要对其进行优化.

I have two numpy arrays x and y:

x = [-256.70946838 -188.26946838  -83.86946838   29.81053162  131.89053162
  213.67053162  271.09053162  315.17053162  310.53053162  296.03053162
  252.53053162  184.67053162   82.59053162  -33.40946838 -139.54946838
 -213.78946838 -271.20946838 -317.02946838 -310.64946838 -298.46946838
 -256.70946838]

y = [ 9.71224758e-02 -3.19097822e-02 -4.80388145e-02  6.48644113e-02
 -3.19097822e-02  9.71224758e-02 -1.57807500e-02  6.48644113e-02
 -4.02877524e-01 -1.93200105e-01  6.48644113e-02  1.64773146e-02
  3.48282294e-04 -1.44813008e-01  6.48644113e-02 -1.57807500e-02
  3.48282294e-04 -8.02968790e-02  2.10025702e-01  1.77767637e-01
  9.71224758e-02]

when I use plot command:

plt.plot(x, y)
plt.show()

Below figure would be the output:

Now I want to find the number of self-intersections based on x and y arrays which in this figure it equals six and I don't know how to find it.

Thanks for helping.

解决方案

Just find the intersections between any two line segments:

x = [-256.70946838, -188.26946838,  -83.86946838,   29.81053162,  131.89053162,
  213.67053162,  271.09053162,  315.17053162,  310.53053162,  296.03053162,
  252.53053162,  184.67053162,   82.59053162,  -33.40946838, -139.54946838,
 -213.78946838, -271.20946838, -317.02946838, -310.64946838, -298.46946838,
 -256.70946838]

y = [ 9.71224758e-02, -3.19097822e-02, -4.80388145e-02,  6.48644113e-02,
 -3.19097822e-02,  9.71224758e-02, -1.57807500e-02,  6.48644113e-02,
 -4.02877524e-01, -1.93200105e-01,  6.48644113e-02,  1.64773146e-02,
  3.48282294e-04, -1.44813008e-01,  6.48644113e-02, -1.57807500e-02,
  3.48282294e-04, -8.02968790e-02,  2.10025702e-01,  1.77767637e-01,
  9.71224758e-02]

def intersection(x1,x2,x3,x4,y1,y2,y3,y4):
    d = (x1-x2)*(y3-y4) - (y1-y2)*(x3-x4)
    if d:
        xs = ((x1*y2-y1*x2)*(x3-x4) - (x1-x2)*(x3*y4-y3*x4)) / d
        ys = ((x1*y2-y1*x2)*(y3-y4) - (y1-y2)*(x3*y4-y3*x4)) / d
        if (xs >= min(x1,x2) and xs <= max(x1,x2) and
            xs >= min(x3,x4) and xs <= max(x3,x4)):
            return xs, ys

xs, ys = [], []
for i in range(len(x)-1):
    for j in range(i-1):
        if xs_ys := intersection(x[i],x[i+1],x[j],x[j+1],y[i],y[i+1],y[j],y[j+1]):
            xs.append(xs_ys[0])
            ys.append(xs_ys[1])

from matplotlib import pyplot as plt
plt.plot(x, y)
plt.scatter(xs, ys, color='r')
plt.show()

This is a straightforward implementation of the wikipedia formula which surely can be optimized if needed.

这篇关于如何在2D图上找到自交点的数量?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！