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

在两点之间画一条线作为答案。请注意直线是否穿过多边形顶点 - 舍入误差可能会导致问题。