查找非规则 2D 形状的最长完全内部线的算法？
Algorithm to find the longest fully-internal line of a non-regular 2D-shape?
我最近一直在做一些图像处理，正在寻找一种算法来确定最长的完全在不规则形状内的线段。换句话说，线段应该是最长的线段，它在其端点难以捉摸地接触到形状。
形状可以表示为一组 (x,y) 坐标或二进制数组。最外层的像素（边缘）已经确定。
一个简单的例子是椭圆，它的解是长轴。一个更复杂的例子是等边三角形，它会在紧邻两个单独角的两个像素之间形成一条线。我的大部分形状都是椭圆形或 'worm-like'（长而波浪形）。
最终我希望使用此方法将 'worm-like' 形状分成它们的段，使用一系列 'cuts' 近似垂直于这条线。我希望这条消息形成的线比回归确定的线更适合这项任务。应该注意的是，这些形状是高分辨率的，因此可能包含多达 1000 个边缘像素，这就是为什么我试图避免简单的 iterative/brute 力方法。
感谢您的所有建议！
以下是一些可视化效果：
我相信，如果我正确理解了这个问题，那么与您要实现的目标类似的东西在计算机视觉文献中称为 平面形状分解。它并不完全相同（没有找到形状中最长的线），而是一种 分解 形状为线分隔的 有意义 段用于以后的形状分析或形状匹配操作（这可能对您想要的有用）。
在下面找到从后面引用的论文 (1) 中提取的示例图像：
如果这是你想要实现的（或多或少），请查看以下论文以了解计算形状分解的方法（并参考其他方法的参考书目）：
(1) 平面形状分解变得简单：
http://bmvc2015.swansea.ac.uk/proceedings/papers/paper013/index.html
我不确定我的想法是否完全正确，但对我来说这听起来是一个 PCA 问题，或者在计算机图形学中是一个面向对象的边界框问题。
示例：
该框的最长轴将是您最长的线。
网上有很多关于如何计算这个盒子的教程，但是步骤很简单：
- 计算你的分数的 PCA
- 计算你的点在第一个主成分上的投影
- 获取最大值-最小值
- 将特征空间中的 (max,0,0) 和 (min,0,0) 重新投影到 XYZ
- 在它们之间画一条线
请注意，这仅适用于凸图形。椭圆体、三角形都可以，但它会计算 "L" 形状的几何对象的对角线。如果您知道您的对象将是凸的，那么这是获得 "longest internal line" 的最快和最简单的方法（因为如果它是凸的，则点之间的所有线都是 "internal"）。如果您的对象是非凸的，那么您需要以某种方式将它们分成凸的小节，例如正如@imaluengo 所建议的那样。
我最近一直在做一些图像处理，正在寻找一种算法来确定最长的完全在不规则形状内的线段。换句话说，线段应该是最长的线段，它在其端点难以捉摸地接触到形状。
形状可以表示为一组 (x,y) 坐标或二进制数组。最外层的像素（边缘）已经确定。 一个简单的例子是椭圆，它的解是长轴。一个更复杂的例子是等边三角形，它会在紧邻两个单独角的两个像素之间形成一条线。我的大部分形状都是椭圆形或 'worm-like'（长而波浪形）。
最终我希望使用此方法将 'worm-like' 形状分成它们的段，使用一系列 'cuts' 近似垂直于这条线。我希望这条消息形成的线比回归确定的线更适合这项任务。应该注意的是，这些形状是高分辨率的，因此可能包含多达 1000 个边缘像素，这就是为什么我试图避免简单的 iterative/brute 力方法。
感谢您的所有建议！
以下是一些可视化效果：
我相信，如果我正确理解了这个问题，那么与您要实现的目标类似的东西在计算机视觉文献中称为 平面形状分解。它并不完全相同（没有找到形状中最长的线），而是一种 分解 形状为线分隔的 有意义 段用于以后的形状分析或形状匹配操作（这可能对您想要的有用）。
在下面找到从后面引用的论文 (1) 中提取的示例图像：
如果这是你想要实现的（或多或少），请查看以下论文以了解计算形状分解的方法（并参考其他方法的参考书目）：
(1) 平面形状分解变得简单： http://bmvc2015.swansea.ac.uk/proceedings/papers/paper013/index.html
我不确定我的想法是否完全正确，但对我来说这听起来是一个 PCA 问题，或者在计算机图形学中是一个面向对象的边界框问题。
示例：
该框的最长轴将是您最长的线。
网上有很多关于如何计算这个盒子的教程，但是步骤很简单：
- 计算你的分数的 PCA
- 计算你的点在第一个主成分上的投影
- 获取最大值-最小值
- 将特征空间中的 (max,0,0) 和 (min,0,0) 重新投影到 XYZ
- 在它们之间画一条线
请注意，这仅适用于凸图形。椭圆体、三角形都可以，但它会计算 "L" 形状的几何对象的对角线。如果您知道您的对象将是凸的，那么这是获得 "longest internal line" 的最快和最简单的方法（因为如果它是凸的，则点之间的所有线都是 "internal"）。如果您的对象是非凸的，那么您需要以某种方式将它们分成凸的小节，例如正如@imaluengo 所建议的那样。