[Жека]

Сообщение от Jlemyp

Жека, скинь пожалуста.Мне тужно будет полезна эта функция.

У меня код под блитц макс был изначально, выложу его тоже.
В блитц 3д нельзя в функцию передать массив, поэтому я сделал в примере передачу объекта TArray, содержащего массив (статический, к сожалению).

Blitz3D:

;создадим квадратный полигон
;1----2
;|    |
;|    |
;4----3
Local poly.TArray = New TArray
poly\array[0] = 0 ;x1
poly\array[1] = 0 ;x2
poly\array[2] = 1
poly\array[3] = 0
poly\array[4] = 1
poly\array[5] = 1
poly\array[6] = 0 ;x4
poly\array[7] = 1 ;y4
poly\count = 8

DebugLog "test (-1,0): "+pointInPoly(poly, -1, 0)
DebugLog "test (0.5,0.5): "+pointInPoly(poly, 0.5, 0.5)
DebugLog "test (0.999,0.999): "+pointInPoly(poly, 0.999, 0.999)
Stop
End


;проверка находится ли точка внутри многоугольника
;многоугольник должен быть выпуклый (вогнутые можно заменить несколькими выпуклыми)
;алгоритм: делается обход отрезков многоугольника по часовой стрелке
;и проверяется - лежит ли точка "справа"(внутри) от каждого из отрезков
Function pointInPoly%(array.TArray, px#, py#)
	
	If(array = Null) Then Return False
	
	Local x1#, y1#, x2#, y2#
	Local koef#, koefA#
	Local k%, cnt% = array\count-1
	Local in = True
	Local sign, sign2
	DebugLog "px,py: "+px+","+py
	
	For k = 0 To cnt Step 2
		x1 = array\array[k]
		y1 = array\array[k+1]
		If(k + 3 < cnt)
			x2 = array\array[k + 2]
			y2 = array\array[k + 3]
		Else 		; "замыкаем" с первой точкой
			x2 = array\array[0]
			y2 = array\array[1]
		EndIf
		
		sign = Sgn(x2 - x1)
		sign2 = Sgn(px - x1)
		
		DebugLog "x1,y1: "+x1+","+y1
		DebugLog "x2,y2: "+x2+","+y2
		
		;исключаем деление на ноль
		If(sign = 0)
			x2 = x2+0.01
			sign = 1
		EndIf
		If(sign2 = 0)
			px = px+0.01
			sign2 = 1
		EndIf
		
		;коэффициенты наклона отрезков (y = k*x + b)
		koef = (y1 - y2) / (x2 - x1)
		koefA = (y1 - py) / (px - x1)
		DebugLog "koef: "+koef
		DebugLog "koefA: "+koefA
		;сама проверка: коэффициен наклона проверяемого отрезка должен быть
		;больше чем отрезка с точкой (px,py) при условии что координаты (x2,y2) и (px,py)
		;лежат по одну сторону от точки (x1,x2)
		;если по разные стороны, то наклон исходного должен быть меньше
		If((sign2 = sign And koefA > koef) Or (sign2 <> sign And koefA < koef))
			in = False
			Exit
		EndIf
		
	Next
	
	Return in
	
End Function


Type TArray
	Field array#[100]
	Field count%
End Type

BlitzMax:

Local xy#[] = [0.0,0.0, 1.0,0.0, 1.0,1.0, 0.0,1.0]

DebugLog "test (-1,0): "+pointInPoly(xy, -1, 0)
DebugLog "test (0.5,0.5): "+pointInPoly(xy, 0.5, 0.5)
DebugLog "test (0.999,0.999): "+pointInPoly(xy, 0.999, 0.999)

DebugStop
End


'проверка находится ли точка внутри многоугольника
'многоугольник должен быть выпуклый
'алгоритм: делается обход отрезков многоугольника по часовой стрелке
'и проверяется - лежит ли точка "справа"(внутри) от каждого из отрезков
Function pointInPoly%(xy:Float[], px:Float, py:Float)
	
	If(xy = Null) Then Return
	
	Local x1:Float, y1:Float, x2:Float, y2:Float
	Local koef:Float, koefA:Float
	Local k, cnt = xy.Dimensions()[0]
	Local in = True
	Local sign, sign2
	
	For k = 0 Until cnt Step 2
		x1 = xy[k]
		y1 = xy[k + 1]
		If(k + 3 < cnt)
			x2 = xy[k + 2]
			y2 = xy[k + 3]
		Else 		' "замыкаем" с первой точкой
			x2 = xy[0]
			y2 = xy[1]
		EndIf
		
		sign = Sgn(x2 - x1)
		sign2 = Sgn(px - x1)
		
		'исключаем деление на ноль
		If(sign = 0)
			x2:+0.01
			sign = 1
		EndIf
		If(sign2 = 0)
			px:+0.01
			sign2 = 1
		EndIf
		
		'коэффициенты наклона отрезков (y = k*x + b)
		koef = (y1 - y2) / (x2 - x1)
		koefA = (y1 - py) / (px - x1)
		
		'сама проверка: коэффициен наклона проверяемого отрезка должен быть
		'больше чем отрезка с точкой (px,py) при условии что координаты (x2,y2) и (px,py)
		'лежат по одну сторону от точки (x1,x2)
		'если по разные стороны, то наклон исходного должен быть меньше
		If((sign2 = sign And koefA > koef) Or (sign2 <> sign And koefA < koef))
			in = False
			Exit
		EndIf
	
	Next
	
	Return in
	
End Function

Можно в "полезные функции" скинуть, наверное.