我正在寻找/尝试开发一种与矩形相交的最佳算法。我正在测试的多边形没有孔。
像此处和这里适用于非常一般的多边形，并且解决方案非常复杂，这是可以理解的。
希望 SO 社区可以帮助我记录仅使用直线多边形的特殊情况的算法。
我正在寻找下图中用绿色填充的多边形：
I am looking for / trying to develop an optimal algorithm for rectilinear polygon intersection with rectangles. The polygons I am testing do not have holes.
Answers like those given here and here are for very general polygons, and the solutions are understandably quite complex.
Hoping that the S.O. community can help me document algorithms for the special cases with just rectilinear polygons.
I am looking for the polygon filled in green in the image below:
发布评论
评论（2）
Preparata 和 Shamos 所著的《计算几何：简介》一书有一章介绍直线多边形。
The book Computational Geometry: an Introduction by Preparata and Shamos has a chapter on rectilinear polygons.
使用扫描线算法，利用直线多边形由其顶点定义的事实。
表示顶点及其所属的矩形，即类似
(x, y, #rect)的内容。将所有边相交产生的点添加到这组点中。这些新点的形式为(x, y, Final)，因为我们已经知道它们属于结果点集。现在：
T中。如果它是矩形 A 中的点和 T 中矩形 B 的点的 y 坐标之间的点，则将其标记为“最终”（反之亦然）。之后，所有标记为“最终”的点都表示生成的多边形的顶点。
令 N 为总点数。进一步假设通过查找 T 来测试是否应该将一个点标记为“最终”需要花费 O(log(n)) 时间，整个算法的时间复杂度为 O(N*log(N)) 。
请注意，查找所有交点的任务可以合并到上述算法中，因为有效地查找所有交点本身通常是一种扫描线算法。另请注意，生成的一组点可能包含多个多边形，这使得从“最终”顶点重建解多边形变得稍微困难。
Use a sweep line algorithm, making use of the fact that a rectilinear polygon is defined by its vertices.
Represent the vertices along with the rectangle that they belong to, i.e. something like
(x, y, #rect). To this set of points, add those points that result from the intersections of all edges. These new points are of the form(x, y, final), since we already know that they belong to the resulting set of points.Now:
T. Mark it "final" if it's a point from rectangle A and between y-coordinates from points from rectangle B in T (or vice versa).After that, all points that are marked "final" denote the vertices of the resulting polygon.
Let N be the total number of points. Further assuming that testing whether we should mark a point as being "final" takes time O(log(n)) by looking up
T, this whole algorithm is in O(N*log(N)).Note that the task of finding all intersections can be incorporated into the above algorithm, since finding all intersections efficiently is itself a sweep line algorithm usually. Also note that the resulting set of points may contain more than one polygon, which makes it slightly harder to reconstruct the solution polygons out of the "final" vertices.