关于常数工作空间简单多边形梯形分解算法的技术疑问

背景与待解决问题 #

我正在研究一篇常数工作空间下简单多边形梯形分解的论文（第51页3.2节），该算法采用平面扫掠法从左到右遍历多边形顶点。其中：

• 关于顶点qi右侧是否存在关联梯形的判定问题已解决
• 目前卡在多边形内部方向检测环节：当判定qi右侧存在梯形后，需判断其关联边e是否满足「端点位于qi右侧，且多边形内部在e的下方」（以此确定e是否为qi的上方边）。我试过三元组定向判断、叉积、直线方程等方法，但都无效，求可行的实现方案。

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