查找中点(计算几何c++)

程序应该读取一个整数N作为输入，然后是N个点的x和y坐标返回集合中任意两个点的中间点的个数。首先，程序将点存储在一个数组中，然后循环遍历这些点并计算点[i]与其他所有点之间的距离。我们根据这个距离对点进行排序然后如果我们发现任意两个点有相同的距离我们检查点[i]是否与它们对齐如果是的话我们将点[i]存储在中间列表中。然后去掉列表中的双精度对象并返回列表的大小。我提交了我的解决方案，但它并不适用于所有的情况。请帮忙:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stdio.h>
using namespace std;
struct Point
{
    int x;
    int y;
    int distance;
};
bool PointSort(Point a,Point b);
bool colinear(Point a,Point b,Point c);
bool same_point (Point first, Point second);
int main()
{
    list<Point> middles;
    int N;scanf("%d", &N);
    Point points[N];
    Point points2[N];
    for(int i=0;i<N;i++)
    {   scanf("%d", &points[i].x);
        scanf("%d", &points[i].y);
        points2[i].x=points[i].x;
        points2[i].y=points[i].y;
    }
    for(int i=0;i<N;i++)
    {
         for(int j=0;j<N;j++)
         {
            points2[j]=points[j];
         }
         for(int j=0;j<N;j++)
         {
            points2[j].distance=(points[i].x-points2[j].x)*(points[i].x-    points2[j].x)+(points[i].y-points2[j].y)*(points[i].y-points2[j].y);
         }
         sort(points2,points2+N,&PointSort);
         for(int j=0;j<N;j++)
         {
            int k=j+1;
            while(points2[j].distance==points2[k].distance)
            {
                 bool coli=colinear(points[i],points2[j],points2[k]);
                 if(coli){middles.push_back(points2[i]);}
                 k++;
            }
         }
     }
    middles.unique(same_point);
    cout<<middles.size();

}
bool PointSort(Point a,Point b)
{
    return a.distance<b.distance;
}
bool colinear(Point a,Point b,Point c)
{
    return (a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y))/2.0==0.0;
} 
bool same_point (Point first, Point second)
{ return (first.x==second.x && first.y==second.y) ; }

您实际上不需要计算距离来检查某些东西是否为中点。A和B之间的中点坐标为M=(A+B)/2。或者，为了让所有的都是整数，A+B=2M, M是中点。下面是解决这个问题的伪代码:

for ( A=0; A<N-1; A++ ) {
    for ( B=A+1; B<N; B++ ) {
        M2 = A+B;
        for ( C=0; C<N; C++ ) {
            if ( C*2 == M2 ) {
               // C is the midpoint of A and B
            }
        }
    }
}

我发现您的代码存在以下潜在问题:

你的代码计算点对之间的距离平方(而不是说明的距离)。由于计算是使用整数算术完成的，因此有可能发生算术溢出。
你的代码删除了所有发现有重复x和y坐标的中点。但是，这是问题表述所要求的吗?如果重复点实际上出现在输入流中，并且恰好是其他一些点的中点，是否应该忽略第二个和所有随后的重复点?同样，如果一个点在输入流中重复了三次(或更多)，那么这算多少个中点?您应该仔细检查问题声明，看看应该如何计算输入流中的重复项，并精确地遵循要求。

你的共线性检查看起来不对。你似乎是在尝试用(points[i] - points2[j])与(points[i] - points2[k])的二维交叉，但这不是正确的方法。下面是如何拍摄2d十字架:

int cross2d(Point a, Point mid, Point c)
{
    // Take the 2d cross product (a - mid) X (c - mid).
    // 2d cross = (u.x * v.y - u.y * v.x) where u = (a-mid) and v=(c - mid)
    int cross = (a.x - mid.x) * (c.y - mid.y) - (a.y - mid.y) * (c.x - mid.x);
    return cross;
}
bool collinear(Point a, Point mid, Point c)
{
    // Check for the points being collinear (or degenerate, i.e. return true if a == mid or mid == c).
    return cross2d(a, mid, c) == 0;
}

同样，对于坐标大且几乎垂直的点三元组，整数溢出是一个潜在的问题。如果你不想做一个二维的交叉，你想做什么?

你正在尝试创建一个O(n平方)算法，通过从某个预期中点的距离对点进行排序。这是值得赞扬的，但由于您的代码无法工作，我将首先创建一个简单的O(n-立方)算法来直接解决问题。然后你可以用它来对改进的n平方算法进行单元测试。
在你的数学表达式中添加一些空格可以使它们更容易阅读。

首先，这是朴素n立方算法。请注意，我在输入流中保留了重复项，同时避免重复计算作为多对点的中点的点:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <list>
#include <stdio.h>
using namespace std;
struct Point
{
    int x;
    int y;
    int id;
};
bool is_middle(Point a, Point middle, Point c);
bool same_point_id(Point first, Point second);
int main()
{
    list<Point> middles;
    int N;
    scanf("%d", &N);
    // https://stackoverflow.com/questions/25437597/find-middle-pointscomputational-geometry-c
    // This program should read for input an integer N then the x and y coordinates of the N points 
    // and return the number of points that are the middle points of any two other points in the set. 
    Point *points = new Point[N];
    for(int i=0;i<N;i++)
    {   
        scanf("%d", &points[i].x);
        scanf("%d", &points[i].y);
        points[i].id = i;
    }
    for(int i=0; i<N-2; i++)
    {
        for(int j=i+1; j<N-1; j++)
        {
            for(int k=j+1; k<N; k++)
            {
                // Check the problem requirement to determine how to count sets of three identical points in the input stream.
                if (is_middle(points[i], points[j], points[k]))
                    middles.push_back(points[j]);
                if (is_middle(points[j], points[k], points[i]))
                    middles.push_back(points[k]);
                if (is_middle(points[k], points[i], points[j]))
                    middles.push_back(points[i]);
            }
        }
    }
    // Prevent the same input point from being counted multiple times.
    middles.unique(same_point_id);
    cout<<middles.size();
    delete [] points;
}
bool is_middle(Point a, Point mid, Point c)
{
    if (a.x - c.x != 2*(a.x - mid.x))
        return false;
    if (a.y - c.y != 2*(a.y - mid.y))
        return false;
    return true;
}
bool same_point_id(Point first, Point second)
{ 
    return (first.id==second.id); 
}

Update:如果你确实需要一个n平方算法，那么根据到中点的距离平方对潜在端点进行排序并不是一个坏主意。如果你想避免潜在的算术溢出，你可以用64位long long int来计算距离的平方:

long long distance_squared(Point a, Point b)
{
    long long dx = ((long long)a.x - (long long)b.x);
    long long dy = ((long long)a.y - (long long)b.y);
    return dx*dx + dy*dy;
}

在大多数平台上，这将比普通的int类型有更多的位——当然也不会更少。

相关内容

最新更新

热门标签：