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

ЗАДАЧА
Имеется 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