点在折线的哪一边是

Question

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

1.定义了多边形的顶点，从考虑的点到点的距离是最小的。变量minimum2p是到该顶点的距离，I2p是顶点的索引。

2.定义了一条折线的段，从考虑的点到它的距离是最小的。只有那些段数(可变的count_s)是由一个垂直点从考虑的点相交。变量minimum2s是到该段的最小距离；I2p是该段的第一个顶点的索引；flag是布尔变量，它存储由所述垂直线相交的哪个段的信息。

3.下一步，与使用链接-1、链接-2或链接-3链接的想法相比，选择合适的部分只是一个问题。我尝试了这里的方法，但它不适用于许多特殊情况。不过，我在那里使用最好的答案作为折线的内部点。因此，我的方法如下：

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

5.下一步，如果第4步不是这样的话，那么我检查一个折线的内部顶点。如果附近也有段关闭，那么我比较索引I2p和I2s，如果最后一个存在的话。如果它们是一致的，那么在选择与之相比较的适当的部分时就没有含糊不清之处。如果它们是不同的，那么偏好就会流向最近的部分而不是最近的顶点。

6.最后，如果附近没有段(在垂直的意义上，从点交叉段)，那么对于内部顶点，我应用了最好的答案 这里的思想。

以下是一些结果对应于由其顶点的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()

Answer 2

基于"绕组数“这一概念的替代解决方案如何？这将涉及到计算从测试点观察到的边界多边形的所有段所呈现的总角度。

如果你想象这条多边形在无穷远处被半圆扩展成一个封闭的等高线，那么这个角度之和对于轮廓外的一个点来说是零的，而对于内部的一个点则是2*Pi。很明显，半圆是在左半平面还是右半平面，将决定直线的哪一边是“内”还是“外”。如果将半圆本身排除在角和之外，因为它贡献了+/ -Pi，那么线的一侧的一个点应该有一个+Pi的角和，而另一边应该给出-Pi。它是+Pi还是-Pi取决于由多边形中的顶点序列定义的方向。

这种方法的一个微妙之处是计算出由折线的每一段所代表的(符号)角。我认为，这可以通过查看连接测试点到给定段两端的两个向量来实现。通过取这些向量的点乘积(除以它们的长度)，你就可以计算出该段所表示的角度的余弦。取反余弦时，负角间的正余弦将模糊不清.然而，通过取两个向量的交叉积 (把它们的z分量当作零)，你可以计算角度的正弦，它的符号将允许你计算逆余弦的正确分支。

Answer 3

一种不计算角度的方法是考虑由测试点和连续折线段生成的三角形的有符号区域。

三角形的有符号区域可以理解为(根据你采用的惯例)一个顶点位于相反线的“左”或“右”。它是由公式0.5 * (-x2*y1 + x3*y1 + x1*y2 - x3*y2 -x1*y3 + x2*y3)为三个顶点(xi, yi)计算的。关键的是，你穿过顶点的顺序会影响符号。

Suppse您的polyline是一个列表[v1, v2, ...., vn]。对于每个相邻顶点的有序对(v_i, v_(i+1))，计算三角形(v_i, your-test-point, v_(i+1))的有符号面积。似乎最关心“边”决定的是最小绝对面积的三角形:也就是点“最靠近”折线的地方。根据你的惯例决定这个三角形是左-还是右-相对于你的折线，通过考虑它的签名区域。

*编辑-一个零区域三角形意味着你的测试点与一个折线段是共线性的；你需要测试它是否是单独的。