如何高效确定一个多边形是凸多边形、非凸多边形还是复杂多边形？

Question

如何高效确定一个多边形是凸多边形、非凸多边形还是复杂多边形？

algorithmgeometrypolygoncomputational-geometryxlib

60

来自XFillPolygon的手册描述：

如果shape为Complex，路径可能会自相交。请注意，路径中连续重合点不被视为自相交。

如果shape为Convex，对于多边形内的每对点，连接它们的线段不会与路径相交。如果客户端已知，请指定Convex以提高性能。如果您为非凸多边形指定Convex，图形结果未定义。

如果shape为Nonconvex，路径不自相交，但形状不完全是凸的。如果客户端已知，请指定Nonconvex而不是Complex以提高性能。如果您为自相交路径指定Nonconvex，图形结果未定义。

我在使用填充XFillPolygon时遇到了性能问题，正如手册所建议的那样，我想采取的第一步是指定正确的多边形形状。目前我正在安全起见使用Complex。

有没有一种有效的算法来确定由一系列坐标定义的多边形是凸的、非凸的还是复杂的？

- hhafez

Stackoverflow 不让我删除已接受的答案，但我建议查看 Rory Daulton 的回答。 - Eugene Yokota

1

请参考此问题以获取有关检查复杂/简单多边形的信息：https://dev59.com/4G865IYBdhLWcg3wEaUx - Drew Noakes

4

FYI for the googlers: 正确答案在这里。 - Will Ness

提醒任何人：此答案在最近的更新后也是正确的！ - Discrete lizard

11个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Peter K.T. Yu · Answer 1

将Uri的代码调整到了Matlab上。希望能有所帮助。

请注意，Uri的算法仅适用于简单多边形！因此，请确保首先测试多边形是否为简单多边形！

% M [ x1 x2 x3 ...
%     y1 y2 y3 ...]
% test if a polygon is convex

function ret = isConvex(M)
    N = size(M,2);
    if (N<4)
        ret = 1;
        return;
    end

    x0 = M(1, 1:end);
    x1 = [x0(2:end), x0(1)];
    x2 = [x0(3:end), x0(1:2)];
    y0 = M(2, 1:end);
    y1 = [y0(2:end), y0(1)];
    y2 = [y0(3:end), y0(1:2)];
    dx1 = x2 - x1;
    dy1 = y2 - y1;
    dx2 = x0 - x1;
    dy2 = y0 - y1;
    zcrossproduct = dx1 .* dy2 - dy1 .* dx2;

    % equality allows two consecutive edges to be parallel
    t1 = sum(zcrossproduct >= 0);  
    t2 = sum(zcrossproduct <= 0);  
    ret = t1 == N || t2 == N;

end