相关疑难解决方法(0)

这似乎并不重要(它在各种论坛上得到了很多讨论),但我绝对需要将它作为更复杂算法的构建块.

输入:2D中的2个多边形(A和B),以[(x0, y0, x1, y2), ...]每个边的列表形式给出.这些点由doubles 对表示.我不知道它们是顺时针,逆时针还是任何方向.我不知道他们不一定是凸的.

输出:表示A,B和交叉多边形AB的3个多边形.其中任何一个都可以是空(？)多边形,例如null.

优化提示:这些多边形代表房间和楼层边界.所以房间边界通常与地面边界完全相交,除非它属于同一平面上的另一层(argh!).

我有点希望有人已经在c#中完成了这个并且让我使用他们的策略/代码,因为到目前为止我在这个问题上发现的是相当艰巨的.

编辑:所以看起来我并不完全是鸡,因为这样做的前景微弱.我想在这里重述所需的输出,因为这是一个特例,可能会使计算更简单:

输出:第一个多边形减去所有相交的位,交叉多边形(复数是正常的).我对第二个多边形并不感兴趣,只是它与第一个多边形的交集.

EDIT2:我目前正在使用GPC(General Polygon Clipper)库,这非常容易!

我正在寻找/尝试开发一种与矩形的直线多边形交叉的最佳算法.我正在测试的多边形没有洞.

像这里和这里给出的答案是非常一般的多边形,解决方案可以理解的非常复杂.

希望SO社区可以帮助我记录具有直线多边形的特殊情况的算法.

我正在寻找下图中填充绿色的多边形:

检测红色矩形是否与黑色多边形重叠的最佳方法是什么？请参考此图片:

给出了两个多边形.如何确定一个多边形是在另一个多边形的内部,外部还是相交？多边形可以是凹面或凸面.

我有一个位于2D网格中的多边形:(
假设我能够绘制一条网格,每条线之间的距离相同)

我现在正在寻找一种算法或某种实现,它可以将多边形切割成沿网格的几个较小的多边形.

C++中的一些示例代码基本上显示了我想要做的事情:

struct Point2D
{
    double x;
    double y;
}

struct Polygon
{
    std::vector<Point2D> points;
}

/**
 * givenPolygon is the 'big' polygon which should be divided
 * gridSize is the distance between the gridlines
 * return value is a vector of the resulting subpolygons
 */
std::vector<Polygon> getSubpolygons( Polygon givenPolygon, double gridSize )
{
    Code here...
}

是否有任何算法或实现的库可以做到这一点？

我有一个quad类型,定义为:

typedef struct __point {
    float x;
    float y;
} point_t;

typedef struct __quad {
    point_t p1;
    point_t p2;
    point_t p3;
    point_t p4;
} quad_t;

如果我在同一平面上有两个这样的四边形,我希望能够计算出这些四边形的交点.例如,如果我们有四A和四B,如果B的任何一个点落在A之外,那么该算法应该产生一个带有点的四边形,如下图所示(A为红色,B为紫色):

编辑:点的排序并不重要,因为我稍后会使用这些点构建一个将在A中绘制的四边形.

可能重复:
多边形交集的简单算法

我正在寻找一个关于如何快速计算两个任意定向四边形的交点的概述(没有预设的拐角或边长约束).我不是要简单地检查它们是否相交,而是希望得到构成所得交叉区域的点.我知道通常多边形交叉不是一个小问题,并且有可用的库可以做得很好.

但是因为在这个我只关注四面形状的特殊情况下,我想知道是否有一种快速方法可以使用,而不需要在我的应用程序中包含一个完整的附加库.

到目前为止,我所想到的只有:

1. 在两个形状上相对于彼此运行'多边形点'
2. 将每个多边形的每个边相互交叉

上述两个步骤是否最终得到了构成最终交叉区域的所有点？有更好的方法可以使用吗？

如果我能得到构成结果区域的点的正确排序,那也很好.这不是强制性的 - 如果你知道任何聪明/快速的方法(凸壳？)我会感激任何建议.

我不想用绘制的最后一个多边形的值覆盖多个多边形的重叠区域，而是绘制这些多边形的平均值。这在Python PIL中可能吗？

示例中的重叠像素的值应为1.5。

在完整的工作程序中，我必须在非常大的网格上绘制约100000个多边形（可能相交或不相交），这就是我使用PIL而不是Numpy的原因。

from PIL import Image, ImageDraw
import numpy as np
import matplotlib.pyplot as plt

img = Image.new('F', (50, 50), 0)

ImageDraw.Draw(img).polygon([(20, 20), (20, 40), (40, 30), (30, 20)],
                            fill=1., outline=None)
ImageDraw.Draw(img).polygon([(10, 5), (10, 25), (25, 25), (25, 10)],
                            fill=2., outline=None)

myimg = np.ma.masked_equal(np.array(img), 0.)
plt.imshow(myimg, interpolation="None")
plt.colorbar()
plt.show()