我有一个大三角形的点，我们称之为 a、b、c。 （a =（x，y）等）。
现在我想统计这个三角形围成的区域内有多少个积分点，所以我首先看一下皮克定理。我考虑的第二种方法是生成一个以三角形的最大值、最小值为界的点列表，然后检查每个点是否位于三角形内部。
我使用重心坐标方法来做到这一点。它有效，但是我的三角形相当大，我的程序基本上是跨点的蛮力。我如何改进这个算法？
我的代码可以在这里找到：https://bpaste.net/show/58433b6e389c https://bpaste.net/show/58433b6e389c
这个问题可以而且应该使用来解决皮克定理 https://en.wikipedia.org/wiki/Pick%27s_theorem。阅读本文以充分了解它的工作原理，并且它适用于您能想到的任何多边形。因此，“Pick 说”如果你想计算多边形的面积，你可以使用以下公式area = noOfInsidePoints + noOfBoundaryPoints /2 - 1。要计算任何多边形的面积，您可以使用以下代码，其中pc是表示多边形顶点的结构体数组。
float computeArea()
{
float area = 0;
for(int i=1;i<=n;++i) // n is the total number of vertices
area += (pc[i].x*pc[i+1].y - pc[i+1].x*pc[i].y );
if(area < 0)
area *= (-1);
}
计算出面积后，我们必须计算所有多边形边上的点数。这可以使用以下方法完成：
int getBoundaryPoints()
{
long left=0, right=0;
int noPoints = 0;
for(int i=1;i<=n;++i)
{
st = abst( pc[i].x - pc[i+1].x );
right = abs( pc[i].y - pc[i+1].y );
if(right == 0)
right = left;
if(left == 0)
left = right;
noPoints += gcd(left, right) +1;
}
}
也计算了这个，我们可以找到里面的点的数量
noPointsInside = (computeArea() - (getBoundaryPoints() - n)) / 2 + 1;
最终时间复杂度：O(N)
最终内存复杂度：O(N)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
