我怎么可以拆分多边形由一条线？ [英] 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?

推荐答案

我最近要做到这一点。只是走多边形不会为凹多边形的工作，如在你的图。下面是我的算法，灵感来自格雷纳 - 霍曼的草图的多边形裁剪算法。拆分为两个比多边形裁剪容易，更难。比较容易，因为你只对夹线，而不是一个矩形或多边形的另一个;更难，因为你需要保持两侧。

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屋！