正交边多边形（凸/凹/带孔）及裁剪矩形形状内最远点求解

针对你提出的两个关于正交图形最远点求解的问题，我结合正交几何的特性整理了实用的解决思路：

首先得明确“最远点”的定义，通常分两种核心场景：

场景A：找距离边界最远的内部点 #

这个点也叫多边形的「最远内点」，对于边仅垂直/水平的正交多边形，有高效的解法：

• 核心特性：正交多边形的最远内点必然落在它的**中轴线（Medial Axis）**上。中轴线是多边形内所有到至少两条边界边距离相等的点的集合，正交多边形的中轴线由线段和90度圆弧构成。
• 操作步骤：
  1. 计算多边形的中轴线（可以用扫描线算法或者专门的正交多边形中轴线生成逻辑）；
  2. 遍历中轴线上的所有线段和圆弧，找到距离边界最远的点——这个点就是中轴线上距离所有相邻边界边距离相等的极值点。
• 带孔处理：把孔的边界也当作障碍物纳入计算，中轴线会自动绕开孔区域，同样在中轴线上找极值点即可。

场景B：找多边形的直径端点（内部两两最远的点对） #

对于任意简单多边形（包括正交类型），内部两点间的最大距离（即多边形直径）必然在顶点上取得；如果是带孔多边形，孔的顶点也要纳入考虑。具体操作：

• 收集外边界的所有顶点和所有孔的顶点；
• 枚举所有顶点对，计算它们的欧氏距离（或曼哈顿距离，根据需求选择）；
• 记录最大距离对应的点对，这两个点就是内部的最远点对。

这个形状本质是由单个矩形裁剪同方向矩形得到的连通正交多边形（可能带孔），边缘由各矩形的边拼接而成。结合你给出的“最远”定义（仅考虑包含点A的连通多边形P），这里的最远点指的是形状内部两两距离最大的边缘点（即形状直径的端点，或直径所在边缘上的所有点）。

解决思路：

1. 合并矩形组为统一多边形：把相邻矩形的重合边合并，提取出整个形状的外边界（如果有孔，还要提取孔的边界），得到完整的连通正交多边形；
2. 提取边缘顶点：收集合并后多边形的所有外边界顶点和孔的顶点（这些都是形状的边缘点）；
3. 计算最大距离并筛选最远点：
   • 枚举所有顶点对，计算距离，找出最大距离值D；
   • 所有与其他顶点距离等于D的顶点，都是候选最远点；
   • 额外检查：如果最大距离是某个顶点到一条平行边缘线段的垂直距离，那么这条线段上的所有点到该顶点的距离都等于D，这些点也属于最远点（比如一个完整的矩形边作为形状边缘，它的对顶点到这条边上所有点的距离都相等且是最大值）。

举个实际例子：如果原矩形是10x10，裁剪掉左上角2x2的小矩形，合并后的外边界顶点是(0,2)、(0,10)、(10,10)、(10,0)、(2,0)、(2,2)，最大距离是(0,10)到(10,0)的欧氏距离（约14.14），这两个点就是边缘最远点；如果是从中间挖掉2x2的矩形，孔的顶点也要纳入计算，但最大距离通常还是外边界的对角顶点。

内容的提问来源于stack exchange，提问作者user19087