如何用线分割多边形? [英] How can I split a Polygon by a Line?

问题描述

如下图，

是否可以用线分割多边形?(分成两个多边形).如果这条线没有完全穿过多边形，它就会失败.

Is it possible to split a Polygon by a Line? (into two Polygons). If the line doesn't go all the way across the polygon it would fail.

这可能吗?如果是这样，我该怎么做?

Is this possible? If so, how would I do this?

推荐答案

我最近不得不这样做.只是走多边形对凹多边形不起作用，就像你的图表一样.下面是我的算法草图，灵感来自 Greiner-Hormann 多边形裁剪算法.分割比多边形裁剪更容易也更难.更容易，因为你只剪线而不是矩形或其他多边形；更难，因为你需要保持双方.

I had to do this recently. Just walking the polygon won't work for concave polygons, as in your diagram. Below is a sketch of my algorithm, inspired by the Greiner-Hormann polygon clipping algorithm. Splitting is both easier and harder than polygon clipping. Easier because you only clip against a line instead of a rect or another polygon; harder because you need to keep both sides.

Create an empty list of output polygons
Create an empty list of pending crossbacks (one for each polygon)
Find all intersections between the polygon and the line.
Sort them by position along the line.
Pair them up as alternating entry/exit lines.
Append a polygon to the output list and make it current.
Walk the polygon. For each edge:
    Append the first point to the current polygon.
    If there is an intersection with the split line:
        Add the intersection point to the current polygon.
        Find the intersection point in the intersection pairs.
        Set its partner as the crossback point for the current polygon.
        If there is an existing polygon with a crossback for this edge:
            Set the current polygon to be that polygon.
        Else
            Append a new polygon and new crossback point to the output lists and make it current.
        Add the intersection point to the now current polygon.

这篇关于如何用线分割多边形?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！