Форум программистов, компьютерный форум, киберфорум
Наши страницы
Turbo Pascal
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.58/19: Рейтинг темы: голосов - 19, средняя оценка - 4.58
MonT
1 / 1 / 0
Регистрация: 14.09.2010
Сообщений: 26
1

Принадлежность точки многоугольнику

06.10.2011, 18:19. Просмотров 3677. Ответов 1
Метки нет (Все метки)

Многоугольник на плоскости задается координатами своих N вершин в порядке обхода их по контуру по часовой стрелке (контур самопересечений не имеет). Для заданной точки Z(x,y) определить, принадлежит ли она стороне многоугольника или лежит внутри или вне его.Нарисовать многоугольник и показать заданную точку на рисунке
1
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.10.2011, 18:19
Ответы с готовыми решениями:

Принадлежность точки фигуре
Выручите пожалуйста,такая задача (Круг за вычетом треугольника) центр круга в...

Принадлежность точки к треугольнику
помогите подредактировать программу для определения принадлежности точки (x,y)...

Принадлежность точки фигуре
Ввести с клавиатуры координаты точки (переменные x и y). Проверить...

Принадлежность точки множеству.
1. На плоскости даны 2 точки А(x;y), B(x;y). Составьте программу, определяющую,...

Принадлежность точки области
Для данных областей составить программу, которая печатает true, если точка с...

1
Puporev
Модератор
55479 / 42580 / 29429
Регистрация: 18.05.2008
Сообщений: 100,730
07.10.2011, 10:56 2
Лучший ответ Сообщение было отмечено MonT как решение

Решение

Алгоритм определения принадлежности точки многоугольнику

Все отрезки кроме горизонтальных проверяются на пересечение с горизонтальным лучом,
выходящим из проверяемой точки.
При попадании луча в вершину пересечение засчитывается только с теми отрезками,
выходящими из вершины, для которых она является верхней.
Точка лежит внутри многоугольника, если кол-во точек пересечения нечетно.

Pascal
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
uses crt,graph;
const nmax=20;
type mas=array[1..nmax+1] of Pointtype;{+1 для построения полигона}
function Max( a,b:integer):integer;
begin
 if a>b then Max:=a else Max:=b;
end;
function Min(a,b:integer):integer;
begin
 if a<b then Min:=a else Min:=b;
end;
{определение точки в многоугольнике}
function PointInPoly (a:Pointtype;p:mas;n:integer):boolean;
var count,i,j:integer;
    t:real;
Begin
t:=0;
count:=0;
for i:=1 to n do
 begin
  j:=(i+1) mod (n+1);{индекс второй точки стороны}
  {не проверяем}
  if p[i].y=p[j].y then continue;{горизонтальная линия}
  if (p[i].y>a.y) and (p[j].y>a.y) then continue;{оба конца стороны выше точки}
  if (p[i].y<a.y) and (p[j].y<a.y) then Continue;{оба конца стороны ниже точки}
  if Max(p[i].y, p[j].y)=a.y then
   inc(count){если верхняя  вершина на 1 горизонтали с точкойб считаем пересечение}
  else If Min(p[i].y,p[j].y)=a.y then
   continue{если нижняя нет}
  else{все остальные случаи}
   begin
    t:=(a.y-p[i].y)/(p[j].y-p[i].y);{коэффициент пропорциональности
                                     деления стороны горизонтальным лучем из т.А}
    if ((t>0)and(t<1))and ((p[i].x+t*(p[j].x-p[i].x))>=a.x) then{условие пересечения правым лучем}
    inc(count);{считаем пересечения}
   end;
  end;
 PointInPoly:=count mod 2=1;{нечетное=true}
end;
var t:pointtype; { проверяемая точка }
    p:mas; { массив вершин многоугольника }
    n,i,j:integer;{размер и счетчики циклов}
    xmx,xmn,ymx,ymn,xc,yc,m:integer;{для построения полигона}
begin
clrscr;
{ввод данных }
repeat
write('Kolichestvo tochek ot 3 do 20 n=');
readln(n);
until n in [3..20];
writeln('Vvedite koordinaty protiv chasovoj strelki:');
for i:=1 to n do
 begin
  write('X[',i,']: '); readln(p[i].x);
  write('Y[',i,']: '); readLn(p[i].y);
 end;
writeln('Vvedite koordinaty tochki:');
write('X= ');
readln(t.x);
write('Y= ');
readln(t.y);
if PointInPoly(t,p,n) then write('Tochka v mnogougolnike')
else writeln('Tochka ne v mnogougolnike');
writeln;
write('Press Enter');
readln;
{переход в графику}
i:=0;
initgraph(i,j,'');
{найдем макс и мин по Х и У}
xmx:=t.x;xmn:=t.x;
ymx:=t.x;ymn:=t.x;
for i:=1 to n do
 begin
  if p[i].x>xmx then xmx:=p[i].x;
  if p[i].x<xmn then xmn:=p[i].x;
  if p[i].y>ymx then ymx:=p[i].y;
  if p[i].y<ymn then ymn:=p[i].y;
 end;
{вычислим масштаб для экрана}
if xmx-xmn>ymx-ymn then m:=round((getmaxY-60)/(xmx-xmn))
else m:=round((getmaxY-60)/(ymx-ymn));
{вычислим положение начала координат на экране}
if xmn>=0 then xc:=30
else if xmx<=0 then xc:=getmaxX-30
else if xmn*xmx<0 then xc:=30+round(-xmn*(getmaxX-60)/(xmx-xmn));
if ymn>=0 then yc:=getmaxY-30
else if ymx<=0 then yc:=30
else if ymn*ymx<0 then yc:=30+round(ymx*(getmaxY-60)/(ymx-ymn));
p[n+1]:=p[1];{замкнем полигон}
moveto(xc+p[1].x*m,yc-p[1].y*m);
for i:=1 to n+1 do
 begin
  setlinestyle(0,0,1);
  setcolor(9);
  lineto(xc+p[i].x*m,yc-p[i].y*m);{полигон}
  setlinestyle(0,0,3);
  setcolor(12);
  circle(xc+p[i].x*m,yc-p[i].y*m,1);{вершины}
 end;
setlinestyle(0,0,3);
setcolor(10);
circle(xc+t.x*m,yc-t.y*m,1);{заданная точка}
readln
end.
Добавлено через 58 минут
Упс... Это при вводе против часовой стрелки...

Добавлено через 24 минуты
Чтобы по часовой нужно только поменять знак в строке 35
<=a.x

Добавлено через 24 минуты
Ну, совсем плохо читал, там еще и
Цитата Сообщение от MonT Посмотреть сообщение
принадлежит ли она стороне
Вот, полностью поправил.
Pascal
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
uses crt,graph;
const nmax=20;
type mas=array[1..nmax+1] of Pointtype;{+1 для построения полигона}
function Max( a,b:integer):integer;
begin
 if a>b then Max:=a else Max:=b;
end;
function Min(a,b:integer):integer;
begin
 if a<b then Min:=a else Min:=b;
end;
function PointInPoly (a:Pointtype;p:mas;n:integer):integer;
var count,i,j:integer;
    t:real;
    f:boolean;
Begin
t:=0;
count:=0;
f:=false;
for i:=1 to n do
 begin
  j:=(i+1) mod (n+1);{индекс второй точки стороны}
  {не проверяем}
  if p[i].y=p[j].y then continue;{горизонтальная линия}
  if (p[i].y>a.y) and (p[j].y>a.y) then continue;{оба конца стороны выше точки}
  if (p[i].y<a.y) and (p[j].y<a.y) then Continue;{оба конца стороны ниже точки}
  if Max(p[i].y, p[j].y)=a.y then
   begin
    inc(count);{если верхняя  вершина на 1 горизонтали с точкойб считаем пересечение}
    f:=true{на стороне}
   end
  else If Min(p[i].y,p[j].y)=a.y then
   continue{если нижняя нет}
  else{все остальные случаи}
   begin
    t:=(a.y-p[i].y)/(p[j].y-p[i].y);{коэффициент пропорциональности
                                     деления стороны горизонтальным лучем из т.А}
    if ((t>0)and(t<1))and ((p[i].x+t*(p[j].x-p[i].x))<=a.x) then
    {условие пересечения левым лучем, правым >=a.x}
    inc(count);{считаем пересечения}
    if abs((p[i].x+t*(p[j].x-p[i].x))-a.x)<0.01 then f:=true;
    {если с точностью 0.01 совпадает с точкой, она на стороне}
   end;
  end;
 if count mod 2=0 then PointInPoly:=-1{четное не в полигоне}
 else
  begin
   if f then PointInPoly:=0
   else PointInPoly:=1
  end
end;
var t:pointtype; { проверяемая точка }
    p:mas; { массив вершин многоугольника }
    n,i,j:integer;{размер и счетчики циклов}
    xmx,xmn,ymx,ymn,xc,yc,m:integer;{для построения полигона}
begin
clrscr;
{ввод данных }
repeat
write('Kolichestvo tochek ot 3 do 20 n=');
readln(n);
until n in [3..20];
writeln('Vvedite koordinaty protiv chasovoj strelki:');
for i:=1 to n do
 begin
  write('X[',i,']: '); readln(p[i].x);
  write('Y[',i,']: '); readLn(p[i].y);
 end;
writeln('Vvedite koordinaty tochki:');
write('X= ');
readln(t.x);
write('Y= ');
readln(t.y);
if PointInPoly(t,p,n)=1 then write('Tochka v mnogougolnike')
else if PointInPoly(t,p,n)=0 then write('Tochka na storone')
else writeln('Tochka ne v mnogougolnike');
writeln;
write('Press Enter');
readln;
i:=0;
initgraph(i,j,'');
xmx:=t.x;xmn:=t.x;
ymx:=t.x;ymn:=t.x;
for i:=1 to n do
 begin
  if p[i].x>xmx then xmx:=p[i].x;
  if p[i].x<xmn then xmn:=p[i].x;
  if p[i].y>ymx then ymx:=p[i].y;
  if p[i].y<ymn then ymn:=p[i].y;
 end;
if xmx-xmn>ymx-ymn then m:=round((getmaxY-60)/(xmx-xmn))
else m:=round((getmaxY-60)/(ymx-ymn));
if xmn>=0 then xc:=30
else if xmx<=0 then xc:=getmaxX-30
else if xmn*xmx<0 then xc:=30+round(-xmn*(getmaxX-60)/(xmx-xmn));
if ymn>=0 then yc:=getmaxY-30
else if ymx<=0 then yc:=30
else if ymn*ymx<0 then yc:=30+round(ymx*(getmaxY-60)/(ymx-ymn));
p[n+1]:=p[1];{замкнем полигон}
moveto(xc+p[1].x*m,yc-p[1].y*m);
for i:=1 to n+1 do
 begin
  setlinestyle(0,0,1);
  setcolor(9);
  lineto(xc+p[i].x*m,yc-p[i].y*m);
  setlinestyle(0,0,3);
  setcolor(12);
  circle(xc+p[i].x*m,yc-p[i].y*m,1);
 end;
setlinestyle(0,0,3);
setcolor(10);
circle(xc+t.x*m,yc-t.y*m,1);
readln
end.
2
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.10.2011, 10:56

Принадлежность точки заштрихованной области
Написать программу, которая вводит с клавиатуры координаты точки на плоскости...

Принадлежность точки к заданной фигуре
Не доходит алгоритм решения.

Найти принадлежность точки области
Задачка: Найти принадлежность точки М ( на картинке) И сам код: тоже на...


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

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

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