Коллинеарные точки C ++ - PullRequest
Новая
       28

Коллинеарные точки C ++

0 голосов
/ 06 июля 2018

У меня есть скрипт, который просит вас ввести число n и после этого просит вас ввести n количество (x, y) точек .

В конце сценарий сортировки (x, y) указывает относительно x

Мне нужно обнаружить коллинеарные точки и удалить их, чтобы скрипт имел только точки в общем положении.

Например:

Input 

10
8   16
2   16
5   9
9   16
15  18
3   17
8   10
3   12
10  17
5   17

выход 

2 16
3 12
5 9
5 17
8 10
9 16
10 17
15 18

Мой сценарий такой: 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
int n,m;
class punto{
private:
    int x;
    int y;
public:
    punto();
    ~punto(){}
    void setx(int xn){ x = xn;}
    void sety(int yn) { y = yn; }
    void printcoord();

    friend bool compare_x(const punto& lhs, const punto& rhs);
    friend bool compare_y(const punto& lhs, const punto& rhs);
    };
punto::punto()
{
    x=0;
    y=0;
}
void punto:: printcoord()
{
    cout << x << " " << y << endl;
}
bool compare_x(const punto& lhs, const punto& rhs) {
    if (lhs.x == rhs.x)
        return lhs.y < rhs.y;
    return lhs.x < rhs.x;
}

int main()
{
    vector<punto> list;
            int x;
        int y;
        punto *p1;
    cin >>n;
    for(int contador=0; contador<n; contador++){
        if(contador<n){
                cin >> x;
                cin >> y;
                p1=new punto;
                p1->setx(x);
                p1->sety(y);
                list.push_back(*p1);
                cin.get();
            }
        }
    vector<punto>::iterator it;
     std::sort(list.begin(), list.end(), compare_x);
     for ( it = list.begin(); it != list.end(); ++it ) {
            it->printcoord();
     }
    return 0;
}

Как видите, мне не хватает функции для определения коллинеарных точек и их удаления.

Буду очень признателен за любую помощь!

1 Ответ

0 голосов
/ 06 июля 2018

Используйте точечное произведение. Пусть a, b, c - три точки. Если все три точки лежат на одной прямой, то вектор b-a и вектор c-a будут иметь точечное произведение | b-a || c-a |.

Это связано с тем, что cos (angle (bac)) = точка (b-a, c-a) / (mag (b-a) * mag (c-a)). Если они коллинеарны, то угол равен нулю. Косинус для нуля равен единице, поэтому точка (б-а, с-а) == МАГ (б-а) * МАГ (с-а) означает, что они коллинеарны.

Если ваши навыки линейной алгебры ржавые или отсутствуют, то вот освежающий курс 

dot(w,v) = w.x*v.x + w.y*v.y
mag(v)=sqrt(v.x*v.x + v.y*v.y)

Хитрость в том, чтобы как-то удалить дорогостоящую функцию квадратного корня. Выравнивая обе стороны, вы получаете 

mag^2(v)=v.x*v.x+v.y*v.y 
cos^2(0)=1^2=1
dot^2(w,v)=(w.x*v.x + w.y*v.y)*(w.x*v.x + w.y*v.y)

просто сделайте проверку 

if( (v.x*v.x + v.y*v.y)*(w.x*w.x + w.y*w.y)) == (w.x*v.x + w.y*v.y)*(w.x*v.x + w.y*v.y) )
...