将形状跟踪到最大 n 边的多边形中 [英] Trace a shape into a polygon of max n sides

问题描述

我正在寻找一种算法，它可以在表面上找到一个不规则的形状，也许不是太不规则，比如一个被压扁的圆，并在形状周围追踪一个最多 n 边的多边形.'n' 最大值可能取决于形状的面积.

I'm looking for an algorithm that will find an irregular shape, maybe not too irregular, like a squashed circle, on a surface, and trace a polygon of a maximum of n sides around the shape. The 'n' maximimum might be based on the area of the shape.

推荐答案

我会这样做:

1. 计算所有曲线段的切角ang及其变化dang

1. compute tangent angles ang and its change dang for all curve segments

您可以为此使用 atanxy 或 atan2

you can use atanxy or atan2 for that

ang[i] = atanxy(x[i]-x[i-1],y[i]-y[i-1]);
dang[i] = ang[i]-ang[i-1];

寻找拐点(黑色)

在这些点上，dang 的符号正在发生变化

at these points the sign of dang is changing so

dang[i-1]*dang[i+1]<0.0

但您需要正确处理 dang=0.0 元素(需要在它们之前和之后扫描).这些点将成为输出多边形的基本骨架

but you need to handle the dang=0.0 elements properly (need to scan before and after them). These points will be the fundamental skeleton for your output polygon

添加颠簸最大点(绿色)

在这些点处，切角在最近的折点之间，因此要找到两个折点之间的最大点 i0 和 i1 找到最接近的角度

at these points the tangent angle is between nearest inflex points so to find max point between two inflex points i0 and i1 find the closest angle to

angavg=0.5*(ang[i0]+ang[i1])

别忘了

|ang[i]-angavg|<=PI

所以 +/- 2.0*PI 如果这不是真的

so +/- 2.0*PI if this is not true

现在您应该拥有闭合多曲线的所有重要点...

应该是这样的:

CW/CCW 或 Red/Blue 只代表 dang[i] ...

CW/CCW or Red/Blue just represents the sign of dang[i] ...

[备注]

应该保留输出点类型(inflex/maxpoint)，因为它可以在以后用于形状的比较和检测...

The output point type should be preserved (inflex/maxpoint) because it can be later used for comparison and detection of shapes ...

这篇关于将形状跟踪到最大 n 边的多边形中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！