Как узнать, что точка лежит внутри замкнутого контура?

> Alexander Larionov
Не, ты посмотри лучше здесь:

Option Explicit
Const pi As Double = 3.14159265358979
Public Function PointInPpolyline(po As Variant, ent As AcadEntity) As Boolean
' by cadhelp
' Function : PointInPpolyline
' LastUpdt : Mar.1,2004.
'
'1. Input — X,Y,Z Point Array and closed LWPolyline
'2. Function create AcadRay and ask inresection between AcadRay and polyline
'3. Output TRUE if inside or FALSE if outside
Dim TempRay As AcadRay
Dim po0, inters As Variant
Dim i As Integer
ReDim po0(2) As Double
Dim Ang As Double
po0(0) = 0: po0(1) = 0: po0(2) = 0
For i = 0 To 10
Set TempRay = ThisDrawing.ModelSpace.AddRay(po, po0) ' Create new AcadRay
Ang = dtr(i * 11.5)
TempRay.Rotate po, Ang
inters = TempRay.IntersectWith(ent, acExtendNone)
TempRay.Delete 'Delete new AcadRay
If UBound(inters) < 0 Then
PointInPpolyline = False
Exit For
ElseIf (UBound(inters) + 1) / 3 Mod 2 = 0 Then
PointInPpolyline = False
Set inters = Nothing
Else
PointInPpolyline = True
Exit For
End If
Next
End Function
' Convert angle in degrees to radians
Public Function dtr(a As Double) As Double
dtr = (a / 180) * pi
End Function

~'J'~

Вычисляет верхнюю границу (индекс) массива. Фактически UBound(inters) - количество точек пересечения.

> Fatty
Данный алгоритм был предложен на форуме по ссылке данной:

> Александр Ривилис
и там был приведён частный случай:
- а если прямая совпадёт с одной из сторон?
Добавляю к нему свой случай:
- точка внутри контура, но луч прошёл через сторону и одну из вершин,
и как результат число пересечений чётное?
Я геодезист, и потому для меня данный вопрос очень актуален. По своему опыту знаю,
что на местности, в реальной ситуации могут встретиться такие варианты, до которых
при тестировании в жизни не додумаешся. Поэтому хотелось бы вариант, который изначально
учитывает все частные случаи.
В своё время я использовал свой алгоритм:
- в цикле определяем дирекционный угол на каждую из вершин, по нему расчитываем угол между смежными вершинами;
- сумма углов даст:
= 360 - точка внутри контура
= 0 - вне контура
- если один из углов =180, точка на контуре.
Дирекционный угол - если не ошибаюсь в математике называется координатный угол.
Для расчётов необходимо использовать именно данный угол, так как при обходе направление
может меняться, то угол будет либо положительный, либо отрицательный, и потому
сумма таких углов учитывает изменение направления.
В своей практике мне не удалось столкнуться с каким либо частным случаем, где бы алгоритм
прокололся, поэтому если кто найдёт его буду рад за информацию.
Но хочу предупредить, из-за большого количества тригонометрических расчётов, для учёта накапливаемой погрешности, на всякий случай полученную сумму я округлял, мне лично хватало до десятого знака.
Позже хотел использовать вариант с площадью (по указанной выше ссылке, он предлагался):
- определяем площадь полигона;
- определяем площадь полигона с добавленной определяемой точкой;
- сравниваем:
-- площадь меньше, точка внутри;
-- площадь больше, точка вне;
-- равны, на контуре.
Но от данного метода пришлось отказаться из-за сложности анализа места вставки определяемой точки.

> Alexander Larionov
>> В методе Fatty так и не понял почему там дельта 11,5 градуса ?
Угол может быть любой, результата не меняет за
исключением случаев указанных выше
Можно применить только один луч с каким-нибудь
"дурацким" углом типа 11,11111
~'J'~

> Alexander Larionov
Я же уже давал ссылки на темы, в которых эти вопросы были решены. Еще раз: http://local.wasp.uwa.edu.au/~pbourke/g … nsidepoly/. Здесь посмотри Solution 2 - это метод определения положения точки относительно полигона при помощи вычисления углов (речь идет о 2D - для 3D все точки нужно спроектировать на одну и туже плоскость).

Всё правильно, с криволинейными объектами он в принципе не может работать.
Но в геодезии и требуется работа по вершинам. Случаи с криволинейными объектами, это уже специфические работы.
На самом деле всё зависит от целей, если например вам необходим алгоритм для работы только
с выпуклыми многоугольниками, то целесообразней использовать известную строгую математическую формулу.
Что же, касается метода описанного Fatty, я просмотрел его. Лично меня он заинтерисовал.
Но, как я уже сказал выше всё зависит от целей, и даже в данном методе.
1) я не совсем понял как в нём решается работа с трёхмерными объектами, особенно если полигон
имеет в каждой вершине разные высоты?
2) данный алгоритм работает, только путём использования встроенных методов AutoCAD.
Если данный алгоритм необходимо просчитать чисто математически, без AutoCAD,
то мы сталкиваемся со сложным математическим анализом. Либо если делать просто, то он будет
работать, как и мой алгоритм, только с прямолинейными многоугольниками.
-- создаём уравнение прямой и в цикле проверяем наличие точки пересечения со сторонами полигона, учитывая частные случаи.
А вот алгоритм, для определения точки пересечения с криволинейными объектами, даже представить себе не могу.
Что касается моего алгоритма, по суммам, если интересует, то завтра скину. Просто писал его
ещё на Pascal, под обработку двоичных DXF фаайлов, поэтому надо ещё вытянуть и перевести.

По поводу ссылки данной:

> Александр Ривилис
Solution 2 - у меня серьёзные опасения, обязательно погоняю.
Старый код нашёл, но не разобрался, дело было на заре программирования.
Написал новый, вроде работает, но особо не тестировал. Поэтому осторожней.
Код нужен самому, так что буду проверять и разбираться со старым,
как разберусь выложу. Поэтому если кто найдёт сбои, напишите.
Точки должны быть введены по часовой стрелке, на другой вариант не тестировал.
Думаю данная проверка и переворот не представляют проблем. Если не ошибаюсь
на данном форуме можно найти как это сделать.
Нашёл интересный случай:
если в контуре есть наложение одной части контура на другую, тоесть
контур перекрывает сам себя, и выбранная точка окажется в перекрываемой зоне,
то сумма будет равна = 360 + (360 * Количество наложений.)

Public Pi As Variant
' Функция расчёта дирекционного угла
' Координаты в математической системе координат
Function DirAngle(ByVal XHome As Double, ByVal YHome As Double, _
                  ByVal XEnd As Double, ByVal YEnd As Double) As Double
Dim dX As Double, dY As Double
   dX = XEnd - XHome
   dY = YEnd - YHome
   If dX = 0 And dY = 0 Then
      DirAngle = 0
    ElseIf dX = 0 And dY > 0 Then DirAngle = 0
    ElseIf dX > 0 And dY > 0 Then DirAngle = Atn(dX / dY) * 180 / Pi
    ElseIf dX > 0 And dY = 0 Then DirAngle = 90
    ElseIf dX > 0 And dY < 0 Then DirAngle = Atn(dX / dY) * 180 / Pi + 180
    ElseIf dX = 0 And dY < 0 Then DirAngle = 180
    ElseIf dX < 0 And dY < 0 Then DirAngle = Atn(dX / dY) * 180 / Pi + 180
    ElseIf dX < 0 And dY = 0 Then DirAngle = 270
    Else: DirAngle = Atn(dX / dY) * 180 / Pi + 360
   End If
End Function
Sub PointToPoligon()
Dim acadObj As AcadEntity
Dim returnPoint As Variant, CoordXY As Variant
Dim XYmin As Variant, XYmax As Variant
Dim StepN As Byte
Dim I As Long
Dim DirAngleI As Double, DirAngleNext As Double
Dim Angle As Double, SumAngle As Double
' Данный способ определения Pi в VBA, в большенстве случаев тригонометрических
' расчётов, позволяет избежать ошибок округления, то есть чисел вроде:
' 359.9999999999 или 360.0000000001
   Pi = CDec("3.1415926535897932384626433832795")
' Получаем координаты определяемой точки
   returnPoint = ActiveDocument.Utility.GetPoint(, "Введите точку:")
   For Each acadObj In ActiveDocument.ModelSpace
      Select Case acadObj.ObjectName
       Case "AcDb3dPolyline", "AcDb2dPolyline", "AcDbPolyline"
         CoordXY = acadObj.Coordinates
         If acadObj.ObjectName = "AcDbPolyline" Then _
            StepN = UBound(acadObj.Coordinate(0)) + 1 _
          Else StepN = 3
' Проверяем найденную полилинию на замыкание
         If CoordXY(UBound(CoordXY) + 1 - StepN) <> CoordXY(0) Or _
           CoordXY(UBound(CoordXY) + 2 - StepN) <> CoordXY(1) Then
            If acadObj.Closed = False Then GoTo NextFor
           ReDim Preserve CoordXY(UBound(CoordXY) + StepN)
            CoordXY(UBound(CoordXY) + 1 - StepN) = CoordXY(0)
            CoordXY(UBound(CoordXY) + 2 - StepN) = CoordXY(1)
         End If
' Делаем простейшую проверку на попадание введённой точки в область,
' описанную минимальными и максимальными координатами полигона
         acadObj.GetBoundingBox XYmin, XYmax
         If returnPoint(0) < XYmin(0) Or returnPoint(0) > XYmax(0) Or _
           returnPoint(1) < XYmin(1) Or returnPoint(1) > XYmax(1) Then
            MsgBox "Точка вне контура!", vbInformation
            GoTo NextFor
         End If
' Непосредственно сам алгоритм определения положения точки
         SumAngle = 0
         For I = 0 To UBound(CoordXY) - StepN Step StepN
            DirAngleI = DirAngle(returnPoint(0), returnPoint(1), CoordXY(I), CoordXY(I + 1))
            DirAngleNext = DirAngle(returnPoint(0), returnPoint(1), CoordXY(I + StepN), CoordXY(I + 1 + StepN))
            Angle = DirAngleNext - DirAngleI
            If Angle < 0 Then Angle = Angle + 360
            If Angle > 180 Then Angle = -1 * (360 - Angle)
            If Abs(Angle) = 180 Then
               MsgBox "Точка на границе контура!", vbInformation
               GoTo NextFor
            End If
            SumAngle = Angle + SumAngle
         Next I
' Данную проверку в принципе можно записать так:
' If Abs(SumAngle) > 359 Then
' Но это надо проверять
         If Hex(Abs(SumAngle)) = Hex(360) Then
            MsgBox "Точка внутри контура!", vbInformation
          Else
            MsgBox SumAngle & " Точка вне контура!", vbInformation
         End If
      End Select
NextFor:
   Next acadObj
End Sub

Теперь о методе предложенном

> Fatty
Все алгоритмы, которые выложены на сайтах указанных в ссылках,
исключительно под прямолинейные полигоны.
Сама идея использовать встроенные средства AutoCAD давно меня интерисовала.
Если делать математический анализ на попадание точки в произвольный контур,
включая сплайны, дуги и т. д., то в AutoCAD это сделать не возможно, так как
мы не знаем уравнения по которым он строит эти кривые, а сами их получить
по данным которые нам предоставляются, вряд ли возможно. А без этих
уравнений мы не сможем найти точки пересечений. Поэтому стоит данный метод
доработать.
1) Надо добавить в начале проверку на попадание точки в область, описанную
минимальными и максимальными координатами.

acadObj.GetBoundingBox XYmin, XYmax
If returnPoint(0) < XYmin(0) Or returnPoint(0) > XYmax(0) Or _
   returnPoint(1) < XYmin(1) Or returnPoint(1) > XYmax(1) Then
   MsgBox "Точка вне контура!", vbInformation
End If

2) Указанные выше частные случаи:
- если прямая совпадёт с одной из сторон;
- точка внутри контура, но луч прошёл через сторону и одну из вершин
Решаются простой проверкой совпадения точки пересечения с вершинами,
если совпали, то вносим изменения в направление луча и повторяем проверку.
3) Выше, в описании своего кода, я привёл случай наложения полигона самого
на себя. Если точка попала в перекрывающуюся область, то число пересечений
чётное. Боюсь что здесь уже нужен серьёзный математический анализ. На сайте:
http://geometryalgorithms.com/Archive/a … m_0103.htm
помоему дан данный пример, но под прямолинейные полигоны.
4) Если мы имеем дело с криволинейными объектами, то возникает ситуация,
когда: точка внутри контура, луч пересекает сторону и идёт по касательной
к кривой. В этом случае мы получаем чётное число пересечений, но сделать
проверку на совпадение с вершинами уже не можем. И тут боюсь тупик.
Поэтому, видимо нужен другой алгоритм.
Например, который Акадовским методом определяет пересечения не с лучом,
а с прямой.
1) Строим отрезок, через точку параллельно оси абсцисс (чисто для простоты
расчётов), с выходом в обе стороны за минимальные и максимальные координаты.
2) Акадовским методом находим точки пересечения с произвольным полигоном.
3) Проверяем: если пересечений нет, или одно, или в одном направлении, то
точка вне контура.
4) Находим ближайшее от точки пересечение, в обоих направлениях,
и в результате получаем отрезок принадлежащий полигону и имеющий концы
на его границах.
5) А теперь самое главное. Как, имеея данную информацию, определить, что
отрезок принадлежит полигону?

В приведённом коде:

> Dron
Необходимо заменить строки:

            If Angle > 180 Then Angle = -1 * (360 — Angle)
            If Abs(Angle) = 180 Then
               MsgBox "Точка на границе контура!", vbInformation
               GoTo NextFor
            End If

на:

            If Hex(Abs(Angle)) = Hex(180) Then
               MsgBox "Точка на границе контура!", vbInformation
               GoTo NextFor
            End If
            If Angle > 180 Then Angle = -1 * (360 — Angle)

Иначе равенство может не работать.
Данная ошибка возникает при сравнении значений типа Double с целыми числами. Видимо в VBA какаято проблема с хвостами после округления.