Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.82
greategi
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 20
#1

Точка в Многоугольнике! - C++

06.05.2012, 20:05. Просмотров 2476. Ответов 3
Метки нет (Все метки)

Задача "Точка в многоугольнике".
Условие. Многоугольник (выпуклый) задан координатами своих вершин
(xi;yi), 1 i N в порядке обхода. Определить, лежит ли точка с координатами
(x0;y0) внутри или вне многоугольника.
Входные данные содержатся в файле input.txt: в первой строке - пара чисел
(x0;y0), в каждой (i+1)-й строке - координаты i-й точки (xi;yi).
Выходные данные нужно вывести в файл output.txt: единственная строка
этого файла должна содержать одно число - 1, если точка внутри многоугольника
(или на его стороне), 0 - в противном случае. (Необезательно делать с помошью файлов)
Пример
Input.txtt Output.txt Input.txt Output.txt
5 3
1 1
6 3
7 6
4 8
2 8
1 5
Ответ
1
7 3
1 1
6 3
7 6
4 8
2 8
1 5
Ответ
0



Вот что я сделал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;
struct Point{
int x;
int y;
 
};
void main()
{
Point O,line;
Point* mass = new Point[6] ;
 
O.x=5;
O.y=3;
mass[0].x=mass[0].y=1;
mass[1].x=6;
mass[1].y=3;
mass[2].x=7;
mass[2].y=6;
mass[3].x=4;
mass[3].y=8;
mass[4].x=2;
mass[4].y=8;
mass[5].x=1;
mass[5].y=5;
 
line.y=3;
line.x=0;
 
int k=0,b=0;
int g,a, TX,TY, count,U;
//
// Y(X) = k * X + b
//Y(X1) = Y1
//Y(X2) = Y2
k = 0;
b = O.y;
 
for(int i=0;i<6;i++)
{
 
 g = (mass[i+1].y-mass[i].y)/(mass[i+1].x-mass[i].x);
 a=(mass[i].y-g*mass[i].x);
 TX = (a - b) / (k - g);
 TY = k * TX + b;
 if(TY!=0&&TX!=0)
     count++;
 
 
 if(count%2==0)
     U=1;
 else 
     U=0;
 
 
 
}
 
cout<<U;
}

Но вот выдает (Необработанное исключение в "0x00411523" в "lab7.exe": 0xC0000094: Integer division by zero.) А потом желтая стрелка указывает на TX = (a - b) / (k - g); И еше пишет что неиницыалезированая переменная count.

Добавлено через 17 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include "stdafx.h"
#include <iostream>
using namespace std;
struct tochka
 {
  int xx;
  int yy;
 };
 
void main()
{
 tochka *t;int x,y,i;
 
 cout<<"Enter x & y:\n";
 cin>>x>>y;
 
 FILE *f1;
  
  f1=fopen("tochki.txt","r");
  
  while(!feof(f1))
   {
    fscanf(f1,"%s",&t[i].xx);
    fscanf(f1,"%s",&t[i].yy);
    i++;
   }
  fclose(f1); 
 
 int maxX,minX,maxY,minY;
 maxX=t[0].xx;minX=t[0].xx;maxY=t[0].yy;minY=t[0].yy;
 for(i=0;i<i;i++)
  {
   if(t[i].xx>maxX)
    {
     maxX=t[i].xx;
    }
   if(t[i].xx < minX)
    {
     minX=t[i].xx;
    }
  }
  for(i=0;i<i;i++)
   {
    if(t[i].yy>maxY)
    {
     maxY=t[i].yy;
    }
   if(t[i].yy < minY)
    {
     minY=t[i].yy;
    }
   }
   
 for(i=0;i<i;i++)
  {
   cout<<"\n"<<i+1<<" Tochka:"<<t[i].xx<<" "<<t[i].yy;
  }
  cout<<"\nMAXX = "<<maxX<<" MINX = "<<minX<<" MAXY = "<<maxY<<" MINY = "<<minY;  
    
  if((x<maxX)&&(x>minX)&&(y<maxY)&&(y>minY))
   {
    cout<<"\n\nTochka x,y lezut v mnogokytnikom";
   }
  else cout<<"\n\nTochka x,y lezut za mnogokytnikom";  
 
  system("pause");
}
Добавлено через 1 минуту
Вот робочая прога но она для треугольника помогите сделать для многоугольника! Пожалуста ! Буду благодарен.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
    #include "stdafx.h"
    #include <iostream>
    #include <math.h>
 
    using namespace std;
 
struct point
{
   int x;
   int y;
};
//площадь
int area(point a, point b, point c)
{
   return abs((a.x - c.x)*(b.y - c.y) + (b.x-c.x)*(c.y-a.y));
}
 
int main()
{
setlocale(LC_ALL, "rus");
   /////////////////////////////////////////////////////////////////////////////
   point a, b, c, d;
   cout << "Введите сначала координаты вершин треугольника, а затем "
        << "координаты точки:" << endl;
   cin >> a.x >> a.y;
   cin >> b.x >> b.y;
   cin >> c.x >> c.y;
   cin >> d.x >> d.y;
   /////////////////////////////////////////////////////////////////////////////
   //Если точка внутри, то суммарная площадь треугольников ABK, BCK, CAK равна площади ABC. Площадь треугольника считается как 1/2 abs (x1y2-x2y1 + x2y3-x3y2 + x3y1-x1y3).
   if (area(a, b, c))
   {
      if (area(a, b, c) == area(a, b, d) + area(a, d, c) + area(b, d, c))
            cout << "Точка находится внутри треугольника\n";
      else 
            cout << "Точка находится вне треугольника\n";
   }
   else
      cout << "Треугольник не существует\n";
   /////////////////////////////////////////////////////////////////////////////
   system("pause");
   return 0;
}
Добавлено через 22 минуты
Вот еше нашел в инете функцію помогите плз


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
bool IsPointInside(Array<const Point2f> polygon, Point2f point)
{
    if (polygon.size <= 1)
        return false;
 
    int intersections_num = 0;
    int prev = polygon.size - 1;
    bool prev_under = polygon[prev].y < point.y;
 
    for (int i = 0; i < polygon.size; ++i)
    {
        bool cur_under = polygon[i].y < point.y;
 
        Point2f a = polygon[prev] - point;
        Point2f b = polygon[i]  - point;
 
        float t = (a.x*(b.y - a.y) - a.y*(b.x - a.x));
        if (cur_under && !prev_under)
        {
            if (t > 0)
                intersections_num += 1;
        }
        if (!cur_under && prev_under)
        {
            if (t < 0)
                intersections_num += 1;
        }
 
        prev = i;        
        prev_under = cur_under;        
    }
 
    return (intersections_num&1) != 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.05.2012, 20:05     Точка в Многоугольнике!
Посмотрите здесь:

Лежит ли точка в многоугольнике - C++
Многоугольник на плоскости (не обязательно выпуклый) задан своими вершинами в порядке обхода часовой стрелки проверить, лежит ли точка А...

Точки в многоугольнике - C++
В общем не давно была олимпиада. и меня меня мучает решение одной задачи: Многоугольник состоит из N (N ≤ 10000) вершин, координаты...

Локализация точки в произвольном многоугольнике - C++
Помогите пожалуйста..Надо в близжайшие 5-6 часов.....BorlandC 309-153-594 ася oksy_@list.ru Множество точек определяет многоугольник....

Посчитать количество углов в многоугольнике, образованном единицами в матрице - C++
дана матрица, состояща из 0 и 1(0 - ничего нет, 1 - есть фигура) требуется посчитать кол-во углов в фигуре, котора состоит из единичек ...

удалить из каждой группы идущих подряд цифр, которой не предшествует точка, все начальные нули (кроме последнего, если за ним идет точка) - C++
В произвольном тексте, содержащем не более 10 строк, в каждой строке не более 80 символов, удалить из каждой группы идущих подряд цифр,...

Класс "Точка". Функция - определение в каком координатном угле находится точка - C++
1. Определить в глобальной области видимости функцию в соответствии с вариантом. Доступ к полям класса осуществить с помощью...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
UFO94
264 / 253 / 13
Регистрация: 04.04.2012
Сообщений: 546
06.05.2012, 22:20     Точка в Многоугольнике! #2
Опишите, пожалуйста, ваш математический алгоритм.
И попробуйте обьявить count в отдельной строке, и всегда(!!!) инициализируйте переменные перед использованием, т.е. либо
C++
1
int count=0;
Либо
C++
1
2
3
int count;
....
count=0;
greategi
0 / 0 / 0
Регистрация: 13.02.2012
Сообщений: 20
10.05.2012, 11:04  [ТС]     Точка в Многоугольнике! #3
пробовал
C++
1
int count=0;
всеравно проблека там в той строчке !Необработанное исключение в "0x00411523" в "lab7.exe": 0xC0000094: Integer division by zero.) А потом желтая стрелка указывает на TX = (a - b) / (k - g);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2012, 19:55     Точка в Многоугольнике!
Еще ссылки по теме:

Седловая точка - C++
Элемент матрицы назовем седловой точки, если он является наименьшим в своей строке и одновременно крупнейшим в своем столбце или, наоборот,...

Точка останова - C++
Здравствуйте все! Не пойму в чём проблема. Вот так всё работает: void main() { char *c = new char ; delete c; }

Седловая точка - C++
Дана целочисленная прямоугольная матрица . Матрица А имеет седловую точку Аij, если Аij является минимальным элементом в i-ой строке и...

оператор точка - C++
почему когда объявляю свой класс в другом классе, и после использования точки, то переменная, например типа int, которю я хочу вывести,...

Треугольник и точка - C++
Задача С клавиатуры вводится координаты вершин треугольника и координаты точки с .Определить лежит ли точка в треугольнике.И если можно...

Точка с координатами - C++
Ребята такое дело,я только начала изучать C++,а препод уже назадавал очень много и я не знаю как это делать.Примеры однотипные.Я вам напишу...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
13.05.2012, 19:55     Точка в Многоугольнике! #4
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
using namespace std;
struct Point{
int x;
int y;
 
};
void main()
{
Point O,line;
Point* mass = new Point[6] ;
 
O.x=5;
O.y=3;
mass[0].x=mass[0].y=1;
mass[1].x=6;
mass[1].y=3;
mass[2].x=7;
mass[2].y=6;
mass[3].x=4;
mass[3].y=8;
mass[4].x=2;
mass[4].y=8;
mass[5].x=1;
mass[5].y=5;
 
line.y=3;
line.x=0;
 
int k=0,b=0;
int g,a, TX,TY, count,U;
//
// Y(X) = k * X + b
//Y(X1) = Y1
//Y(X2) = Y2
k = 0;
b = O.y;
 
for(int i=0;i<6;i++)
{
 
 g = (mass[i+1].y-mass[i].y)/(mass[i+1].x-mass[i].x);
 a=(mass[i].y-g*mass[i].x);
 if (k!=g) TX = (a - b) / (k - g);else TX=99999; 
 if (k!=g) TY = k * TX + b;else TY=99999;
 if(TY!=0&&TX!=0)
     count++;
 
 
 if(count%2==0)
     U=1;
 else 
     U=0;
 
 
 
}
 
cout<<U;
}



Я избавился там от деления на 0
Yandex
Объявления
13.05.2012, 19:55     Точка в Многоугольнике!
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru