мозго... занималка :)

вот такой у нас murph шутник и затейник

Алгоритм с лучем проще в описании чем твой Drunkard

Если луч выпущеный из точки пересекает не четное количество сторон, то точка внутри.

в одну строку )

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

твой, завалится на неправильных и на дырках.

m ты где вычитал свой этот бред! ;D
Ты раскинь мозгой и поймешь, какая там у тебя одна строчка.
Итак:
1) что ты будешь делать со своим лучом если он воткнется прямиком в вершину? Тогда точка может быть внутри, а если он коснулся вершины и точка снаружи?
2)для n-угольника с вершиной вовнутрь сушествует вероятность, что луч пройдет прямо по стороне и число пересечений луча и стороны будет равно бесконечности.

Так, что Шура, не пудрите мне мозги. Уши от мертвого осла получишь у Пушкина. ;D
У моего алгоритма таких проблем нет.

а так?

<br>function IsPointIntoPolygon(x,y:real;X,Y:array[0..N] of real):Boolean<br>begin<br>  i:=0;<br>  Result:=False;<br>  X[0]:=X[n];<br>  Y[0]:=Y[n];<br>  repeat<br>    if not((y>Y[i])xor(y<=Y[i+1]))<br>    then<br>    begin<br>      if (x-X[i]<(y-Y[i])*(X[i+1]-X[i])/(Y[i+1]-Y[i]))<br>      then<br>      begin<br>        Result:=not(Result)<br>      end;<br>    end;<br>    i:=i+1<br>  until not(i<=n-1);<br>end;<br>

Сообщение отредактировано: murph - 28.03.02, 17:03

Цитата Drunkard, 26.03.02, 02:56:53

Вот murph уже решение предложил.
И я тоже на пальцах придумал. Ну ладно уж выложу его тоже, раз уж обдумал и записал.
Вот тебе алгоритм определения находится ли точка в заданном тр-ке. С таким решением сможет справиться не то чтобы 10-классник, а 6-ти классник. Нау хау продадим тупым буржуям  

Алгоритм, конечно, классный, но долгий , а имеется другой школьный способ из линейной алгебры. Решаем систему уравнений с тремя неизвестными (a, b, c)
Tx = a*x1 + b*x2 + c*x3
Ty = a*y1 + b*y2 + c*y3
1 = a + b + c

Если a, b, c >= 0, то точка лежит в треугольнике (это расширяется на все выпуклые полигоны)
(я понимаю, что тема стара, и про неё уже забыли, но увидев такое, не мог не отозваться )

Это к тебе в Польшу только сегодня тема дошла? Ну и далече же ты! ;D

Да, скоро начнут доходить посты с апреля сего года. Жду не дождусь .

Может комп проапгрейдить? А лучше монитор, авось побыстрее доходить станут? :

Заботлывый ты ;D. Проапгрейдь ;D