Определете дали (x,y,z) точка е вътре във форма, дефинирана от масив от точки

Ако имам масив от точки (x,y,z) и ми е дадена една точка (x,y,z), какъв код да използвам, за да определя дали тази точка се намира във формата, дефинирана от масива?

Чертая празно на този...

използвам C#

РЕДАКТИРАНЕ

Благодаря за отговорите, момчета, от коментарите намерих тази връзка (http://alienryderflex.com/polygon/), което обяснява процеса доста добре.

Благодаря!

FYI:

bool pointInPolygon() {
    
      int      i, j=polySides-1 ;
      boolean  oddNodes=NO      ;
    
      for (i=0; i<polySides; i++) {
        if (polyY[i]<y && polyY[j]>=y
        ||  polyY[j]<y && polyY[i]>=y) {
          if (polyX[i]+(y-polyY[i])/(polyY[j]-polyY[i])*(polyX[j]-polyX[i])<x) {
            oddNodes=!oddNodes; }}
        j=i; }
     
      return oddNodes; }

Ще трябва малко работа, но това е куражът.

Благодаря отново


arrays c# shapes point shape
person Matt    schedule 10.02.2011    source източник
comment
възможен дубликат на C# точка в многоъгълник   -  person Jim Lewis    schedule 11.02.2011
comment
Това е добре известен проблем. Вижте en.wikipedia.org/wiki/Point_in_polygon   -  person Elian Ebbing    schedule 11.02.2011
comment
Вашият проблем е недостатъчно уточнен. Как масивът определя формата? Това ли е изпъкналата обвивка на точките в масива? Или има някакъв ред на триъгълни ленти с множество петна, който определя полиедър?   -  person Nordic Mainframe    schedule 11.02.2011
comment
Може би не точно дубликат на другата публикация, която намерих - просто забелязах, че Мат търси решение в 3 измерения.   -  person Jim Lewis    schedule 11.02.2011
comment
@Джим, @Елиан. Не, не е така. Това е точка в МНОГОСТЪР. Той има триизмерни координати.   -  person Nordic Mainframe    schedule 11.02.2011
comment
@Elian: Има ли разлика, когато формата е 3D? @Michal: не е толкова просто; min/max XYZ ви дава hitbox; куб, в който ще се побере формата. Точката може да е извън формата, но в кутията за удари.   -  person KeithS    schedule 11.02.2011
comment
А, не бях виждал този въпрос, когато търсих. Благодаря за това..   -  person Matt    schedule 11.02.2011
comment
local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly   -  person Jaroslav Jandek    schedule 11.02.2011

Отговори (2)


arrow_upward
16
arrow_downward

Използвайте точка, за която знаете, че е извън формата, и проверете дали линията от тази точка до дадената точка минава през повърхностите на фигурата. Ако минава през нечетен брой повърхности, дадената точка е вътре във формата.

person Guffa    schedule 10.02.2011
comment
Отличен отговор, но всъщност да направите това е по-трудно, отколкото звучи. - person KeithS; 11.02.2011
comment
Току-що създадохте 3 нови въпроса за Мат. - person Amy West; 11.02.2011
comment
Това е методът, който ще използвам. Благодаря за помощта - person Matt; 11.02.2011
comment
По-добър начин да направите това може да бъде да започнете с точката, която искате да тествате, и да продължите да увеличавате стойността й x в цикъл. Всеки път, когато текущата ви позиция е над координатна стена, добавете 1 към вашия брояч (освен ако предишната точка също е била стена). Ако вашият брояч е нечетен, след като сте повторили своя хоризонтален прозорец, първоначалната точка е била във формата. Ако броячът е четен, първоначалната точка е била извън формата. Можете да направите този метод по-бърз, като използвате QuadTree, за да проверите дали дадена координата е стена. Можете също така да направите бърза проверка на правоъгълник в началото, за да отхвърлите далечни точки. - person John Kurlak; 04.06.2012
comment
Това е 2D решение, но заключението все още е валидно. Изберете посока и тръгнете, ако има нечетен брой пресечки, вие сте вътре във формата, в противен случай не сте. Просто трябва да промените операторите if и циклите по подходящ начин, за да отчетете 3 измерения, а не 2. - person Nevyn; 09.03.2013
comment
@Nevyn: Не, както беше посочено, това е решение, което е агностик на измеренията. Решението работи също толкова добре с две или три измерения, или дори четири или четиринадесет. Действителното изпълнение става по-сложно с повече измерения, разбира се. - person Guffa; 09.03.2013

arrow_upward
2
arrow_downward

В допълнение към отговора на Guffa, по-трудно е, отколкото звучи, да се определи дали линия пресича повърхност. Ето математиката зад това: Пресечна точка на прави и равнини. Трябва да вземете този основен алгоритъм (който включва намиране на нормалата на всяка повърхност към тази точка, след това определяне на ъгъла между нормалата и линията, за да образувате правоъгълен триъгълник, на който намирате третата точка; библиотеката Media3D на WPF има функции за точки и вектори, които правят всичко това по-лесно), след това определете дали точката, която сте намерили, пресича равнината на повърхността в границите на тази повърхност. За да направите ТОВА, можете да вземете всяка 2D проекция на тази повърхност, която има площ > 0, и да извършите теста „точка в многоъгълник“, който е 2D версията на теста „точка в многостен“, който се опитвате да направите.

Късмет.

person KeithS    schedule 10.02.2011