标签: computational-geometry

我有两个位图,我想只在像素位于由四个角(四边形)定义的区域内时才将像素从A复制到B. 位图A和B具有相同的大小,并且四边形被定义为图像的像素空间中的四个{x,y}坐标.

最糟糕的情况我可以测试每个像素的中心对着四边形,看看像素的中心是否在四边形内,但这非常慢.什么是更好的算法？

给定一组n点,我们能找到三个点来描述最小面积的三角形O(n^2)吗？如果是,如何,如果没有,我们能做得更好O(n^3)吗？

我发现一些论文表明这个问题至少和要求找到三个共线点(一个面积为0的三角形)的问题一样困难.这些论文O(n^2)通过将其简化为三和问题的实例来描述该问题的解决方案.然而,我无法找到任何我感兴趣的解决方案.请参阅此(查找一般位置)以获取此类论文以及有关3-sum的更多信息.

我一直在审查算法，这是Anany Levitin的算法书中的问题。

您在实线上有n个打开间隔（a1，b1），...，（an，bn）的列表。（一个开放区间（a，b）严格包含其端点a和b之间的所有点，即（a，b）=（xi a <x <b}。）找出这些区间中具有共同点的最大数目例如，对于时间间隔（1、4），（0、3），（-1.5、2），（3.6、5），此最大数为3。为此问题设计一种算法，其算法优于二次方程时间效率。

任何人都可以帮助我为它形成算法或在互联网上建议任何资源。

谢谢，哈琳德拉

我有一些线,他们的交集描述了一个多边形,如下所示:

我知道线的顺序和它们的方程式.

为了找到内部角度,我找到了每个线的方向.但是我很困惑,因为减去两条线的方向会产生两个不同的角度,即使我按照多边形的边排序.

例如,在下图中,如果我只是减去线条的方向,我会得到以下任何一个角度:

让我更困惑的是,当多边形不是凸面时,我的角度大于180,并且使用我的方法我根本得不到正确的角度:

我发现这种解决问题的方法是错误的.

那么,使用线条找到内部角度的最佳方法是什么？我知道对于凸多边形,我可能会找到向量,然后找到它们之间的角度,但即使对于我的例子中的P6,向量方法也会失败.

无论如何,我更喜欢一种方法,它不包括解决这个凹度问题的条件案例.

谢谢.

给定表示2D中多边形的点列表,如何确定该点是否在多边形内.

请注意,多边形可以是凹面或凸面.您还可以对点的顺序做出任何假设.

我有一组例如8分.我知道每个点之间的所有距离.是否有算法重建这些点的三维坐标.

我有一组非相交线,其中一些在顶点连接.我试图找到包含给定点的最小多边形(如果存在).因此,在下面的图像中,在所有线段的列表中,给定红色点,我想只获得蓝色线段.我正在使用Python,但可能适应其他语言的算法; 我不知道这个问题叫什么.

我有一个多面体,其面是三角形.我知道在CGAL中,Triangle_3类提供了'squared_area'方法,通过它我们可以计算三角形的面积.有什么方法可以将它应用于多面体面吗？或者有关如何计算每个方面面积的任何想法？

struct Rect
{
double left, right, top, bottom;
};

std::vector<Rect> vec;

现在我们有N(N> 1000)个矩形,什么是一个有效的算法来确定它们中的任何两个是否重叠？

更新: 所有这些矩形与坐标系平行.

我有：
-一组已知大小的点（在我的情况下，只有6个点）
-一条以x = s + t * r为特征的线，其中x，s和r是3D矢量

I need to find the point closest to the given line. The actual distance does not matter to me.

I had a look at several different questions that seem related (including this one) and know how to solve this on paper from my highschool math classes. But I cannot find a solution without calculating every distance, and I am sure there has to be a better/faster way. Performance is absolutely crucial …