计算三角形内的晶格点 [英] Counting lattice points inside a triangle
问题描述
我已经指出了一个大三角形,所以将其称为a,b,c。 (a =(x,y)依此类推。)
I've points for a big triangle lets call it a, b, c. (a = (x, y) and so on).
现在,我想计算该三角形围成的区域内的积分点数,因此我首先看一下在匹克定理中。我考虑的第二种方法是生成一个以三角形的最大值,最小值为边界的点的列表,然后检查每个点是否位于三角形内。
Now I want to count the number of integral points inside the area enclosed by this triangle, so I first looked at Pick's theorem. The second approach that I considered was generating a list of points bounded by max, min of the triangle, and then checking if each point lies inside the triangle.
我使用了重心坐标法可以做到这一点。它可以工作,但是我的三角形很大,我的程序基本上是跨点的蛮力。我如何改进此算法?
I used the Barycentric coordinates method to do this. It works however my triangle is pretty huge and my program is basically a brute force across points. How do I improve on this algorithm?
可以在这里找到我的代码: https://bpaste.net/show/58433b6e389c
My code can be found here: https://bpaste.net/show/58433b6e389c
推荐答案
可以并且应该解决此问题使用皮克定理。阅读本文可全面了解它的工作原理,它将适用于您能想到的任何多边形。因此, Pick说说,如果要计算多边形的面积,则公式为 area = noOfInsidePoints + noOfBoundaryPoints / 2-1
。要计算任何多边形的面积,可以使用以下代码,其中 pc
是表示多边形顶点的结构数组。
This problem can and should be solved using Pick's theorem. Read the article to have a full understanding on how it works and it will work for any polygon you can think of. So, "Pick says" that if you want to compute the area of a polygon you have the formula area = noOfInsidePoints + noOfBoundaryPoints /2 - 1
. To compute the area of any polygon you can use the following code, where pc
is an array of structures representing the vertices of the polygon.
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);
}
计算出面积后,我们必须计算所有多边形边缘。可以使用以下方法完成此操作:
Having the area computed, we have to count the number of point from all of the polygon edges. This can be done using the following:
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;
}
}
也对此进行了计算,我们可以找到
Having this computed too, we can find the number of point inside
noPointsInside = (computeArea() - (getBoundaryPoints() - n)) / 2 + 1;
最终时间复杂度:O(N)
最终内存复杂度:O(N)
Final time complexity: O(N) Final memory complexity: O(N)
这篇关于计算三角形内的晶格点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!