Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
Incolour
#1

Локализация точки в произвольном многоугольнике - C++

12.01.2010, 16:30. Просмотров 1183. Ответов 1
Метки нет (Все метки)

Помогите пожалуйста..Надо в близжайшие 5-6 часов.....BorlandC
309-153-594 ася
oksy_@list.ru
Множество точек определяет многоугольник. Для данной точки определить где она расположена относительно этого многоугольника: внутри, снаружи.
(предполагается, что в файле записано несколько пар чисел, которые можно рассматривать как координаты точек на плоскости или как координаты концов отрезков.)


Общее решение задачи:
Для решения этой задачи проведем прямую из точки а в некоторую бесконечно удаленную от многоугольника точку. На всем своем протяжении эта прямая может n раз пересечь границу нашего многоугольника. Если прямая не пересекает ни одного ребра заданного многоугольника, то n=0. Если следовать по прямой из бесконечно удаленной точки к точке a, то первое пересечение приведет нас внутрь многоугольника, при втором пересечением мы выйдем за границу этого многоугольника, при третьем — снова окажемся внутри и т.д. Из этих наблюдений можно заключить, что каждое нечетное пересечение означает попадание внутрь нашего многоугольника, а каждое четное — выход из него. Таким образом, если при движении по прямой только что описанным образом, мы попадаем в точку a с нечетным числом пересечений границы многоугольника, то точка a находится внутри него, если же число пересечений четно, то точка лежит вне многоугольника.
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.01.2010, 16:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Локализация точки в произвольном многоугольнике (C++):

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

Точка в Многоугольнике! - C++
Задача "Точка в многоугольнике". Условие. Многоугольник (выпуклый) задан координатами своих вершин (xi;yi), 1 i N в...

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

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

Табуляция и локализация С++ - C++
сделать программу локализации кореней которое задано уравнением путем табуляции функции на отрезке -20 и 20 с шагом h=0.2 что-то не так...

Локализация консоли - C++
Всем привет. Дело такое. Есть программа, которая при определенных условиях должна заменять символ в строке на 219 символ ASCII...

1
Radjuk
134 / 68 / 12
Регистрация: 10.10.2009
Сообщений: 187
12.01.2010, 22:49 #2
надо брать координаты точки и смотреть или значение X и Y больше или меньше значений A(X) и A(Y)
и так для всех точек

Добавлено через 5 часов 33 минуты
вот кому надо будет еще посмотрите
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
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.xls","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";  
 
  getch();
}
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.01.2010, 22:49
Привет! Вот еще темы с ответами:

Русская локализация - C++
На просторах вашего форму нашел, следующий код программы//Подключение библиотек// #include &quot;stdafx.h&quot; #include &lt;locale&gt; #include...

Как работает локализация в C++ - C++
Здравствуйте, появился вопросы. В заголовочном файле &lt;locale&gt; определены функции isalpha, ... ,tolower, toupper; которые в зависимости от...

Локализация для Unicode - C++
Всем привет! Подскажите как подключить локализацию при работе с Unicode. Для ANSI, насколько я знаю (VS2010) ...

Табуляция и локализация корней - C++
сделать программу локализации кореней которое задано уравнением путем табуляции функции на отрезке -20 и 20 с шагом h=0.2 что-то не так...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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