判断线段方向是顺时针还是逆时针

Question

我有一个由2D点 (x1,y1),(x2,y2)......(Xn,Yn) 组成的曲线段列表，是否有公式可以确定绘制该曲线段的方向是顺时针还是逆时针？非常感谢您的帮助。

- Ahmed Abobakr

---

一个线段如何具有顺时针/逆时针方向？它的确切定义是什么？ - kraskevich

@LuisMendo - 好的，我明白了。你可以尝试找出曲线的重心。一旦你找到了重心，就可以找到每个曲线上的点与这个重心的夹角。之后，使用diff函数来查看点之间相邻的差异。如果输出向量中每个元素的diff元素为正数，则可以将其视为顺时针方向。如果它是负数，则可以将其视为逆时针方向。也许可以制作一个正负次数的直方图，并选择具有更高计数的箱子作为所选方向。 - rayryeng

@rayryeng 我正在打我的答案，然后看到了你的评论。我认为我的答案或多或少就是你建议的。 - Luis Mendo

@rayryeng 我认为你所提到的歧义可以通过__展开相位__来消除（前提是采样点足够细致）。这就是我在我的答案中所做的。 - Luis Mendo

@LuisMendo - 没错。我忘了 unwrap。很好的发现！ - rayryeng

Answer 1

另外，您也可以使用一些线性代数知识。如果您有三个点a、b和c，并按顺序排列，则可以按照以下步骤进行：

 1)  create the vectors u = (b-a) = (b.x-a.x,b.y-a.y) and v = (c-b) ...
 2) calculate the cross product uxv = u.x*v.y-u.y*v.x
 3) if uxv is -ve then a-b-c is curving in clockwise direction (and vice-versa).

通过沿着相同的方式沿着更长的曲线走，甚至可以检测出当“S”形曲线从顺时针变为逆时针时的变化，如果有用的话。

- Penguino

---

对我来说，这是迄今为止最好的解决方案。+1 - nicolas

@seb - 没关系。我误读了算法。我会删除我的评论，因为它是无意义的。 - rayryeng

@Penguino：我有N个点，我尝试了你的方法，但是因为我有N个点，我对每两个相邻不同向量的叉积结果进行求和，这样做正确吗？ - Ahmed Abobakr

@ahmed：是的，做一些像x1=diff(x) y1=diff(y)这样的事情，然后对x1 y1的所有连续元素进行X乘积。 - nicolas

@ahmed 是的 - 如果曲线在其整个长度上都是局部顺时针的，那么你将得到所有的负叉积，所以求和是可以的。但如果曲线在其整个长度上具有相同的曲率方向，则可以通过仅对前三个点进行测试来节省时间。 - Penguino

Answer 2

一种可能的方法。 如果您点列表所代表的行的采样均匀且足够平滑，并且该行足够简单，则应该可以正常工作。

1. 减去平均值以“居中”该行。
2. 转换为极坐标以获得角度。
3. 取消角度包装，以确保其增量有意义。
4. 检查总增量是否为正或负。

我假设您的数据在x和y向量中。

theta = cart2pol(x-mean(x), y-mean(y)); %// steps 1 and 2
theta = unwrap(theta); %// step 3
clockwise = theta(end)<theta(1); %// step 4. Gives 1 if CW, 0 if ACW

这只考虑了所有点的“综合”效果。这并不告诉您是否沿途有“折痕”或方向不同的部分。

一种可能的改进方法是通过某种积分替换x和y的平均值。原因是：如果在一个区域中采样更密集，则平均值会偏向该区域，而积分不会。

- Luis Mendo

---

嗯...这基本上就是我写的建议方法！非常好。我决定放弃所有差异，并查看哪个符号的数量更多，然后选择它。这仍然是一个不错的方法。 - rayryeng

Luis，我尝试了你的方法，它有效 :) 非常感谢你的帮助。 @rayryeng，非常感谢您的帮助。 - Ahmed Abobakr

@LuisMendo - 我收藏了这篇文章，主要是因为不同的SO用户（Yvon、你和我自己）之间的合作，最终得出了一个对OP有效的答案。谢谢！ - rayryeng

@ahmedabobakr - 非常欢迎。很高兴我们能够帮助您解决这个问题！ - rayryeng

@rayryeng 抱歉如果我（无意中）抄袭了你的方法。我正在忙着准备我的答案，完全不知道你在评论中提出了相同的方法。 - Luis Mendo

@LuisMendo - 没问题。老实说，我不确定我的方法是否可行。看到你发布了一个答案，而且楼主接受了它，证明了我脑海中的想法是正确的。声望分数只是次要的。我在这里大多是为了帮助人们，这篇文章和合作就是证明。 - rayryeng

Answer 3

现在这是我的方法，就像在评论中提到的-

另一种方法：从起点到终点画一条直线。 这条线确实是一个向量。 CW曲线大部分在此线的右侧。对于CCW，左侧。

我写了一个示例代码来阐述这个想法。 大部分解释可以在代码的注释中找到。

clear;clc;close all

%% draw a spiral curve
N = 30;
theta = linspace(0,pi/2,N); % a CCW curve
rho = linspace(1,.5,N);
[x,y] = pol2cart(theta,rho);
clearvars theta rho N

plot(x,y);
hold on

%% find "the vector"
vec(:,:,1) = [x(1), y(1); x(end), y(end)]; % "the vector"

scatter(x(1),y(1), 200,'s','r','fill') % square is the starting point
scatter(x(end),y(end), 200,'^','r','fill') % triangle is the ending point
line(vec(:,1,1), vec(:,2,1), 'LineStyle', '-', 'Color', 'r')

%% find center of mass
com = [mean(x), mean(y)]; % center of mass

vec(:,:,2) = [x(1), y(1); com]; % secondary vector (start -> com)

scatter(com(1), com(2), 200,'d','k','fill') % diamond is the com
line(vec(:,1,2), vec(:,2,2), 'LineStyle', '-', 'Color', 'k')

%% find rotation angle
dif = diff(vec,1,1);
[ang, ~] = cart2pol(reshape(dif(1,1,:),1,[]), reshape(dif(1,2,:),1,[]));
clearvars dif

% now you can tell the answer by the rotation angle
if ( diff(ang)>0 )
    disp('CW!')
else
    disp('CCW!')
end

通过比较两个向量，即将旋转向量[起点 -> 质心]旋转到向量[起点 -> 终点]，然后将旋转角度与0进行比较，可以始终确定点在有向线(向量)的哪一侧。几秒钟的思维动画可以帮助理解。

- Yvon

---

不无用！+1 我的投票...大约 22 分钟后。我已达到今天的最大投票次数。 - rayryeng