Геометрия

← →
RealRascal © (2004-05-05 20:20) [0]

Имеется сетка, треугольная, на плоскости. Как определить, какому треугольнику принадлежит точка с координатами х и у?
Вариант . Перебрать все треугольники. Проверить на принадлежность этой точки каждому треугольнику.
Сама задача определения принадлежности требует много вычислений. Поэтому этот вариант не пригоден. Есть мыслишки?

← →
VMcL © (2004-05-05 20:27) [1]

>>RealRascal © (05.05.04 20:20)

Координаты вершин треугольников вычисляемы? Если да, то нет проблемы.

← →
RealRascal © (2004-05-05 20:36) [2]

> Координаты вершин треугольников вычисляемы? Если да, то
> нет проблемы.

они известны,
тругольники разные все по размеру

← →
SergP © (2004-05-05 20:40) [3]

>Имеется сетка, треугольная, на плоскости

Опиши сетку. каким образом она задана...

← →
Jack128 © (2004-05-05 20:42) [4]

> Сама задача определения принадлежности требует много вычислений
смотря как проверять. Например для начала можно проверить чтобы min(X1, X2, X3) <= X <= max(X1, X2, X3) and min(Y1, Y2, Y3) <= Y <= max(Y1, Y2, Y3) - это отсеет подавляющее большенство треугольников, а уж оставшиеся можно более точно проверить..

← →
RealRascal © (2004-05-05 20:50) [5]

список(TLIST) из элементов. каждый элемент(WORD) содержит номер и три узла. Каждый узел содержит 2 floata - x и y. Требуется определить номер элемента.

← →
Algol (2004-05-05 21:31) [6]

> RealRascal © (05.05.04 20:50) [5]

Это из области многомерной интерполяции?

← →
SergP © (2004-05-05 22:01) [7]

А перебор почему не устраивает?

Я вот подумал как определить принадлежность точки треугольнику...

Допустим X,Y - координаты точки

X1,Y1, X2,Y2, X3,Y3 координаты вершин.

проверяем три неравенства:

(X1-X)*(X2-X) + (Y1-Y)*(Y2-Y) >=0
(X2-X)*(X3-X) + (Y2-Y)*(Y3-Y) >=0
(X3-X)*(X1-X) + (Y3-Y)*(Y1-Y) >=0

Если хотябы 2 из них верные, то точка принадлежит треугольнику...

← →
SergP © (2004-05-05 22:03) [8]

Мля... ошибся....

Вот так правильно:
(X1-X)*(X2-X) + (Y1-Y)*(Y2-Y) =< 0
(X2-X)*(X3-X) + (Y2-Y)*(Y3-Y) =< 0
(X3-X)*(X1-X) + (Y3-Y)*(Y1-Y) =< 0

Если хотябы 2 из них верные, то точка принадлежит треугольнику...

← →
Algol (2004-05-05 22:18) [9]

> SergP © (05.05.04 22:03) [8]

Автор же сказал, что

> задача определения принадлежности требует много вычислений.
> Поэтому этот вариант не пригоден.

← →
RealRascal © (2004-05-05 22:19) [10]

> Algol (05.05.04 21:31) [6]

Это все тот же МетодКонечныхЭлементов. Требуестя определить номер элемента, чтобы аппроксимировать перемещения внутри него

> SergP © (05.05.04 22:03) [8]

Проверим...
А из каких соображений это получено? Из уравнений прямых?

← →
RealRascal © (2004-05-05 22:22) [11]

> Algol (05.05.04 22:18) [9]

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

← →
SergP © (2004-05-05 22:32) [12]

>> SergP © (05.05.04 22:03) [8]

>Проверим...
>А из каких соображений это получено? Из уравнений прямых?

ИМХО я снова ошибся.... :-(((
Кое чего не учел....

← →
Algol (2004-05-05 22:32) [13]

> да, но похоже от этого никуда не деться...

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

← →
Algol (2004-05-05 22:34) [14]

Да и если все равно нужно искать ближайшую точку, то вероятно нужно сначала ее найти, а потом приверить только те треугольники, вершиной которых эта точка является ))

← →
SergP © (2004-05-05 22:40) [15]

>Да и если все равно нужно искать ближайшую точку, то вероятно нужно
>сначала ее найти, а потом приверить только те треугольники, вершиной
>которых эта точка является ))

Ну слава богу не я один...Вы тоже ошиблись... :-)))

← →
Algol (2004-05-05 22:41) [16]

Алгоритм определения принадлежности точки треугольнику описан и доказан здесь http://www.kcn.ru/tat_ru/universitet/infres/kazancev/compgraf.zip

← →
RealRascal © (2004-05-05 23:18) [17]

> Algol (05.05.04 22:41) [16]

Спасибо за ссылку, там еще много полезного кроме этого

← →
RealRascal © (2004-05-09 09:11) [18]

Если тема еще кому-то интересна, вот как я сделал.
Приходится все равно все элементы проверять... не знаю как сделать по другому...
Вот функция возвращает номер элемента

Function TFEMPro.ENoByXY(Const x, y: double): word; Var i : integer; Begin result:=0; For i:=1 To Elems.Count-1 Do Begin If Elems.items[i].HaveXY(x, y) Then Begin result:=i; break; End; End; End;

А эта функция проверяет на принадлежность точки элементу.
Сначала параллельным переносом координаты преобразуются так, чтобы искомая точка находилась в начале координат.
Затем проверяется, имеют ли вершины координаты одинаковых знаков. Если все вершины имеют одинаковый знак, то, безусловно, точка не принадлежит треугольнику. Выход. Если же нет, то проверяется более ресурсоемкое условие - равенство суммы площадей трех маленьких треугольников(проверяемая точка одна из вершин их вершин, две другие - большого тр-ка) площади большого.

Function TElem.HaveXY(Const x, y: double): boolean; Var x1, x2, x3, y1, y2, y3 : double; sx1, sx2, sx3, sy1, sy2, sy3 : TValueSign; Begin y1:=nodes[1].y-y; y2:=nodes[2].y-y; y3:=nodes[3].y-y; x1:=nodes[1].x-x; x2:=nodes[2].x-x; x3:=nodes[3].x-x; sx1:=sign(x1); sx2:=sign(x2); sx3:=sign(x3); sy1:=sign(y1); sy2:=sign(y2); sy3:=sign(y3); If ((sx1=sx2)And(sx2=sx3))Or((sy1=sy2)And(sy2=sy3)) Then Begin result:=false; exit; End Else Begin If SameValue( (GetAreaXY(0,0 , x1, y1, x3, y3))+ (GetAreaXY(0,0 , x2, y2, x3, y3))+ (GetAreaXY(0,0 , x1, y1, x2, y2)),(GetArea),0.001) Then result:=true Else result:=False; End; End;

Пожалуйста, если есть какие-нибудь предложения по оптимизации, выскажитесь. Не оставлю без внимания ни одного сообщения.

← →
Algol (2004-05-09 09:35) [19]

For i:=0 To Elems.Count-1 Do

← →
RealRascal © (2004-05-09 09:46) [20]

> Algol (09.05.04 09:35) [19]
> For i:=0 To Elems.Count-1 Do

Нет, это не ошибка. Нулевой элемент = nil. Введен для того, чтобы нумер узла в списке и совпадал с его порядковым номером в сетке.

← →
SergP © (2004-05-09 10:05) [21]

>Пожалуйста, если есть какие-нибудь предложения по оптимизации,
>выскажитесь. Не оставлю без внимания ни одного сообщения.

насчет вычисления площадей не знаю насколько это хорошо...

Я первоначально думал так:

Сначала как у тебя паралельным переносом переносим все так чтобы точка оказалась в (0,0)

Затем смотрим на 3 вектора 0A,0B и 0C (координаты векторов равны кординатам соответствующих вершин треугоьника, который получился в результате переноса.
И теперь чтобы точка была в треугольнике, необходимо и достаточно чтобы сумма углов между векторами была 360 градусов. Т.е. 2*pi. Если же сумма будет меньше, то точка за пределами...
Но вот как далее это посчитать я пока не знаю.
соs угла между двумя векторами a и b вычисляется так

cos(y)= a*b/(|a|*|b|) (где a*b - скалярное произведение векторов)

В SergP © (05.05.04 22:03) я ошибся полагая что для этого хотябы 2 из 3 углов должны быть более 90 градусов...
Но может кто-то еще что-то сможет придумать....

← →
RealRascal © (2004-05-09 10:16) [22]

> SergP © (09.05.04 10:05) [21]

вычисление займет, имхо, куда больше времени, чем вычисление четырех площадей.
Вот так вычисляется площадь
Function TElem.GetAreaXY(x1, y1, x2, y2, x3, y3: double): double; Begin Result:=abs(0.5*(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1)); End;
А как вычисляется косинус я не знаю. Вроде с пом. ряда...

← →
Algol (2004-05-09 12:26) [23]

Для оптимизации можно предложить например следующее:
Для каждого треугольника храним прямоугольник, содержаищий его.
Координаты вычисляются очень просто - через минимумы и максимумы координат вершин. Вычисляется это один раз для всех треугольников. Далее в TFEMPro.ENoByXY проверяем вхождение точки в соотв прямоугольник (это тоже просто). И только если точка входит в него, делаем проверку на вхождение в треугольник. При этом алгоритм проверки в HaveXY уже не столь существеннен, поскольку эта функция будет вызываться очень редко, и ее временем можно пренебречь.

> Algol (09.05.04 12:26) [23]

По сути дела, так и происходит, только уже в самой HAVEXY.
Алгоритм ее устроен так, что более сложное условие(с площадями) проверяется очень редко.
Точка становиться началом координат, и проверяются знаки. По ресурсоемкости, это, имхо, даже быстрее, чем строить прямоугольники и хранить их где-то.

> Result:=abs(0.5*(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1));

Что-то подозрительно просто.... Я сомневаюсь в правильности. попробую проверить...

Проверил на конкретном примере:

x1=0; y1=0
x2=1; y2=3
x3=3; y3=1

Реально площадь треугольника равна 5,667
По твоей Result:=abs(0.5*(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1));
получается 4

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

>Result:=abs(0.5*(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1));

Если ты хочешь проверить или сумма плошадей "маленьких" треугольников равна прощади "большого" треугольника, то ИМХО можно упростить вычисления

Тебе нужно проверить или:

abs(0.5*(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1))=abs(0.5*(x2*y3-x3*y2+x3*0-0*y3+0*y2-x2*0))+abs(0.5*(0*y3-x3*0+x3*y1-x1*y3 +x1*0-0*y1))+abs(0.5*(x2*0-0*y2+0*y1-0*y3+x1*y2-x2*y1)),
т.е:
abs(x2*y3-x3*y2+x3*y1-x1*y3+x1*y2-x2*y1)=abs(x2*y3-x3*y2)+abs(x3*y1-x1*y3)+abs(x1*y2-x2*y1)

поэтому для проверки ИМХО достаточно вычислить значения:
x2*y3-x3*y2
x3*y1-x1*y3
x1*y2-x2*y1

И проверить или они имеют одинаковый знак, т.е. или все они >=0 или все =<0

Вобщем щас я вообще не уверен в том что написал, так как с бодуна и мне хреново. но думаю что можно сделать где-то так...

проверим...

> x2*y3-x3*y2
> x3*y1-x1*y3
> x1*y2-x2*y1
>
> И проверить или они имеют одинаковый знак, т.е. или все
> они >=0 или все =<0

согласен.

>RealRascal © (05.05.04 20:20) :
Зачем же все?

Бросаете иголочку. Случайно.
Она (иголочка) и вершин и катетов так или иначе
касается. Дальше вспоминаем о Гауссе.
О случайности:))
Потом заходим на любой поисковик и набираем
магические слова "интегральная геометрия" "Новиков"
"парадокс Бертрана" ну, если хотите ещё и "Коши".

> [30] SergP © (10.05.04 03:18)

Спасибо, все заработало еще быстрее.

Вроде тут больше нечего оптимизировать.
Всем спасибо.

Геометрия Найти похожие ветки