Ахтунк... Задачка. Геометрия. 3 класс.

Чо то я наверно ребенка в школу не отдам...

Только не простая. Формула любви тута...

ну ты порисуй примерчики пока, потом доложишь :-)

топологией. Для начала полагаем многоугольник а) замкнутой и б) ограниченной и в) односвязной фигурой.
Луч -- это на самом деле непрерывный путь из точки "бесконечность"(которая заведомо ВНЕ многоугольника) в точку, которая нас интересует. А граница многоугольника -- замкнутый контур. Так вот каждое первое пересечение контура на пути из одной точки в другую переводит нас из состояния ВНЕ контура в состояние ВНУТРИ контура. А каждое второе -- наоборот.

Уважаемый, ваш метод уже полчаса назад разрисован примерчиками. Метод хорош и аксиоматический. Респегт.

так как нет условия в каком порядке соединяются точки
то
красная точка центр координат
если в во всех 4х четвертях есть хотябы 1 точка то, наша красная точка находится в геометрической фигуре)

:-d Страх не справиться если ребенок подойдет вдруг с вопросом? :-)
:-) Просто-то как всё.

Дык я не претендую... :-) На самом, как показывает наша олимпиадная практика, лучший (всм, быстрее всех кодируется и меньше ошибок при сдаче работ возникает) -- метод, указанный Биореактором. Разумеется, если исходные данные более-менее задают последовательность вершин. :-)

Оооо... Бинго! Так то идеальный вариант решения, хрен подкопаешься. Возможно это и есть нужный ответ.
А мы тут формулы, множества и т.п.

какие четвертях ещё? :-)
вовсе не факт, что

а покажите мне ктонить ВПУКЛЫЙ треугольник! :-d

элегантно

---


[Сообщение изменено пользователем 25.07.2007 13:35]

можно составить систему неравенств, которая описывает данный нам многоугольник (а зная координаты вершин это сделать не сложно)
потом подставить в него координаты красной точки
удовлетворяет всем усовиям - ок, мы попали внутрь!
хоть одно не пошло - мы в пролете :-)

2Тузя

светлая голова

да, красиво
но не думаю что в 3 классе дети ваще знают что такое система координат, а две системы - они будут в шоке
я уж молчу про афинную систему... :-d

[Сообщение изменено пользователем 25.07.2007 13:35]

но не полно :-)

Если не находится, то условие


--------------------------------------------------------------------------------
Цитата:
От пользователя: Тузя

если в во всех 4х четвертях
--------------------------------------------------------------------------------

не выполняется.

Нашел в старых исходниках:
-----------------------------8<-------------------------------

function InContur_Up_Down(B: TList; P: TVertex; DirY: Integer):boolean;
{находится ли точка внутри/на контуре при направлении луча вверх (DirY < 0),
вниз (DirY > 0)}
var One,Two,On,Done:boolean; //,Lower
Point1,Point2,Point3: TVertex;
OutP:TVertex;
TempP:TVertex;
I,Start,Sect,Limit: Integer;
T:byte;
R:TRect;
begin
try
Result:=False;
GetMaxRect(B, R);
I:= 0;
Sect:= 0;
Limit:= B.Count-1;
if Limit<1 then Exit;
{если точка попадает в прямоугольник контура}
if (InLimits(R.Left, R.Right, P.X) = 0) and
(InLimits(R.Top, R.Bottom, P.Y) = 0) then
begin
while TVertex(B[I]).X = P.X do I:= NextP(I, Limit, False);
Point1:= TVertex.Create(0,0);// New(PCoor,Init(0, 0));
Point2:= TVertex.Create(0,0);//New(PCoor,Init(0, 0));
Point3:= TVertex.Create(P.X, DirY);//New(PCoor,Init(P.X, DirY));
OutP:= TVertex.Create(0,0);//New(PCoor,Init(0, 0));
Start:= I;
repeat
One:= TVertex(B[I]).X < P.X;
Two:= not One;
On:= False;
repeat
TempP:= TVertex(B[I]);
I:= NextP(I, Limit, True);
Done:= I = Start;
if TVertex(B[I]).X = P.X then
On:= True
else
One:= TVertex(B[I]).X < P.X;
until (One = Two) or On or Done;
if (One = Two) or On then
if On then
begin
if ((TVertex(B[I]).Y < P.Y) and (DirY < 0))
or ((TVertex(B[I]).Y > P.Y) and (DirY > 0)) then
begin
repeat
I:= NextP(I, Limit, True);
Done:= I = Start;
Two:= TVertex(B[I]).X = P.X;
until not Two;
Two:= TVertex(B[I]).X < P.X;
if Two <> One then Inc(Sect);
end;
end
else
if ((TempP.Y < P.Y) and (DirY < 0)) or ((TempP.Y > P.Y) and (DirY > 0))
or ((TVertex(B[I]).Y < P.Y) and (DirY < 0)) or ((TVertex(B[I]).Y > P.Y) and (DirY > 0)) then
begin
Point1.X:=TempP.X; Point1.Y:=TempP.Y;// Assign(TempP.X, TempP.Y);
Point2.X:=TVertex(B[I]).X;Point2.Y:=TVertex(B[I]).Y;
if LineIntersect(Point1, Point2, P, Point3, T, OutP) then
if ((OutP.Y < P.Y) and (DirY < 0))
or ((OutP.Y > P.Y) and (DirY > 0)) then Inc(Sect);
end;
until Done;
OutP.Free;
Point3.Free;
Point2.Free;
Point1.Free;
Result:= (Sect mod 2) = 1;
end
else
Result:= False;
finally
end;
end;

function InContur(X,Y: Integer; B: TList): boolean;
var P: TVertex;
begin
try
P:=TVertex.Create(X,Y);
Result:=InContur_Up_Down(B, P,-15000) or InContur_Up_Down(B, P, 15000);
P.Free;
except
Result:=False;
end;
end;

-----------------------------8<-------------------------------
Работает вполне нормально, но за алгоритм прошу не пинать, мало ли что у мну в исходниках валяется
:-d

Именно.... :-)

а можно блок-схему? :-)

вообще у меня есть идеальное решение - свести задачу к задаче с самолетом и мухами, а дальше методом индукции - самолет взлетит - значит точка в фигуре, не взлетит - значит вне фигуры

Дык, а чо там, проверяется пересечение сторон, да и все :-)

Знаю 2 способа

ПЕРВЫЙ

Всё правильно:
1. Разбиваем на выпуклые многоугольники, самое простое - на треугольники. Это делается так:
а) Находим выпуклую вершину (с острым углом) с самым минимальным углом
б) "отрезаем" от многоугольника треугольник с этой выбранной вершиной и двумя соседними
в) продолжаем рекурсивно, пока в остатке не останется треугольник
2. Для каждого из треугольников переориентируем его, чтобы вершины шли в направлении часовой стрелки.
3. Искомая точка находится внутри треугольника, если она находится справа от каждого из трех векторов, проходящих через вершины (расположенные по часовой) треугольника. Можно и не переориентировать треугольник - тогда эта точка должна быть с одной и той же стороны от трех векторов

ВТОРОЙ СПОСОБ
Называется "Сканирующая линия" (или scanline)
1. Проводится в любой системе координат горизонтальная линия через исходную точку.
2. Считается количество пересечений слева от этой точки с гранями многоугольника. Пересечение с вершиной "снаружи" считается за два пересечения
3. Если количество пересечений слева будет нечетное - то вершина внутри многоугольника

[Сообщение изменено пользователем 25.07.2007 13:48]

[Сообщение изменено пользователем 25.07.2007 17:57]

[Сообщение изменено пользователем 25.07.2007 13:35][/quote]






все ваши рисунки как фигура обходит центр координат распадаются, так как не сказано в каком порядке соеденяются точки