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

ЗАДАЧА
Имеется 3D тело (замкнутая поверхность), состоящее из полигонов (кусочков/треугольников) с координатами углов x1[i] y1[i] z1[i], x2[i] y2[i] z2[i], x3[i] y3[i] z3[i] ( где i - номер полигона). Необходимо определить, точка простарнстава с координатами x0 y0 z0 находится внутри тела (замкнутой поверхности) или вне его...

======
ОБЩАЯ ТЕОРИЯ (научное обоснование )

Предполагаю, что если провести от этой точки (назовём её P) луч (L) в любую сторону, то, если он будет иметь чётное число пересечений с многогранником М, то это значит, что точка Р лежит вне объекта М, в противном случае - она внутри него, т.е. принадлежит ему и имеет нечётное число пересечений. Луч из точки Р наиболее удобно пускать параллельно какой-либо координате, скажем y... Т.е. имеем луч L (x>x0, y=y0, z=z0). Однако, решать задачу пересечения луча и ограниченной треугольником плоскости - трудоёмко, стоит упростить до пересечения полуплоскости (П) и граней многогранника. Как я сказал, точка Р лежит внутри многогранника, если луч, исходящий из Р, пересекает нечётное число его граней. Прямая L пересекается с многогранником, если она имеет непустое пересечение с какой-либо из его граней. Проведём через луч L плоскость, этот луч делит её на 2 части, вот одна из них и есть полуплоскость П (x>x0, y>y0, z=z0). Есои полуплоскость П не проходит через вершины многогранника М, то прямая L не пересекает этот многогранник тогда и только тогда, когда для каждой грани М полуплоскость П пересекает чётное (0,2,4,6,...) число её рёбер... Так проще, т.к. оперируем одновременно в 3 раза меньшим числом координат, и алгоритм работает быстрее, нежели, если сравнивать луч и грань.

попробую изобразить теперь алгоритм, пока что пересечения прямой L и многогранника М:

Просматриваем рёбра М, и с ними проводим тест на пересечение с полуплоскостью П. Если ребро и полуплоскость имеют общую точку, то в счётчике граней, которым ребро принадлежит, прибавляется 1 (предварительно счётчик - массив, имеющий ту же размерность, что и список граней, - обнуляется). Если после просмотра всех рёбер хотя бы в одном из счётчиков нечётное число, то L и М пересекаются. Основным в данном алгоритме является тест на пересечение ребра (отрезка) и полуплоскости.

Массив координат может быть задан любым способом, это может быть и сплошной массив, где каждые три члена - три координаты узла грани многогранника, а т.к. грань - треугольник, то каждые 9 членов - это грань. Может быть задан списком TList, где каждый член - это x, y, z: GLFloat, как удобно... хоть тремя массивами... Структура многогранника задаётся массивом S рамерности 4*Е, где Е - число рёбер. Здесь S[1, i] и S[2, i] - номера вершин многогранника, являющиеся концами i-го ребра, а S[3, i] и S[4, i] - номера граней, для которых i-е ребро является общим. F - число граней, = V div 3, где V - список, и = V div 9 где V - массив координат (в зависимости от того, как представлять массив, писал выше)... IND[i] = счётчик.

Т.е. имеем нечто (Листинг №1):

Код

for i:=1 to F do IND[i]:=0; // обнуляем счётчик  for i:=1 to F do begin        // SemplaneSegment(П, S[1, i],  S[2, i]);тест на пересечение полуплоскости и отрезка,         // возвращает 1 если пересечение есть, и 0, если нет.        IND[S[3, i]]:=IND[S[3, i]] + SemplaneSegment(П, S[1, i],  S[2, i]); // Для каждой грани заносим         IND[S[4, i]]:=IND[S[4, i]] + SemplaneSegment(П, S[1, i],  S[2, i]); // информацию в счётчик  end;  for i:=1 to F do begin        if IND[i] = нечётно  then 'пересечение есть'         else 'пересечения нет';  end;

Теперь, основная задача - принадлежность точки Р многограннику М. Как известно из вышесказанного (а то сами не догадались) - каждое ребро многогранника является общим только для 2х граней, обзавём их Fk1 и Fk2. Обозначим плоскости их соотвественно Пk1 и Пk2. Ребро назовём Ek "отмеченным", если П пересекает Ek и только одна из плоскостей, Пk1 или Пk2, пересекается с L. Т.е. если полуплоскость П не проходит через вершины многогранника М, то точка Р принадлежит М, если и только если число отмеченных рёбер - нечётно, и в противном случае Р лежит вне М, т.е. число отмеченных рёбер - чётно...

вот теперь, я подошёл и к алгоритму нахождения решения принадлежности точки к многограннику

Сначала проводим тест на пересечение граничных плоскостей Пk и луча L, формируем список признаков INTR(k), где INTR(k):= -1, если пересечения нет, INTR(k):= 0, если Пk пересекает L вблизи точки Р (точность задаётся), и INTR(k):= 1, если пересечение есть. Далее просматриваются рёбра М и , если встречается ребро Еk, у которого только одна из плоскостей Пkj пересеккается с L, проводится тест на пересечение Ek и П. Если пересечение есть, то ребро - отмечается. Подсчитав число отмеченных рёбер (можно брать сумму по mod 2) и определив чётность, выясняется, лежит точка Р вне или внутри М.

Тест на пересечение Пk и L примерно так: если уравнение плоскости Пk - следующее x=Bk*y + Ck*z + Dk (такая форма записи всегда возможна, если только L и Пk - непараллельны, а если же они параллельны, то пересечения нет), то L и Пk пересекаются, когда Bk*y0 + Ck*z0 + Dk > x0. Коэффициенты уравнения плоскости, как правило, несложно определить при любом способе многогранника, а по трём точкам (треугольник) плоскость определяется через матрицу.
Важно знать, лежит ли Р вблизи границы М с точностью до некоторого числа W. Для граней, у которых INTR(k)=0 нужно завести отдельный счётчик. В случае если ребро пересекается с П и является стороной Fk, прибавить к счётчику Fk единицу. Если на выходе в каком-то из счётчиков - нечет, то Р лежит на этой грани.
Добавим к прошлым переменным ещё пару... FP - массив размера 4*F коэффициентов плоскостей, проходящих через грани М.

Вот, примерно что должно получиться...
(Листинг №2)

Код

for i:=1 to F do begin        INTR[i]:=LightPlane(L, FP[i]);        // LightPlane(L, FP[i]) - функция пересечения луча и плоскости, возвращает 1,        // если плоскость i-й грани пересекает луч, и 0, если нет, массив INTR имеет размерность F...       INDP:=0;  end;  for i:=1 to E do begin       if (INTR[S[3, i]] + INTR [S[4, i]]) = 1 then begin             INDP:= INDP + SemplaneSegment(П, S[1, i],  S[2, i]); // счётчик              // SemplaneSegment(П, S[1, i],  S[2, i]); тест на пересечение полуплоскости и отрезка и 1-го листинга       end;       if INDP = нечёт then 'точка внутри многогранника' else 'вне многогранника'; // тут пока без граничных точек  end;

SemplaneSegment(П, S[1, i], S[2, i]); - тест на пересечение ребра и полуплоскости. Тут нужно подробнее... Будем рассматривать сучай, когда полуплоскость - суть верхняя полуплоскость 0XY, остальные случаи приводятся к этому вращением пространства. (достаточно 3 вращения вокруг координатных осей, чтобы совместить две полуплоскости) Итак, у нас полуплоскость П: z=z0, y>y0 и ребро Е, задаваемое координаными вершинами V1(x1,y1,z1) и V2(x2,y2,z2). Сопоставим каждой вершине Vi код Сi = 0, 1, 2, 3 по следующему правилу:

Код

Ci = 0 если zi >= z0 и yi >= y0 Ci = 1 если zi >= z0 и yi < y0 Ci = 2 если zi < z0   и yi < y0 Ci = 3 если zi < z0   и yi >= y0

Е и П пересекаются, если один из кодов вершин = 0, а другой 3, и могут пересекаться, если С2 = С1 + 2 (mod 4), т.е. (С1, С2) = (0, 2); (2, 0); (1, 3); (3, 1). В остальных случаях - пересечения заведомо нет.


Это ж, готовая статья.. нужен только код... У меня мозг полностью отключен... Тот, кто напишет код - получит от меня + в репу и ссылку на своё соавторство в FAQ по Delphi... Кто бы ещё закрепил пока эту тему...

Модератор: Название темы должно отражать ее суть!

...

Это сообщение отредактировал(а) Quadr0 - 14.7.2011, 22:45

Цитата(Quadr0 @ 11.7.2005, 14:31)

Берём 2 координаты краааайних точки многогранника. Если координата точки больше координаты меньшей точки и меньше координаты большей точки, то... точка внутри! Этот способ успешно работает в 2D, а для 3D реализовать его не составит и труда. Просто 3 раза по 3 осям (x, y, z) проделай такое сравнение, взяв для каждой оси крайние точки. Даже код бы привёл, но у меня не стоит OpenGL Library, да и, как я сказал в 3D я пока профан

Скажем так, фигура представляет собой стокан И твой вариант уже не работает. К тому же не факт, что максимальные и минимальные координаты не будут соотвествовать какому-нибудь отростку. Ведь никто не говорит, что многогранник - это куб...




Добавлено @ 16:06

...

Это сообщение отредактировал(а) Quadr0 - 14.7.2011, 22:45

Цитата(Quadr0 @ 11.7.2005, 17:48)

ересечение будет только с одной плоскостью. У стакана же дырка сверху.

А что, толщина стенок =0? Я об этом не говорил, я сказал "Тело", и "замкнутая поверхность"... Т.е. твой вариант - окажись точка внутри стакана, он покажет её принадлежность ему.... Что в корне не верно.

...

Это сообщение отредактировал(а) Quadr0 - 14.7.2011, 22:45

По порядку:
Имеем массив вершин в виде списка, задаём его глобально.

Код

private     { Private declarations }     ...     Model : TList;

Каждая его запись - это (xi, yi, zi)
т.к. каждая грань у нас - это треугольник, то считывать массив нужно сразу по три записи:

Код

for i := 0 to round (Model.Count / 3)-1 do begin           // тут проводим необходимые манипуляции с узлами.           // Model.Items [i * 3] - это (x1, y1, z1)           // Model.Items [i * 3 + 1] - это (x2, y2, z2)           // Model.Items [i * 3 + 2] - это (x3, y3, z3)         end;

Чтобы не было иллюзий по поводу объекта - вот разложенный массив (частично, т.к. целиком - оооочень много) очень простого, очень маленького объекта:

Код

способ записи : x1; y1; z1; x2; y2; z2; x3; y3; z3;  -0,863885998725891; -0,117430999875069; 2,29054307937622; -0,940873026847839; 0; 2,30152010917664; -0,38332998752594; 0; 2,80417609214783;  -0,38332998752594; 0; 2,80417609214783; -0,273265987634659; -0,0881099998950958; 2,78583192825317; -0,863885998725891; -0,117430999875069; 2,29054307937622;  -0,273265987634659; -0,0881099998950958; 2,78583192825317; -0,38332998752594; 0; 2,80417609214783; 0,0936160013079643; 0; 3,03528094291687;  0,0936160013079643; 0; 3,03528094291687; 0,141424998641014; -0,0514210015535355; 2,99137306213379; -0,273265987634659; -0,0881099998950958; 2,78583192825317;  0,141424998641014; -0,0514210015535355; 2,99137306213379; 0,0936160013079643; 0; 3,03528094291687; 0,548605024814606; 0; 3,06835794448853;  0,548605024814606; 0; 3,06835794448853; 0,574316024780273; -0,0183439999818802; 3,00595998764038; 0,141424998641014; -0,0514210015535355; 2,99137306213379;  0,574316024780273; -0,0183439999818802; 3,00595998764038; 0,548605024814606; 0; 3,06835794448853; 0,809033989906311; 0; 2,99859404563904;  0,555972993373871; -0,143141001462936; 2,15115690231323; 0,548605024814606; 0; 2,41158390045166; 0,702723979949951; 0; 2,05207109451294;  -0,0164490006864071; -0,168706998229027; 2,26483106613159; -0,863885998725891; -0,117430999875069; 2,29054307937622; -0,273265987634659; -0,0881099998950958; 2,78583192825317;  -0,273265987634659; -0,0881099998950958; 2,78583192825317; 0,20006799697876; -0,0881099998950958; 2,57307004928589; -0,0164490006864071; -0,168706998229027; 2,26483106613159;  0,20006799697876; -0,0881099998950958; 2,57307004928589; -0,273265987634659; -0,0881099998950958; 2,78583192825317; 0,141424998641014; -0,0514210015535355; 2,99137306213379;  0,141424998641014; -0,0514210015535355; 2,99137306213379; 0,35418900847435; -0,0514210015535355; 2,74177694320679; 0,20006799697876; -0,0881099998950958; 2,57307004928589;  0,35418900847435; -0,0514210015535355; 2,74177694320679; 0,141424998641014; -0,0514210015535355; 2,99137306213379; 0,574316024780273; -0,0183439999818802; 3,00595998764038;  -3,34644103050232; 0; 1,19810402393341; -3,43257689476013; -0,110063999891281; 1,09119403362274; -3,51025795936584; 0; 1,04242694377899;  -3,43257689476013; -0,110063999891281; 1,09119403362274; -3,34644103050232; 0; 1,19810402393341; -3,07526707649231; 0; 1,40385103225708;  -3,07526707649231; 0; 1,40385103225708; -3,13770389556885; -0,201783999800682; 1,31700205802917; -3,43257689476013; -0,110063999891281; 1,09119403362274;  -2,75811004638672; -0,0769869983196259; 1,58736801147461; -2,68296194076538; 0; 1,6509850025177; -2,16472101211548; 0; 1,95026898384094;  -2,16472101211548; 0; 1,95026898384094; -2,18668794631958; -0,264183014631271; 1,86382603645325; -2,75811004638672; -0,0769869983196259; 1,58736801147461;  -2,74601101875305; -0,201783999800682; 1,55679500102997; -2,75811004638672; -0,0769869983196259; 1,58736801147461; -2,18668794631958; -0,264183014631271; 1,86382603645325;  -2,18668794631958; -0,264183014631271; 1,86382603645325; -2,16472101211548; 0; 1,95026898384094; -1,52589201927185; 0; 2,19547009468079;  -1,52589201927185; 0; 2,19547009468079; -1,54321897029877; -0,322825998067856; 2,11951303482056; -2,18668794631958; -0,264183014631271; 1,86382603645325;  -1,54321897029877; -0,322825998067856; 2,11951303482056; -1,52589201927185; 0; 2,19547009468079; -0,940873026847839; 0; 2,30152010917664;  -0,940873026847839; 0; 2,30152010917664; -0,863885998725891; -0,117430999875069; 2,29054307937622; -1,54321897029877; -0,322825998067856; 2,11951303482056;  -1,54321897029877; -0,322825998067856; 2,11951303482056; -0,863885998725891; -0,117430999875069; 2,29054307937622; -0,907939016819; -0,355902999639511; 2,07417011260986;  -0,907939016819; -0,355902999639511; 2,07417011260986; -0,863885998725891; -0,117430999875069; 2,29054307937622; -0,0164490006864071; -0,168706998229027; 2,26483106613159;  -0,0164490006864071; -0,168706998229027; 2,26483106613159; -0,0677250027656555; -0,385224014520645; 2,05207109451294; -0,907939016819; -0,355902999639511; 2,07417011260986;  -0,0677250027656555; -0,385224014520645; 2,05207109451294; -0,0164490006864071; -0,168706998229027; 2,26483106613159; 0,555972993373871; -0,143141001462936; 2,15115690231323;  0,555972993373871; -0,143141001462936; 2,15115690231323; 0,743022978305817; -0,293503999710083; 1,87960696220398; -0,0677250027656555; -0,385224014520645; 2,05207109451294;

Хмммм... Короче, сперва давай составиv алгоритм и напишем саму функцию теста на пересечение полуплоскости и отрезка.

Т.е. тут имеем задачу, пересечения отрезка с полуплоскостю. Повторюсь, для каждой вершины ребра задаём коды Сi...

Код

Ci = 0 если zi >= z0 и yi >= y0 Ci = 1 если zi >= z0 и yi <  y0 Ci = 2 если zi <  z0 и yi <  y0 Ci = 3 если zi <  z0 и yi >= y0

Попробую изобразить алгоритм:

Код

function SemplaneSegment(П, S[1, i], S[2, i]): integer; ... begin ...    if (zi >= z0) and (yi >= y0) then COD[i]:=0;    if (zi >= z0) and (yi < y0) then COD[i]:=1;    if (zi < z0) and (yi < y0) then COD[i]:=2;    if (zi < z0) and (yi >= y0) then COD[i]:=3;    //... ...       if (COD[i+1]=COD[i]+2 (mod 4)) then SemplaneSegment():=1 else SemplaneSegment():=0; end;

Должно быть нечто подобное... Почему именно такой алгоритм я выбрал, потому что до этого я пытался рассчитать телесный угол. Цикл по всем узлам и рассчитывал телесный угол со всеми гранями ( треугольниками ) тела. Если этот угол равен 4Пи, то узел находится внутри, в противном случае снаружи. Но такой алгоритм работал 12 часов (при том, что у процесса стоял максимальный приоритет)... После чего вешал систему... Очень неопртимальный вариант... Этот должен на порядок быстрее работать. У меня в системе до 10 миллионов узлов.

Цитата(Quadr0 @ 11.7.2005, 20:10)

её координата х больше х левой стенки и меньше х правой.

И от куда ты знаешь, какая х левая, а какая правая?

Цитата(Quadr0 @ 11.7.2005, 20:10)

Дно же у нас будет,

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

мда... интересный способ...

а через вектора реализовать не пробовали...

Могу предложить следующий оригинальны алгоритм.
Окружаем фигуру кубом(не обязательно соприкасающимся, лишь бы вся фигура поместилась в куб)
1. Точку отмечаем флагом 1
2. От нее проверяем все соседние точки на предмет того не пересеклись ли они с кубом, если пересеклись, то точка наружняя, если нет, то отмечаем ее флагом 1.
3. Рекурсивно от полученных точек проверяем все ближайшие точки, которые не имеют флага 1 и повторяем до исчерпания всех точек. Если так никто с кубом и не пересекся, то точка внутри

Набросок

function Naruzhnyaya(x,y,z:integer):boolean;
var b:boolean;
begin
b:=false;
if PereseklasSFiguroy(x,y,z)=1 then flag[x,y,z]=1;
if flag[x,y,z]=1 then
else
begin
flag[x,y,z]=1;
if PereseklasSKubom(x,y,z) then
b=true
else
b:=Naruzhnyaya(x-1,y,z0) or Naruzhnyaya(x+1,y,z) or Naruzhnyaya(x,y-1,z) or Naruzhnyaya(x1,y+1,z) or
Naruzhnyaya(x,y,z-1) or Naruzhnyaya(x,y,z+1) or Naruzhnyaya(x+1,y+1,z) or Naruzhnyaya(x-1,y+1,z) or
Naruzhnyaya(x+1,y-1,z) or Naruzhnyaya(x-1,y-1,z) or Naruzhnyaya(x,y+1,z+1) or Naruzhnyaya(x,y-1,z+1) or Naruzhnyaya(x,y+1,z-1) or Naruzhnyaya(x,y-1,z-1) or Naruzhnyaya(x+1,y,z+1) or Naruzhnyaya(x+1,y,z+1) or Naruzhnyaya(x+1,y,z-1) or Naruzhnyaya(x-1,y,z+1) or Naruzhnyaya(x-1,y,z-1) or Naruzhnyaya(x+1,y+1,z+1) or Naruzhnyaya(x+1,y+1,z-1) or Naruzhnyaya(x+1,y-1,z+1) or Naruzhnyaya(x+1,y-1,z-1) or Naruzhnyaya(x-1,y+1,z+1) or Naruzhnyaya(x-1,y+1,z-1) or Naruzhnyaya(x-1,y-1,z+1) or Naruzhnyaya(x-1,y-1,z-1);
end;
Naruzhnyaya:=b;
end;

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

...

Это сообщение отредактировал(а) Quadr0 - 15.7.2011, 00:38

Quadr0, OpenGL тут не причём, да хоть Direct3D... Какая разница... Это же математика, а не графика... Ведь фигуру можно просчитывать, не рисуя её... а представив в виде массива её вершин...

Daemon05, попробуем разобрать то, что ты предлагаешь...

Цитата(Daemon05 @ 12.7.2005, 03:52)

Окружаем фигуру кубом(не обязательно соприкасающимся, лишь бы вся фигура поместилась в куб)

Это понятно... просто ограничиваем пространство вокруг многогранника.

Цитата(Daemon05 @ 12.7.2005, 03:52)

1. Точку отмечаем флагом 1

Пусть..

Цитата(Daemon05 @ 12.7.2005, 03:52)

2. От нее проверяем все соседние точки на предмет того не пересеклись ли они с кубом, если пересеклись, то точка наружняя, если нет, то отмечаем ее флагом 1.

Как точка может с чем-нибудь пересечься? Она же точка! Да и предстваь, что создаётся конечноразнстная сетка 1000000х1000000х1000000 узлов, т.е. это габариты куба.

Цитата(Daemon05 @ 12.7.2005, 03:52)

3. Рекурсивно от полученных точек проверяем все ближайшие точки, которые не имеют флага 1 и повторяем до исчерпания всех точек. Если так никто с кубом и не пересекся, то точка внутри

По любому нужно определить, не то, что точка внутри, или нет куба, а фигуры, сложного многогранника.

А мне непонятно... По какой такой причине это перенесено в раздел "Delphi: Звук, графика и видео"?

Цитата(Quadr0 @ 11.7.2005, 13:31)

dr.ZmeY? Берём 2 координаты краааайних точки многогранника. Если координата точки больше координаты меньшей точки и меньше координаты большей точки, то... точка внутри! Этот способ успешно работает в 2D, а для 3D реализовать его не составит и труда. Просто 3 раза по 3 осям (x, y, z) проделай такое сравнение, взяв для каждой оси крайние точки. Даже код бы привёл, но у меня не стоит OpenGL Library, да и, как я сказал в 3D я пока профан Думаю 1 плюч я хотя бы заслужил

Этот алгоритм не обязан работать в 2D. В доказательство возьми виток толстой спирали, точка в центре, по твоему алгоритму она получается внутри

Прошлый алгоритм явно не годится для таких размеров. Попробуем методы аналитической геометрии.
Есть еще метод, но тяжело объяснить без рисунков и чертежей
Теория: У каждого треугольника есть три других треугольника, с которыми он имеет общую сторону.
1. Сориентируем поверхность, для этого к каждому треугольнику дадим нормаль, направление которой для первого треугольника выбирается произвольно, допустим обходя контур по часовой стрелке и проводя нормаль буравчиком. Для остальных треугольников нормаль выбирается следующим образом. Допустим мы обошли произвольно треугольник ABC, причем в направлении по контуру от A к B, от B к C, от C к A . Тогда треугольник BCD обходим в направлении C>B>D, аналогично соседний к нему треугольник обходим в направлении D>B>E и т.д.
Получаем в памяти набор нормалей, количество которых равно количеству треугольников.
2. Возьмем очевидно наружную точку. Допустим возьмем для этого далекую точку. Ищем ближайшую вершину треугольника. Находим ее. Проводим вектор в направлении от вершины до точки и скалярно множим на вектор найденной в п.1. нормали любого из трех треугольников, которому принадлежит эта ближайшая точка. Что получилось при этом умножении неважно - главное знак - плюс или минус. Допустим плюс.
3. Вот и все. Теперь чтобы определить наружность любой точки, просто находим ближайшую к этой точке вершину, проводим вектор в направлении от ближайшей вершины до точки и скалярно множим этот вектор на нормаль любого из трех треугольников которым принадлежит эта вершина. Опять же интересен только знак если плюс - точка снаружи, если минус то внутри.

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

Не знаю поняли ли вы чего из сказанного выше
Тот же алгоритм на пальцах:
1. Мы просто раскрашиваем внутренние стороны каждого треугольника в черный цвет, а наружние в красный. При этом не забываем, что можем ошибится и раскрасить наоборот внутренность треугольников в красный а наружность в черный.
2. Теперь смотрим на ближайший треугольник от явно наружней точки и определяем красного или черного цвета стенку мы видим. Допустим черный - ура, значит наружняя сторона покрашена черным
3. Теперь от нужной нам точки смотрим на ближайший треугольник. Если видим черный цвет то точка внутри фигуры если красный, то снаружи.

И совсем на пальцах:
Если вас посадить в коробку черного цвета, но при этом обитую внутри красным, то увидев красный цвет вы догадаетесь что находитесь внутри


Это сообщение отредактировал(а) Daemon05 - 13.7.2005, 02:53

Хмммм... Я смотрю тут многие не совсем понимают суть задачи.... Графика в данной задачи - это всего-лишь визуализация решения - и это подзадача далеко не самой высшей сложности и важности.

Поясню на пальцах. Необходимо создать разностную сетку в некоторой прямоугольной области Lx на Ly на Lz размером Nx на Ny на Nz, в которой находится 3D объект (или объекты) - правильный многогранник, каждая грань которого - треугольник. Общее число узлов Nx*Ny*Nz. К примеру Nx=Ny=Nz=100. Общее число узлов 1000000. Нам надо выпускать 10000 (100*100) лучей с какой-либо грани и смотреть перебором какие из треугольников пересечет каждый луч. Для данного луча мы получим набор точек пересечения с многогранником. Эти точки надо будет упорядочить по возрастанию, а затем способом чет-нечет определить, лежит ли узел с координатами x,y,z внутри или вне многогранника. Например мы выпустили луч снизу (из точки xl,yl,0) и нашли, что он пересекает тело в шести точках z1,z2, .... z6. Тогда можно идти по этому лучу через шаг сетки и смотреть, сколько раз перешли точки пересечения. Если 0 или четное число раз, то узел вне многогранника. Иначе внутри.
Для надежности можно пустить лучи не с одной грани, а с трех (снизу, сбоку,сзади). Если по лучу снизу узел вне многогранника, а по боковому и заднему внутри, то считать что узел внутри. Это для того, чтобы исправить ошибки
конструирования фигуры (многогранника). Иногда могут попасться незамкнутые поверхности, и у нас получиться нечетное число пересечений, чего в реале быть не может.

Тут наверняка можно несколько упростить (и одновременно усложнить) алгоритм... Если отказаться от создания полуплоскости, и считать как пересечение луча с треугольником (гранью многогранника).
Решение будет состоять из следующих шагов:

• Проверка: параллельна ли прямая плоскости
• Нахождение пересечения плоскости треугольника с отрезком

Точка пересечения P находится подстановкой в уравнение плоскости Ax + By + Cz + D = 0 уравнения прямой P = P1 + мю (P2 - P1). (рис 1) Р2 у нас заведомо лежит дальше, т.е. это луч.

Заметим, что значения A,B,C являются компонентами вектора нормали к плоскости, И они у нас есть (есть так же массив, в котором находятся значения векторов нормали ко всем треугольникам).

D можно затем получить, подставлив одну из вершин в уравнение плоскости, например

A*Pa*x + B*Pa* + C*Pa* = -D
Это дает нам выражение для мю, из которого точка пересечения P может быть найдена через уравнение прямой.

мю = ( D + A P1x + B P1y + C P1z ) / ( A (P1x - P2x) + B (P1y - P2y) + C (P1z - P2z) )

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

Ну и в последнюю очередь необходимо установить, лежит ли точка пересечения внутри треугольника, ограниченного Pa, Pb, Pc.

Способ, которым мы воспользуемся, опирается на то, что сумма внутренних углов вида вершина-точка-вершина равна 2pi, если точка внутри треугольника. Для точки вне треугольника эта сумма будет меньше. Очевидно, сумма берется для одной точки - точки пересечения линии и плоскости и по всем сочетаниям вершин, как проиллюстрировано на рисунке 2

Если мы вычислим единичные векторы Pa1, Pa2, Pa3 как (мы проверяем точку P на принадлежность треугольнику)

Pa1 = (Pa - P) / |(Pa - P)|
Pa2 = (Pb - P) / |(Pb - P)|
Pa3 = (Pc - P) / |(Pc - P)|

углы будут


a1 = acos(Pa1 * Pa2)
a2 = acos(Pa2 * Pa3)
a3 = acos(Pa3 * Pa1)

Рис.1

Присоединённый файл ( Кол-во скачиваний: 14 )
 linefacet1_1_.gif 2,29 Kb

Рис.2

Присоединённый файл ( Кол-во скачиваний: 7 )
 linefacet2_1_.gif 1,25 Kb

Будем обозначать A,B,C - точки плоскости, X,Y - точки прямой(концы отрезка), SP - скалярное произведение, VP - векторное произведение. O - искомое множество точек пересечения

Код

N: = VP ( B - A, C - A ); N: = N / | N |  - нормаль к плоскости  // в принципе это можно и не делать V: = A - X // расстояние до плоскости по нормали d: = SP ( N, V )   W: = Y - X // приближение к плоскости по нормали при прохождении отрезка e: = SP ( N, W )  if e<>0)   O: = X + W * d/e          // одна точка else  if d=0   O: =X + W * (anything)     // прямая принадлежит плоскости else   O: = empty;                // прямая параллельна плоскости

dr.ZmeY:
1. лудше твои многоугольники привести к треугольникам(триангуляция).
2. Правильно пронумировать узлы... т.е. от ентого будет зависить куда будет направленна нормаль элемента(треугольника). Т.е. нормали должны быть или внутрь тела... или от тела.

Например... принимаем что в тело.

PS: И не забывать об окрестности(погрешности)... при которой будет считаться что узлы совпадают.

3. Проверить замкнуто ли твое тело или нет. Т.е. имеет ли оно объем... или енто просто сложная поверхность.

Не объем: выход.

Если объем:
4. Проверить принадлежность точки какому нить элементу(треугольнику).

Принадлежит: выход.

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

Если снаружи:
6. Например проверить: точка внутри полости тела или вне его.

Это сообщение отредактировал(а) Girder - 13.7.2005, 11:35

Цитата(Girder @ 13.7.2005, 12:28)

1. лудше твои многоугольники привести к треугольникам(триангуляция).

Почитай внимательнее, они уже представлены как треугольники (иначе нельзя, ведь импорт идёт из DXF-файла)

Цитата(Girder @ 13.7.2005, 12:28)

2. Правильно пронумировать узлы... т.е. от ентого будет зависить куда будет направленна нормаль элемента(треугольника). Т.е. нормали должны быть или внутрь тела... или от тела.

Нормаль направлена наружу... Это не сильно относится к задаче... Нормаль определяет больше пложение грани, и её видимость при визуализации в OpenGL или D3D...

Цитата(Girder @ 13.7.2005, 12:28)

3. Проверить замкнуто ли твое тело или нет. Т.е. имеет ли оно объем... или енто просто сложная поверхность.

А вот это проверить нереально... Считаем, что замкнуто... Если нет, то будет ошибка, или придётся направлять лучи в разные стороны, и проверять, сравнивать результаты... Ошибку это устранит, но алгоритм будет в 4 раза долше работать, что не желательно...

Цитата(Girder @ 13.7.2005, 12:28)

4. Проверить принадлежность точки какому нить элементу(треугольнику). Принадлежит: выход. Нет не принадлежит: 5. Проверить в любом направлении, от точки, нормаль элемента(треугольника). Если он лежит над плоскостью(со стороны точки) перпендикулярной рассматриваемого направления - то точка находиться внутри... иначе с наружи. Если снаружи: 6. Например проверить: точка внутри полости тела или вне его.

Масло масленное, этот алгоритм я уже и описал, собсвенно...

Вот, попробую простенький аналог привести, это вариант с крайними вершинами, как был предложен Quadr0, только для 2D. Тут нужно определить, принадлежит ли точка с координатами (х0,у0) многоугольнику (x[i], y[i]) где i=1,2,3..n.

Код

function pointpol(x0,y0:real, x,y array of real) : boolean; var i:integer; b:boolean; begin    x[n+1]:=x[1]; y[n+1]:=y[1]; // на всякий пожарный перезамыкаем многоугоьник    b:=false;    for i:=1 to n do begin        if (y0<y[i]) or (y0>y[i+1]) then begin             if (x0-x[i])<((y0-y[i]) * (x[i+1]-x[i])/(y[i+1]-y[i])) then begin                  b:=true;             end;        end;    end;   pointpol:=b; end;

Как ясно, тут никак нельзя учесть многоугольник с отверстием....

Цитата(dr @ 13.7.2005, 14:59)

А вот это проверить нереально...

Здрасти... А какже проверка окрестности всех узлов(точек)?

Цитата(dr @ 13.7.2005, 14:59)

Как ясно, тут никак нельзя учесть многоугольник с отверстием....

Так триангулированно у тебя тело(поверхность тела) или нет?

Это сообщение отредактировал(а) Girder - 13.7.2005, 15:48

Цитата(Daemon05 @ 13.7.2005, 03:11)

Теперь от нужной нам точки смотрим на ближайший треугольник.

Вот в этом то и проблема - в определении "ближайшего" треугольника. Хотя идея интересная, красивая...

Кстати, если рассматривать вариант Quadr0 для определения пересечения луча с гранью, т.е. 2D, можно использовать его гля проекции грани и луча, тогда это будет многоугольник (треугольник) и точка... Хммм...
Добавлено @ 16:52

Цитата(Girder @ 13.7.2005, 16:47)

Так триангулированно у тебя тело(поверхность тела) или нет?

А что? Одно другому мешает?

К твоей теории про полуплоскости и лучи у меня появились следующие замечания:

Цитата

если провести от этой точки (назовём её P) луч (L) в любую сторону, то, если он будет иметь чётное число пересечений с многогранником М, то это значит, что точка Р лежит вне объекта М, в противном случае - она внутри него,

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

Цитата

Однако, решать задачу пересечения луча и ограниченной треугольником плоскости - трудоёмко

Ничего трудоемкого. В твоем случае когда луч выходит из точки x0, y0, z0. Идет параллельно оси z, т.е. луч (x=x0, y=y0, z>z0), а треугольник задется набором координат трех его вершин (x1,y1,z1;x2,y2,z2;x3,y3,z3) то вычисляются три числа a1, a2,a3 по следующим формулам:

a1=((x2-x0)*(y3-y0)-(y2-y0)*(x3-x0))/D
a2=((y1-y0)*(x3-x0)-(x1-x0)*(y3-y0))/D
a3=((x1-x0)(y2-y0)-(x2-x0)*(y1-y0))/D

где заранее вычисляется D=(x1-x0)*(y2-y0)(z3-z0)+(z1-z0)*(x2-x0)*(y3-y0)+(y1-y0)*(z2-z0)*(x3-x0)-(z1-z0)*(y2-y0)*(x3-x0)-(y1-y0)*(x2-x0)*(z3-z0)-(x1-x0)*(y3-y0)*(z2-z0)

Если все три числа a1,a2,a3 неотрицательны, то луч пересекает треугольник, при этом кроме того(что неотрицательны) если одно из чисел равно нулю, то луч пересекает ребро треугольника, если два числа равны нулю, то луч пересекает вершину треугольника. Все три числа равны нулю никак быть не смогут. Если хоть одно или два числа отрицательны, то луч совсем никак не проходит через треугольник. Но если все три числа отрицательны, то луч проходил бы через треугольник если пусть его в точности в обратную сторону.
Если D получилось равно нулю, то будет деление на ноль, тут необходимы дополнительные вычисления, но я их приводить не буду. Это означает, что луч может не просто пересечь, но пройти вдоль грани треугольника.

Цитата

Есои полуплоскость П не проходит через вершины многогранника М, то прямая L не пересекает этот многогранник тогда и только тогда, когда для каждой грани М полуплоскость П пересекает чётное (0,2,4,6,...) число её рёбер...

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

Прошлое сообщение мое было!

Цитата(Guest @ 14.7.2005, 03:57)

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

Аааааа.... ты внимательно читал правила?

Цитата

Есои полуплоскость П не проходит через вершины многогранника М, то прямая L не пересекает этот многогранник тогда и только тогда, когда для каждой грани М полуплоскость П пересекает чётное (0,2,4,6,...) число её рёбер...

Цитата

если полуплоскость П не проходит через вершины многогранника М, то точка Р принадлежит М, если и только если число отмеченных рёбер - нечётно, и в противном случае Р лежит вне М, т.е. число отмеченных рёбер - чётно...

Это ж как теоремы...
К тому же проверку можно простую сделать... Пускаем лучи во все 4 стороны и смотрим, если в 3х из 4х случаев внутри, значит внутри, или наоборот

Цитата(Guest @ 14.7.2005, 03:57)

Ничего трудоемкого. В твоем случае когда луч выходит из точки x0, y0, z0. Идет параллельно оси z, т.е. луч (x=x0, y=y0, z>z0), а треугольник задется набором координат трех его вершин (x1,y1,z1;x2,y2,z2;x3,y3,z3) то вычисляются три числа a1, a2,a3 по следующим формулам: a1=((x2-x0)*(y3-y0)-(y2-y0)*(x3-x0))/D a2=((y1-y0)*(x3-x0)-(x1-x0)*(y3-y0))/D a3=((x1-x0)(y2-y0)-(x2-x0)*(y1-y0))/D где заранее вычисляется D=(x1-x0)*(y2-y0)(z3-z0)+(z1-z0)*(x2-x0)*(y3-y0)+(y1-y0)*(z2-z0)*(x3-x0)-(z1-z0)*(y2-y0)*(x3-x0)-(y1-y0)*(x2-x0)*(z3-z0)-(x1-x0)*(y3-y0)*(z2-z0)

Всё намного проще ты мой последний пост не читал берём проекцию треугольника и луча на плоскости, т.е. имеем точку с координатами (x0,y0,z0), её проекция на плоскости 0XY будет (x0,y0), берём проекцию треугольника (x1,y1,z1; x2,y2,z2; x3,y3,z3), его проекция на той же плоскости - (x1,y1; x2,y2; x3,y3) и решаем задачу на плоскости, да к тому же убрав лишнюю координату - многократно ускоряем алгоритм Ведь нас интересует - пересекает ли луч где z>=z0 а что такое этот луч, как не проекция (точка с координатами (x0,y0))... И тут, даже если луч упёрся в ребро (точка лежит на стороне треугольника) - то всё равно она ему принадлежит Но тут колизия, нельзя проверять смежную грань, ведь луч упёшись в ребро, делает принадлежность свое положительным и для другой грани... что при подсчёте пересечений может дать ошибку, хотя и вероятность этого мала, но нельзя от неё отрекаться... Так что в любом случае нужно пускать лучи во все стороны


ЗЫ: А Quadr0 получает +, за то, что сам того не ведая, подкинул хорошую идею

Цитата

Аааааа.... ты внимательно читал правила?

:_)
Думаю, да - но ты носом ткни куды надо, на всякий случай

Цитата

К тому же проверку можно простую сделать... Пускаем лучи во все 4 стороны и смотрим, если в 3х из 4х случаев внутри, значит внутри, или наоборот

Здесь не статистика с ошибками эксперимента, здесь математика, а значит можно придумать фигуру настолько кривую, что 3 из 4 будут внутри или все 4 в ребра уйдут

Цитата

Всё намного проще ты мой последний пост не читал берём проекцию треугольника и луча на плоскости, т.е. имеем точку с координатами (x0,y0,z0), её проекция на плоскости 0XY будет (x0,y0), берём проекцию треугольника (x1,y1,z1; x2,y2,z2; x3,y3,z3), его проекция на той же плоскости - (x1,y1; x2,y2; x3,y3) и решаем задачу на плоскости, да к тому же убрав лишнюю координату - многократно ускоряем алгоритм Ведь нас интересует - пересекает ли луч где z>=z0 а что такое этот луч, как не проекция (точка с координатами (x0,y0))... И тут, даже если луч упёрся в ребро (точка лежит на стороне треугольника) - то всё равно она ему принадлежит

Посмотри внимательно - именно эта задача и решена в моих формулах. Там отсутствует z, во всех формулах, т.е. речь и идет о проекциях. Единственно z есть в вычислении D, но ведь нужно же определить идет луч в сторону треугольника или противоположную даже если проекции хорошо легли- (для D важен только знак)

Я все таки отрабатываю алгоритм, связанный с определением внешних и внутренних сторон треугольника, пока результаты следующие:
Пусть задан набор треугольников образующих фигуру.
1. Обозначим все узлы буквами(в конечной программе соответственно цифрами) т.е. для рисунка 1 это будут узлы A, B, C, D.
2. В задании треугольников расставим узлы в правильном порядке, т.е. допустим треугольники введены в программу в следующем порядке
ABC, DAB, BCD, ACD
Для этого
Возьмем двумерный массив M[N,3], (N - количество треугольников) в который заложим эту информацию
Содержимое массива M[4,3] в нашем случае (рис1) будет следующим:
[A,B,C] [D,A,B] [B,C,D] [A,C,D]
Заведем массив, который назовем потоком, т.к. он будет постепенно заполнятся, а в начале пуст
P[N,3,2] (в примере P[4,3,2]) чем он будет заполняться? А вот чем - первый треугольник разбиваем на пары вершин в строгом порядке как они указаны в массиве M т.е. A первым B вторым C третим и формируем пары(для этого последняя размерность массива сделана 2)
заполняем P для первого треугольника т.е. элемент P[1,x,x]
[AB,BC,CD]
Заполняем в P второй треугольник, но при этом проверяем, не встречались ли ранее такие же пары в том же порядке
[DA,AB... - опаньки AB уже было, - что тогда делаем - а переставляем во втором треугольнике в массиве M[2,x] A и B местами - получаем M[2,x]=[D,B,A]
попробуем еще раз
P[2,x,x]=[DB,BA,AD] - классно пары не повторились(теперь не AB а BA)

Теперь третий треугольник вводим его пары в P
P[3,x,x]=[BC... - опа, опять было!!! переставляем M[3,x]=[C,B,D] и еще разок попробуем
P[3,x,x]=[CB,BD,DC] - уффф ничего вроде не повторилось

ну и четвертый треугольник
P[4,x,x]=[AC,CD,DA] Ну тут повезло с первого раза - ничего не повторилось и соответственно ничего переставлять не надо. итого мы расставили узлы в правильном порядке в массиве М а именно
[A,B,C] [D,B,A] [C,B,D] [A,C,D]
а возникает вопрос - а на какой это все надо было - а то, что теперь мы по порядку следования узлов в треугольнике можем определить, внешнюю и внутренню сторону - а значит вычислить нормали всегда направленные наружу у всех треугольнико или вовнутрь. Действительно обратите внимание на порядок узлов - если идти от С к B, потом от B к D и наконец от D вернуться к С (рис2) то внешняя сторона треугольника обходится по часовой, а внутренняя против часовой стрелки - и так для всех треугольников - внешняя по часовой.


Присоединённый файл ( Кол-во скачиваний: 6 )
 _______.gif 3,44 Kb

Цитата(Daemon05 @ 15.7.2005, 03:07)

Здесь не статистика с ошибками эксперимента, здесь математика, а значит можно придумать фигуру настолько кривую, что 3 из 4 будут внутри или все 4 в ребра уйдут

Чем больше ухитряться, тем тормознутее придётся делать алгоритм...

Цитата(Daemon05 @ 15.7.2005, 03:07)

Посмотри внимательно - именно эта задача и решена в моих формулах. Там отсутствует z, во всех формулах, т.е. речь и идет о проекциях. Единственно z есть в вычислении D, но ведь нужно же определить идет луч в сторону треугольника или противоположную даже если проекции хорошо легли- (для D важен только знак)

Знаю, но слишком много вычислений... А теперь представь, что 10млн. точек нужно каждую сверить с 50 тыс треугольников...
Добавлено @ 04:05

Цитата(Daemon05 @ 15.7.2005, 04:21)

Я все таки отрабатываю алгоритм, связанный с определением внешних и внутренних сторон треугольника, пока результаты следующие:

Все нормали известны, все направлены наружу.... (иначе многогранник не построить)

Я абсолютно не читал что понаписали выше (нет времени сейчас), но х. сказ-ть, что проблема элементарно разрешается с помощью векторов. Заведи класс, например Vector, реализ. в нем все основные св-ва в-ров, в т ч смеш произведение. Далее из ланной точки проводишь вектор перпендикулярно какой-либо плоскости, если смеш произв этого вект и вывбранных опред образом вект из пл. например с координ xi+1-xi,... положительно, то этои ири в-ра образуют прав торойку и след. нах по ододну сторну плоскости. И так в цикле для всех полоскостей. Если знак везде один, то точка нах по одну сторону от всех плоскостей, те внутри фигуры.

Цитата

Я абсолютно не читал что понаписали выше (нет времени сейчас), но х. сказ-ть, что проблема элементарно разрешается с помощью векторов. Заведи класс, например Vector, реализ. в нем все основные св-ва в-ров, в т ч смеш произведение. Далее из ланной точки проводишь вектор перпендикулярно какой-либо плоскости, если смеш произв этого вект и вывбранных опред образом вект из пл. например с координ xi+1-xi,... положительно, то этои ири в-ра образуют прав торойку и след. нах по ододну сторну плоскости. И так в цикле для всех полоскостей. Если знак везде один, то точка нах по одну сторону от всех плоскостей, те внутри фигуры.

Я так делал... очень долгий алгоритм...
Добавлено @ 01:18
Собственно, у меня почти готово.. .потом, как-нибудь, выложу результат...

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

dr.ZmeY
Извини все сообщения "ниасилил".

Но почему, например нельзя сделать сечение данного тела горизонтальной плоскостью, проходящей через нужную точку, а потом решать задачу в 2D (собственно так же -- сечением) ?

Цитата(Daemon05 @ 15.7.2005, 03:21)

а возникает вопрос - а на какой это все надо было - а то, что теперь мы по порядку следования узлов в треугольнике можем определить, внешнюю и внутренню сторону - а значит вычислить нормали всегда направленные наружу у всех треугольнико или вовнутрь. Действительно обратите внимание на порядок узлов - если идти от С к B, потом от B к D и наконец от D вернуться к С (рис2) то внешняя сторона треугольника обходится по часовой, а внутренняя против часовой стрелки - и так для всех треугольников - внешняя по часовой.

Вот, хоть один человек движется в правильном направлении.

Давйте будем грамотными инженерами и обратимся к книгам Например
А.В.Боресков Е.В.Шикин Г.Е.Шикина "Компьютерная графика: первое знакомство" Москва. "Финансы и Статистика", 1996
страница 93-97 отсканированный фрагмент

Это сообщение отредактировал(а) DENNN - 29.7.2005, 15:23

P.S. через пару дней ссылку удалю, так что кому нужно качайте сейчас или как-то это дело на форум перенесите.

Это сообщение отредактировал(а) DENNN - 27.7.2005, 14:12

Те же страницы в DjVu.



Присоединённый файл ( Кол-во скачиваний: 17 )
 scan.djvu 254,35 Kb

А как определить принадлежит или нет точка многограннику, заданному координатами вершин в Maple.

Точно так же, как и не в Мaple.

Цитата(DENNN @ 27.7.2005, 13:56)

а возникает вопрос - а на какой это все надо было - а то, что теперь мы по порядку следования узлов в треугольнике можем определить, внешнюю и внутренню сторону - а значит вычислить нормали всегда направленные наружу у всех треугольнико или вовнутрь. Действительно обратите внимание на порядок узлов - если идти от С к B, потом от B к D и наконец от D вернуться к С (рис2) то внешняя сторона треугольника обходится по часовой, а внутренняя против часовой стрелки - и так для всех треугольников - внешняя по часовой.

А если многогранник вогнутый!?? Такой вариант не пройдет

Цитата(amium @ 4.12.2005, 21:34)

А если многогранник вогнутый!?? Такой вариант не пройдет

Читай внимаетльно отсканированные страницы. Там предлагается другое решение.

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

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

Цитата

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

Да и с простой вогнутой фигурой не сработает. Вот изображение.

Присоединённый файл ( Кол-во скачиваний: 10 )
 mnogogran.JPG 11,73 Kb

Да, твоя правда.