多边形相交的简单算法 [英] A simple algorithm for polygon intersection

问题描述

我正在寻找一种非常简单的算法来计算多边形相交/剪裁.也就是说，给定多边形 P、Q，我希望找到包含在 P 中的多边形 TQ，我希望 T 在所有可能的多边形中是最大的.

I'm looking for a very simple algorithm for computing the polygon intersection/clipping. That is, given polygons P, Q, I wish to find polygon T which is contained in P and in Q, and I wish T to be maximal among all possible polygons.

我不介意运行时间(我有几个非常小的多边形)，我也可以得到多边形相交的近似值(即点数较少的多边形，但它仍然包含在多边形的交点).

I don't mind the run time (I have a few very small polygons), I can also afford getting an approximation of the polygons' intersection (that is, a polygon with less points, but which is still contained in the polygons' intersection).

但对我来说，算法简单(测试成本更低)并且最好短(代码更少)对我来说非常重要.

But it is really important for me that the algorithm will be simple (cheaper testing) and preferably short (less code).

请注意，我希望获得一个表示相交的多边形.对于两个多边形是否相交的问题，我不需要只需要一个布尔值的答案.

edit: please note, I wish to obtain a polygon which represent the intersection. I don't need only a boolean answer to the question of whether the two polygons intersect.

推荐答案

我知道原发帖人正在寻找一个简单的解决方案，但不幸的是，确实没有简单的解决方案.

I understand the original poster was looking for a simple solution, but unfortunately there really is no simple solution.

尽管如此，我最近创建了一个开源免费软件裁剪库(用 Delphi、C++ 和 C# 编写)，它可以裁剪各种多边形(包括自相交的多边形).这个库使用起来非常简单:http://sourceforge.net/projects/polyclipping/ .

Nevertheless, I've recently created an open-source freeware clipping library (written in Delp C++ and C#) which clips all kinds of polygons (including self-intersecting ones). This library is pretty simple to use: http://sourceforge.net/projects/polyclipping/ .

这篇关于多边形相交的简单算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！