Ахтунк... Задачка. Геометрия. 3 класс.
W
WSV
элегантно
но неправильно.
tvertex как объявлен?
[Сообщение изменено пользователем 25.07.2007 13:40]
C
_Cью_
ясна
просто лень вникать в текст кода )))
тока зачем проверять пересечения сторон? :-)
d
demiurg_ii
не сказано в каком порядке соеденяются точки
Тогда лично мы (участники етих programming contest) с чистой совестью рисуем выпуклую оболочку, и не парим мозг товарищам по ACM-овской команде :-)
[Сообщение изменено пользователем 25.07.2007 13:41]
какие четвертях ещё?
ну тут в школу
система координат
2|1
----
3|4
[Сообщение изменено пользователем 25.07.2007 13:41]
C
~CyberFox~
епрст... :-) бугага...
проводим произвольный луч из точки. Если имеем ноль, или четное число пересечения c реберами многоугольника - точка вне многоугольника... если число пересечений с ребрами нечетное - внутри.
математигы :-)
проводим произвольный луч из точки. Если имеем ноль, или четное число пересечения c реберами многоугольника - точка вне многоугольника... если число пересечений с ребрами нечетное - внутри.
математигы :-)
tvertex как объявлен?
TVertex = class
X,Y: Integer;
constructor Create(Ax,Ay: Integer);
end;
constructor TVertex.Create(Ax,Ay: Integer);
begin
X:=Ax; Y:=Ay;
end;
проводим произвольный луч из точки.
)))) вариант :-) но ет опять к дядям кодерам и формулам :-)
моё решение не требует формул :-) и ваще нехрена не требует)) как раз 3ий класс))
проводим произвольный луч из точки. Если имеем ноль, или четное число пересечения c реберами многоугольника - точка вне многоугольника... если число пересечений с ребрами нечетное - внутри.
Уже писал об этом. Но только ты забыл о перечении луча с вершиной :-d
ВТОРОЙ СПОСОБ
Называется "Сканирующая линия" (или scanline)
1. Проводится в любой системе координат горизонтальная линия через исходную точку.
2. Считается количество пересечений слева от этой точки с гранями многоугольника. Пересечение с вершиной "снаружи" считается за два пересечения
3. Если количество пересечений слева будет нечетное - то вершина внутри многоугольника
Называется "Сканирующая линия" (или scanline)
1. Проводится в любой системе координат горизонтальная линия через исходную точку.
2. Считается количество пересечений слева от этой точки с гранями многоугольника. Пересечение с вершиной "снаружи" считается за два пересечения
3. Если количество пересечений слева будет нечетное - то вершина внутри многоугольника
епрст... бугага...
проводим произвольный луч из точки. Если имеем ноль, или четное число пересечения c реберами многоугольника - точка вне многоугольника... если число пересечений с ребрами нечетное - внутри.
математигы
проводим произвольный луч из точки. Если имеем ноль, или четное число пересечения c реберами многоугольника - точка вне многоугольника... если число пересечений с ребрами нечетное - внутри.
математигы
а уравнение луча написать можешь чтобы можно было проверить пересечение с прямой на бумаге а не в компьютере?
Одной формулой тут нифига не решается, все равно нужен перебор отрезков и алгоритм.
моё решение не требует формул и ваще нехрена не требует)) как раз 3ий класс))
только оно неверное
только оно неверное
жду доказательств
опять ж напомню вам)) что нет в условиях как мы соединяем эти точки :-)
индукцией надо решать
весь западный научный мир на индукцию перешел, а мы что-же отстаем славяне :-(
весь западный научный мир на индукцию перешел, а мы что-же отстаем славяне :-(
W
WSV
жду доказательств
опять ж напомню вам)) что нет в условиях как мы соединяем эти точки
опять ж напомню вам)) что нет в условиях как мы соединяем эти точки
Ога. И соединяем ли вообще...
[Сообщение изменено пользователем 25.07.2007 13:59]
я какойто пост пропустил)) какая индукция)) какое програмирование
3ИЙ КЛАСС!!!!! :-) черепашки нинзя, кукла барби, покемоны
3ИЙ КЛАСС!!!!! :-) черепашки нинзя, кукла барби, покемоны
жду доказательств
опять ж напомню вам)) что нет в условиях как мы соединяем эти точки
опять ж напомню вам)) что нет в условиях как мы соединяем эти точки
<center><br><br><img src="http://www.monton.ru/misc/kontra.gif"><br><br></center>
хоть как соединяй эти точки, но по вашему точка не внутри фигуры
Одной формулой тут нифига не решается, все равно нужен перебор отрезков и алгоритм.
Решается! Вот:
Для определения точки внутри многоугольника есть пара функции в Win32 API:
PtInRegion(CreatePolygonRgn(многоугольник, число вершин, ALTERNATE), x, y)
:-d
[Сообщение изменено пользователем 25.07.2007 14:10]
для каждой стороны надо посчитать выражение
(Хк-Хн)*(Ум-Ун)-(Хм-Хн)*(Ук-Ун)
к - конец
н- начало
м - тестируемая точка.
Если все выражения одного знака, то внутри, иначе - снаружи.
(Хк-Хн)*(Ум-Ун)-(Хм-Хн)*(Ук-Ун)
к - конец
н- начало
м - тестируемая точка.
Если все выражения одного знака, то внутри, иначе - снаружи.
Ты забыл про то, что многоугольник может быть и не выпуклым. А на рисунке именно такой и есть. В этом случае твой алгоритм не работает. Для этого нужно разбивать многоугольник на выпуклые части.
для каждой стороны надо посчитать выражение
(Хк-Хн)*(Ум-Ун)-(Хм-Хн)*(Ук-Ун)
к - конец
н- начало
м - тестируемая точка.
Если все выражения одного знака, то внутри, иначе - снаружи.
(Хк-Хн)*(Ум-Ун)-(Хм-Хн)*(Ук-Ун)
к - конец
н- начало
м - тестируемая точка.
Если все выражения одного знака, то внутри, иначе - снаружи.
неверно
Если все выражения одного знака, то внутри, иначе - снаружи.
Если полигон будет невыпуклый, то не проканает :-)
Кстати, помню, решал как-то еще более простую задачу: проверить, лежит ли точка на отрезке. Тоже намучался будь здоров. Даже звонил своей училке математики - и та не смогла помочь. :-)
Решилось через уравнение прямой.
Ты забыл про то, что многоугольник может быть и не выпуклым. А на рисунке именно такой и есть. В этом случае твой алгоритм не работает. Для этого нужно разбивать многоугольник на выпуклые части.
даже для выпуклого неверно
Обсуждение этой темы закрыто модератором форума.