Определите, находится ли точка (x, y, z) внутри формы, заданной массивом точек

Если у меня есть массив точек (x, y, z) и мне дана одна точка (x, y, z), какой код я использую, чтобы определить, находится ли эта точка в пределах формы, определенной массивом?

Я рисую пробел на этом...

я использую С#

ИЗМЕНИТЬ

Спасибо за ответы, ребята, из комментариев я нашел эту ссылку (http://alienryderflex.com/polygon/), что довольно хорошо объясняет процесс.

Спасибо!

К вашему сведению:

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# Point in polygon   -  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
Возможно, это не совсем точная копия другого поста, который я нашел — просто заметил, что Мэтт ищет решение в трех измерениях.   -  person Jim Lewis    schedule 11.02.2011
comment
@Джим, @Элиан. Нет, это не так. Это точка в ПОЛИЭДРОН. Он имеет трехмерные координаты.   -  person Nordic Mainframe    schedule 11.02.2011
comment
@Elian: Отличается ли это, когда форма трехмерная? @Michal: не так просто; min/max XYZ дает вам хитбокс; куб, внутри которого поместится фигура. Точка может быть вне формы, но в хитбоксе.   -  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

В дополнение к ответу Гуффы, определить, пересекает ли линия поверхность, сложнее, чем кажется. За этим стоит математика: Пересечение линий и плоскостей. Вы должны взять этот базовый алгоритм (который включает в себя нахождение нормали каждой поверхности к этой точке, затем определение угла между нормалью и линией для формирования прямоугольного треугольника, в котором вы найдете третью точку; библиотека WPF Media3D имеет функции для точек и Векторы, которые упрощают все это), затем определите, пересекает ли найденная точка плоскость поверхности в пределах границ этой поверхности. Чтобы сделать ЭТО, вы можете взять любую 2D-проекцию этой поверхности, площадь которой > 0, и выполнить тест «точка в многоугольнике», который является 2D-версией теста «точка в многограннике», который вы пытаетесь сделать.

Удачи.

person KeithS    schedule 10.02.2011