algorithm - 如何根据严格规范的多边形剪裁线

Question

我需要在一个非常规范的多边形上剪下一条线。多边形将始终是一个矩形，沿欧几里得轴定向，并且可能有“截断”的角。看看这张照片，看看我的意思。

可以切割拐角，以便在其中一个边缘形成一个点，但不会更多。在某些情况下（实际上，大多数情况下）不会切角，我已经实现了 Cohen-Sutherland 算法来处理这些情况，但是当切角时我不知道该怎么做。我想有一些通用算法可以根据多边形剪裁一条线，但我对此知之甚少。此外，对于我的情况，这可能是矫枉过正。我正在处理的多边形总是简单的、凹的和单调的。有什么好的（最好是简单的）算法吗？

Answer 1

这是一种方法：

For each side of a convex polygon
  p = the intersection point between line and the polygon side
  if p lies between the endpoints of the polygon side, save point p
  if there are two saved points then exit the loop
next

在两点之间画一条线作为答案。小心线是否穿过多边形顶点——舍入错误可能会导致问题。