确定多边形上线段的最佳起点和终点
Determining best start and end points for line segment on polygon
我无法找到解决以下问题的最佳方法。我尝试了多种解决问题的方法，但我总是 运行 遇到一些极端情况。
问题如下：
- 您有
List 个坐标（x 和 y 点）形成一个闭合多边形。此列表保证形成一个点按顺时针方向排列的多边形。
- 你得到了
Set 个坐标（x 和 y 点），这些坐标来自上面的 List 个坐标。
- 你必须计算出使用上面所有点组成的直线的起点和终点
Set。
我遇到的问题是我想不出找到 'best' 起点和终点的方法。对于许多情况，您可以选择第一个点和最后一个点（使用 List 的索引）来形成起点和终点，但是这可能会导致一条线比它必须的要长。
例如，假设我们有以下多边形：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0
我们的线段必须包含以下 Set 坐标：0, 7, 3。
如果我们找到最小和最大索引，我们得到 index(0)、index(7)，因此我们可以形成线 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，这是一条有效的线，但它比它需要。最好的线段是 7 -> 0 -> 1 -> 2 -> 3.
如何有效地找到最佳（包含 Set 中所有点的最短）线段？
对于上下文：我正在开发一个使用 JTS Geometries 绘制形状的应用程序。使用贝塞尔曲线对绘制的形状进行平滑处理，得到 'curved edges'。绘制形状（通过放置点）后，用户可以编辑形状。我们想用他们修改的点（形成上面的Set）找出起点和终点，这样我们就可以'smooth'只有受影响的区域。
所以我们有一个 Set，我们需要按照索引的顺序将这个集合放入 List。
转换 ISet = [Index(i, List) for i in Set]
下一个排序ISet
对于 ISet 中的成对连续项目和这对（最后一个，第一个）计算该对的距离。
对距离最大的一对进行了罚款。那么最好的结束和开始就是那一对。
将你的集合转换为排序列表，将这个列表与其副本连接起来，其中每个元素都添加了多边形顶点数 N，然后在这个双列表中找到最长的空 运行（相邻差异）。然后获取所需长度的子列表，将其转换为连续范围（但取元素模 N）
(0,3,7) + (0+8,3+8,7+8) = (0,3,7,8,11,15)
最大差值是7-3，所以最好的子列表以7开头，就是
(7%8 .. 11%8) = (7,0,1,2,3)
我无法找到解决以下问题的最佳方法。我尝试了多种解决问题的方法，但我总是 运行 遇到一些极端情况。
问题如下：
- 您有
List个坐标（x 和 y 点）形成一个闭合多边形。此列表保证形成一个点按顺时针方向排列的多边形。 - 你得到了
Set个坐标（x 和 y 点），这些坐标来自上面的List个坐标。 - 你必须计算出使用上面所有点组成的直线的起点和终点
Set。
我遇到的问题是我想不出找到 'best' 起点和终点的方法。对于许多情况，您可以选择第一个点和最后一个点（使用 List 的索引）来形成起点和终点，但是这可能会导致一条线比它必须的要长。
例如，假设我们有以下多边形：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 0
我们的线段必须包含以下 Set 坐标：0, 7, 3。
如果我们找到最小和最大索引，我们得到 index(0)、index(7)，因此我们可以形成线 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7，这是一条有效的线，但它比它需要。最好的线段是 7 -> 0 -> 1 -> 2 -> 3.
如何有效地找到最佳（包含 Set 中所有点的最短）线段？
对于上下文：我正在开发一个使用 JTS Geometries 绘制形状的应用程序。使用贝塞尔曲线对绘制的形状进行平滑处理，得到 'curved edges'。绘制形状（通过放置点）后，用户可以编辑形状。我们想用他们修改的点（形成上面的Set）找出起点和终点，这样我们就可以'smooth'只有受影响的区域。
所以我们有一个 Set，我们需要按照索引的顺序将这个集合放入 List。
转换 ISet = [Index(i, List) for i in Set]
下一个排序ISet
对于 ISet 中的成对连续项目和这对（最后一个，第一个）计算该对的距离。
对距离最大的一对进行了罚款。那么最好的结束和开始就是那一对。
将你的集合转换为排序列表，将这个列表与其副本连接起来，其中每个元素都添加了多边形顶点数 N，然后在这个双列表中找到最长的空 运行（相邻差异）。然后获取所需长度的子列表，将其转换为连续范围（但取元素模 N）
(0,3,7) + (0+8,3+8,7+8) = (0,3,7,8,11,15)
最大差值是7-3，所以最好的子列表以7开头，就是
(7%8 .. 11%8) = (7,0,1,2,3)