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

Turbo Pascal

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 5.00
MonT
1 / 1 / 0
Регистрация: 14.09.2010
Сообщений: 26
#1

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

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

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

Принадлежность точки к треугольнику - Turbo Pascal
помогите подредактировать программу для определения принадлежности точки (x,y) заданной фигуре. предполагается что a>0 и b>0. ...

Принадлежность точки области - Turbo Pascal
Для данных областей составить программу, которая печатает true, если точка с координатами (х, у) принадлежит закрашенной области, и false —...

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

Принадлежность точки фигуре - Turbo Pascal
Ввести с клавиатуры координаты точки (переменные x и y). Проверить принадлежность этой точки заштрихованной области.

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

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

1
Puporev
Модератор
53999 / 41632 / 14717
Регистрация: 18.05.2008
Сообщений: 97,854
07.10.2011, 10:56 #2
Алгоритм определения принадлежности точки многоугольнику

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

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
Привет! Вот еще темы с ответами:

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

Помогите проверить точки на принадлежность. - Turbo Pascal
Необходимо определить принадлежность числа к отрезку АВ

Определить принадлежность точки области - Turbo Pascal
Помогите сделать.

Определить принадлежность точки области - Turbo Pascal
Для данных областей составить линейную программу,которая печатает true,если точка с координатами (x,y) принадлежит закрашенной области,и...


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

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

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