Как узнать находится ли точка внутри фигуры?

Question

Как узнать находится ли точка внутри фигуры?

Дима Минаев Профи (713), закрыт 12 лет назад

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

Answer 1

Возмем треугольник – по Герону – площадь,
Затем вместо одной вершины, возмем данную точку
И снова площадь … если меньше .. значит внутри.
Сложную фигуру разобъем на треугольники и так же.
Это если выпуклая. Если нет … то смотреть,
Не должна принадлежать вогнутости – так же.
Это самый общий случай.

Answer 2

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

но это будет работать только для выпуклых фигур.. . кажется.. .

короче говоря, есть такая книжка как "computer graphics using OpenGL", авторы HiLL и KELLEY
вот в такой обложке:

или вот в такой:

Answer 3

Евгений Ваньков Мыслитель (8547) 12 лет назад

Лучшеб фигуру привели для примера

Answer 4

Если не понял что написал саша мошкин пиши сделаю за тебя

Answer 5

А можно сделать хитро, через WinAPI:

Declare Function CreatePolygonRgn Lib "gdi32.dll" (lpPoint As POINTAPI, ByVal nCount As Long, ByVal nPolyFillMode As Long) As Long
Declare Function PtInRegion Lib "gdi32.dll" (ByVal hrgn As Long, ByVal x As Long, ByVal y As Long) As Boolean
Type POINTAPI
x As Long
y As Long
End Type

Sub Hop()
Dim crd() As POINTAPI
Dim hrgn As Long
x = InputBox("Введите координату x точки")
y = InputBox("Введите координату y точки")
cnt = InputBox("Введите количество вершин многоугольника")
ReDim crd(1 To cnt)
For i = 1 To cnt
crd(i).x = InputBox("Введите координату x " & i & "-й вершины многоугольника")
crd(i).y = InputBox("Введите координату y " & i & "-й вершины многоугольника")
Next
hrgn = CreatePolygonRgn(crd(1), cnt, 1)
If PtInRegion(hrgn, x, y) Then
MsgBox "Точка принадлежит многоугольнику"
Else: MsgBox "Точка не принадлежит многоугольнику"
End If
End Sub

Answer 6

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