Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 17.05.2019, 22:05   #1
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию Принадлежит ли точка многоугольнику

Здравствуйте.
Такая проблема: точка (2, 1) должна показывать результат YES, но она показывает No.
Yes или No это результат который показывает программа, принадлежит ли точка многоугольнику.
Подскажите, что нужно добавить в код.


#include "pch.h"
#include <iostream>
#include <math.h>
#include <algorithm>
#include <set>



using namespace std;

#define INF 10000
set<int> S;
struct Point
{
int x;
int y;
};

bool onSegment(Point p, Point q, Point r)
{
if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
return true;
return false;

}
int orientation(Point p, Point q, Point r)
{
int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);



if (val == 0)
return 0;

return(val > 0) ? 1 : 2;

}
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);



if (o1 != o2 && o3 != o4)
{
S.insert(p1.x);
return true ;
}



if (o1 == 0 && onSegment(p1, p2, q1)) return true;


if (o2 == 0 && onSegment(p1, q2, q1)) return true;


if (o3 == 0 && onSegment(p2, p1, q2)) return true;


if (o4 == 0 && onSegment(p2, q1, q2)) return true;




return false;
}


bool isInside(Point polygon[], int n, Point p)
{

if (n < 3) return false;


Point extreme = { INF, p.y };


int x, count = 0, i = 0;
do
{
int next = (i + 1) % n;


if (doIntersect(polygon[i], polygon[next], p, extreme))
{

if (orientation(polygon[i], p, polygon[next]) == 0)
return onSegment(polygon[i], p, polygon[next]);

count++;
}
i = next;
} while (i != 0);


x = S.size();

return x & 1;
}






int main()
{
Point polygon1[] = { {-2,-2}, {0, 4}, {1, 1}, {4, 0} };
Point p = { -1, 1 }; //Yes
int n = sizeof(polygon1) / sizeof(polygon1[0]);
isInside(polygon1, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

p = { 2, 2 }; //NO
isInside(polygon1, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

cout << endl;

Point polygon2[] = { {2, 2}, {4, 4}, {6, 6}, {-3, 1}, {-1,-1}, {5, 1} };
p = { 2 , 1 };
n = sizeof(polygon2) / sizeof(polygon2[0]);
isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

p = { 3, 2 };
isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

p = { 6, 6 };
isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

p = { 3, 3 };
isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

p = { -3, 0 };
isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
S.clear();

return 0;
}
Programist_r вне форума Ответить с цитированием
Старый 18.05.2019, 10:04   #2
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Код:
#include "pch.h"
#include <iostream> 
#include <math.h>
#include <algorithm>
#include <set>
 
 
 
using namespace std;
 
// Define Infinite (Using INT_MAX caused overflow problems) 
#define INF 10000
set<int> S;
 
struct Point
{
    int x;
    int y;
};
 
// Given three colinear points p, q, r, the function checks if 
// point q lies on line segment 'pr' 
bool onSegment(Point p, Point q, Point r)
{
    if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
        q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
        return true;
    return false;
 
}
 
// To find orientation of ordered triplet (p, q, r). 
// The function returns following values 
// 0 --> p, q and r are colinear 
// 1 --> Clockwise 
// 2 --> Counterclockwise 
int orientation(Point p, Point q, Point r)
{
     int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
 
    
 
     if (val == 0)
         return 0;  //COLLINEARITY
     
     return(val > 0) ? 1 : 2; // clock or counterclock wise 
    
}
 
// The function that returns true if line segment 'p1q1' 
// and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
 
         // Find the four orientations needed for general and 
    // special cases
    int o1 = orientation(p1, q1, p2);
    int o2 = orientation(p1, q1, q2);
    int o3 = orientation(p2, q2, p1);
    int o4 = orientation(p2, q2, q1);
 
    
    // General case
    if (o1 != o2 && o3 != o4)
    {
        S.insert(p1.x);
        return true ;
    }
 
    
    // Special Cases
    // p1, q1 and p2 are colinear and p2 lies on segment p1q1
    if (o1 == 0 && onSegment(p1, p2, q1)) return true;
    
    // p1, q1 and p2 are colinear and q2 lies on segment p1q1
    if (o2 == 0 && onSegment(p1, q2, q1)) return true;
 
    // p2, q2 and p1 are colinear and p1 lies on segment p2q2
    if (o3 == 0 && onSegment(p2, p1, q2)) return true;
 
    // p2, q2 and q1 are colinear and q1 lies on segment p2q2
    if (o4 == 0 && onSegment(p2, q1, q2)) return true;
 
 
    
 
    return false; // Doesn't fall in any of the above cases
}
 
// Returns true if the point p lies inside the polygon[] with n vertices
bool isInside(Point polygon[], int n, Point p)
{
    // There must be at least 3 vertices in polygon[]
    if (n < 3)  return false;
 
    // Create a point for line segment from p to infinite
    Point extreme = { INF, p.y };
 
    // Count intersections of the above line with sides of polygon
    int x, count = 0, i = 0;
    do
    {
        int next = (i + 1) % n;
 
        // Check if the line segment from 'p' to 'extreme' intersects
        // with the line segment from 'polygon[i]' to 'polygon[next]'
        if (doIntersect(polygon[i], polygon[next], p, extreme))
        {
            // If the point 'p' is colinear with line segment 'i-next',
            // then check if it lies on segment. If it lies, return true,
            // otherwise false
            if (orientation(polygon[i], p, polygon[next]) == 0)
                return onSegment(polygon[i], p, polygon[next]);
 
            count++;
        }
        i = next;
    } while (i != 0);
 
    // Return true if count is odd, false otherwise
    x = S.size();
    //cout<<x<<endl;
    return x & 1;  // Same as (count%2 == 1)
}
 
 
 
 
 
// Driver program to test above functions
int main()
{
    Point polygon1[] = { {-2,-2}, {0, 4}, {1, 1}, {4, 0} };   //точки многоугольника
    Point p = { -1, 1 };                                                      //точка которую проверяем на наличие её в многоугольнику  
    int n = sizeof(polygon1) / sizeof(polygon1[0]);               // количество вершин многоугольника          
    isInside(polygon1, n, p) ? cout << "Yes \n" : cout << "No \n";   // проверка
    S.clear();
 
    p = { 2, 2 };                                                           //NO
    isInside(polygon1, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
 
    cout << endl;
 
    Point polygon2[] = { {2, 2}, {4, 4}, {6, 6}, {-3, 1}, {-1,-1}, {5, 1} };
     p = { 2 , 1 };
     n = sizeof(polygon2) / sizeof(polygon2[0]);
    isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
 
    p = { 3, 2 };
    isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
 
    p = { 6, 6 };
    isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
 
    p = { 3, 3 };
    isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
 
    p = { -3, 0 };
    isInside(polygon2, n, p) ? cout << "Yes \n" : cout << "No \n";
    S.clear();
        return 0;
}
Programist_r вне форума Ответить с цитированием
Старый 18.05.2019, 10:04   #3
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Так думаю будет лучшее видно
Programist_r вне форума Ответить с цитированием
Старый 18.05.2019, 12:11   #4
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

точка (2, 1) должна показывать результат YES, но она показывает No.

Что нужно ещё добавить в код, чтобы решить эту проблему?
Programist_r вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Сколько из заданных точек принадлежит данному звездному многоугольнику Programist_r Помощь студентам 9 12.05.2019 11:54
Принадлежит ли точка прямоугольнику? - C++ _D4rki_ Помощь студентам 2 08.03.2017 20:54
Определить принадлежит ли точка Nairs Помощь студентам 11 10.10.2015 13:56
С#. принадлежит ли точка треугольнику pro100saniok Общие вопросы .NET 7 21.06.2010 14:16