Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/13: Рейтинг темы: голосов - 13, средняя оценка - 5.00
Incolour
1

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

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

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


Общее решение задачи:
Для решения этой задачи проведем прямую из точки а в некоторую бесконечно удаленную от многоугольника точку. На всем своем протяжении эта прямая может n раз пересечь границу нашего многоугольника. Если прямая не пересекает ни одного ребра заданного многоугольника, то n=0. Если следовать по прямой из бесконечно удаленной точки к точке a, то первое пересечение приведет нас внутрь многоугольника, при втором пересечением мы выйдем за границу этого многоугольника, при третьем — снова окажемся внутри и т.д. Из этих наблюдений можно заключить, что каждое нечетное пересечение означает попадание внутрь нашего многоугольника, а каждое четное — выход из него. Таким образом, если при движении по прямой только что описанным образом, мы попадаем в точку a с нечетным числом пересечений границы многоугольника, то точка a находится внутри него, если же число пересечений четно, то точка лежит вне многоугольника.

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.01.2010, 16:30
Ответы с готовыми решениями:

Точки в многоугольнике
В общем не давно была олимпиада. и меня меня мучает решение одной задачи: Многоугольник...

Интерполяция в многоугольнике - найти значение неизвестной точки
Никак не могу придумать алгоритм. Нужны подсказки. Итак, условие: есть несколько точек. Их...

Оптимизировать код, проверки нахождения точки в многоугольнике
Можно ли оптимизировать этот код, т. е. выполнить проверку (заданную в коде) более простым...

Точка в Многоугольнике!
Задача "Точка в многоугольнике". Условие. Многоугольник (выпуклый) задан координатами...

1
135 / 69 / 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
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2010, 22:49

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

Найти в многоугольнике длины диагоналей
Найти в многоугольнике длины диагоналей, вывести на экран размер и вершины самой маленькой и самой...

Найти синус угла в многоугольнике
Я хочу найти синус каждого угла в многоугольнике с помощью векторного произведения, вот части кода:...

Посчитать кол-во прямых углов в многоугольнике
Дан многоугольник. Требуется найти количество прямых углов в этом многоугольнике. В первой строке...


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

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

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