algorithm - 点在多段线的哪一侧

Question

我正在尝试编写一个代码来识别随机点位于随机多段线(不是闭合多段线)的哪一侧。折线被认为是无限的，第一段和最后一段延伸到无穷大。如果它们是交叉的折线，则应将其视为多边形(我还没有详细说明这种情况的代码)。逻辑如下:

1. 定义多段线的顶点，距所考虑点的距离最短。变量 minimum2p 是到该顶点的距离，I2p 是顶点的索引。

2. 定义折线的线段，距所考虑点的距离最短。只有那些与考虑点的垂线相交的线段才算数(变量 count_s)。变量minimum2s是到线段的最小距离； I2p 是该段第一个顶点的索引； flag 是一个 bool 变量，它存储了与所提到的垂线相交的线段的信息。

3. 接下来只需选择合适的分割来与使用进行比较，例如，来自链接 link-1 的想法。 , link-2或 link-3 .我尝试了 here 中的方法，但它不适用于许多特殊情况。我用 the best answer虽然有折线的内部点。因此，我的方法如下:

4. 首先，检查它是折线的第一个还是最后一个顶点。如果是这种情况，则所选段相应地是第一个或最后一个，但前提是没有其他段比第一个或最后一个段更近。如果有另一个分割，那么我选择那个分割。

5. 接下来，如果第 4 步不是这种情况，那么我将检查折线的内部顶点。如果附近还有一个段关闭，那么我比较索引 I2p 和 I2s，如果最后一个存在的话。如果它们重合，那么在选择合适的分割市场进行比较时就没有歧义。如果它们不同，则优先选择最近的线段而不是最近的顶点。

6. 最后，如果附近没有线段(从穿过线段的点垂直的意义上讲)，那么对于内部顶点，我应用来自 the best answer 的想法here .

Here are some results对于不同的折线，由其顶点的X和Y坐标定义，对应地存储在'polylineX'和'polylineY'中(红色为'左'位置，灰色为'右'位置，黑色是折线上的位置，蓝线代表一条折线)。

正如您所注意到的，对于相对平滑的多段线，代码有效。然而，对于更尖锐的，或者在某些方面更复杂的，代码不能正常工作。我的代码中遗漏了什么？考虑到某些情况，应该添加什么条件？

代码如下:

clear all
close all 
clc
clf
polylineX = [0 1 2 3 4 5 6 7 8];
polylineY = [-10 20 -13 18 -17 16 -21 23 -25];
hold on
title(['polylineX=[',num2str(polylineX),'], polylineY=[',num2str(polylineY),']'])
chosen = 0;
span = 60;

for ii = 10:70
for jj = 30:60
    ii
    jj
    position = -2;
    point = [(jj-round(span/2))/1 (ii-round(span/2))/1];

    axis equal
    plot(polylineX,polylineY,'.-','MarkerSize',1,'LineWidth',1);

    distance2p = zeros(1,length(polylineX)); % distances from the point to the points (2p) of the polyline
    distance2s = zeros(1,length(polylineX)-1); % distances from the point to the segments (2s) of the polyline
    flag = zeros(1,length(polylineX)-1);
    count_s = 0; % counter of segments, which are intersected by the normal pointing from the 'point'
    k = 0;

    for i = 1:length(polylineX)-1
        pos = sign((polylineX(i+1) - polylineX(i)) * (point(2) - polylineY(i)) -...
                   (polylineY(i+1) - polylineY(i)) * (point(1) - polylineX(i)));

        % computing the distances from the 'point' to all segments and mark if
        % the distance vectors intersect the segments
        [flag(i),distance2s(i)] = distanceToLine([polylineX(i) polylineX(i+1)],[polylineY(i) polylineY(i+1)],[point(1) point(2)]);

        if flag(i)
            if k == 0
                minimum2s = distance2s(i);
                I2s = i;
            end;
            k = 1;
            count_s = count_s + 1; % count segments, which are intersected by the normal pointing from the 'point'
            if distance2s(i) < minimum2s
                I2s = i;
                minimum2s = distance2s(i);
            end;
        end;
    end;


    % first compute the distances between the 'point' under consideration and the
    % points of the given polyline
    for i  = 1:length(polylineX)
        distance2p(i) = sqrt((point(1)-polylineX(i))^2+(point(2)-polylineY(i))^2);
    end;
    [minimum2p,I2p] = min(distance2p);
    clear k pos i

    % now we need to choose which segment of the polyline to compare our 'point' with. These
    % segments are either adjacent to that point of the polyline, which is the closest
    % to the 'point' of interest, or the closest to the 'point' segment, which
    % has an intersection with the normale pointing from the 'point'.

    if I2p == 1 % if the 'point' is near the start of polyline
        if exist('minimum2s','var')
            if I2p == I2s
                chosen = I2p;
            else
                chosen = I2s;
            end;
        else
            chosen = I2p;
        end;

    elseif I2p == length(polylineX) % if the 'point' is near the end of polyline
        if exist('minimum2s','var')
            if I2s == I2p-1
                chosen = I2p - 1;
            else
                chosen = I2s;
            end;
        else
            chosen = I2p - 1;
        end;
    else
        if exist('minimum2s','var')
            if I2p == I2s
                chosen = I2p;

            else
                chosen = I2s;
            end;
        else
                pos1 =  sign((polylineX(I2p) - polylineX(I2p-1)) * (point(2) - polylineY(I2p-1)) -...
                 (polylineY(I2p) - polylineY(I2p-1)) * (point(1) - polylineX(I2p-1)));
                % position of the second segment relative to the first segment
                pos2 =  sign((polylineX(I2p) - polylineX(I2p-1)) * (polylineY(I2p+1) - polylineY(I2p-1)) -...
                             (polylineY(I2p) - polylineY(I2p-1)) * (polylineX(I2p+1) - polylineX(I2p-1)));
                if (pos1 == 1 && pos2 == 1) || (pos1 == -1 && pos2 == -1)
                    chosen = I2p;
                elseif pos1 == 0 || pos2 == 0
                    chosen = I2p;
                else
                    chosen = I2p - 1;
                end;
        end;
    end;

    position = sign((polylineX(chosen+1) - polylineX(chosen)) * (point(2) - polylineY(chosen)) -...
                    (polylineY(chosen+1) - polylineY(chosen)) * (point(1) - polylineX(chosen)));

    if position == 1
        plot(point(1),point(2),'r.','MarkerSize',5)
    elseif position == -1;
        plot(point(1),point(2),'.','Color',[0.9 0.9 0.9],'MarkerSize',5) % gray color
    elseif position == 0
        plot(point(1),point(2),'k.','MarkerSize',5)
    elseif position == -2
        plot(point(1),point(2),'g.','MarkerSize',5)
    end;

    pause(0.00000001)
    clear chosen  count_s distance2p distance 2s flag I2p I2s minimum2p minimum2s point pos1 pos2 position

end;
end;

Answer 1

我有一个天真的想法是从点到线整合角度。积分从无穷大的一侧开始，然后遍历所有点到无穷大的另一侧。那只是一堆 atan2 函数。

曲线的边由积分符号决定。即使曲线重叠，这也应该有效。

在 python 中:

from math import atan2,pi
#import matplotlib.pyplot as plt

# difference of two angles should be always -pi < x < pi
def fixed_angle(a):
    if a > pi:
       return a - 2*pi
    elif a < (-1*pi):
       return a + 2*pi
    assert(-1*pi < a < pi) # just check, to be sure
    return a

# polyline
xs = [0, 1, 2, 3, 4, 5, 6, 7, 8];
ys = [-10, 20, -13, 18, -17, 16, -21, 23, -25];

# start point
x = 4
y = 0

#from first two points
angle_start = atan2(ys[0]-ys[1],xs[0]-xs[1])
#last angle is angle of last section
angle_end = atan2(ys[-1]-ys[-2],xs[-1]-xs[-2]) 

integ = 0
prev =  angle_start
for i in range(len(xs)):
    a = atan2(ys[i]-y,xs[i]-x)
    integ += fixed_angle(a-prev)
    prev = a

integ += fixed_angle(angle_end - prev)

if integ > 0:
    print("point is left")
else:
    print("point is right")

#plt.plot(xs,ys)
#plt.show()