如何从指定XY平面图中查找查询点的最小面积包围多边形？

给定一个图，图中每个顶点都是XY平面内的点，且所有顶点的度数≥2（蓝色点），同时给定一个二维查询点(x, y)（红色点）。如何找出图的边的子集，使其构成包围该查询点的最小面积多边形？

示例原图：

对应的最小面积包围多边形（绿色显示）：

要找到目标多边形，本质是定位图中包含查询点的最内层简单环，具体步骤如下：

• 检测点与环的包含关系：用射线法判断查询点是否在某个环内部。从查询点出发引一条水平射线，统计射线与环边的交点数量——若为奇数，说明点在环内；偶数则在外部。需注意处理射线经过边端点、与边共线的特殊情况，避免误判。
• 枚举所有包含查询点的简单环：因为图中所有顶点度数≥2，图由环或环相连的结构组成。用DFS回溯法枚举所有简单环：从任意顶点出发记录路径，当回到路径起点时得到一个环，同时要避免重复枚举同一环（比如顺时针/逆时针的同一环）。
• 筛选最小面积环：对所有包含查询点的环，用鞋带公式计算面积。公式为：对于按顺序排列的多边形顶点$(x_1,y_1),(x_2,y_2),...,(x_n,y_n)$，面积为$\frac{1}{2}|\sum_{i=1}^n (x_i y_{i+1} - x_{i+1} y_i)|$（其中$x_{n+1}=x_1,y_{n+1}=y_1$）。最终取面积最小的环，其对应的边子集就是答案。

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