November 28, 2020, 02:04:47 AM
Welcome,
Guest
. Please
login
or
register
.
Did you miss your
activation email
?
1 Hour
1 Day
1 Week
1 Month
Forever
Login with username, password and session length
Home
Forum
Help
Search
Gallery
Login
Register
SyntaxBomb  Indie Coders
»
Languages & Coding
»
Blitz Code Archives
»
Algorithms
»
[bmx] Point inside convex polygon by Warpy [ 1+ years ago ]
« previous
next »
Print
Pages: [
1
]
Go Down
Author
Topic: [bmx] Point inside convex polygon by Warpy [ 1+ years ago ] (Read 614 times)
BlitzBot
Jr. Member
Posts: 1
[bmx] Point inside convex polygon by Warpy [ 1+ years ago ]
«
on:
June 29, 2017, 12:28:41 AM »
Title :
Point inside convex polygon
Author :
Warpy
Posted :
1+ years ago
Description :
Normally it's quite difficult to tell if a point is inside an arbitrary polygon. For a concave polygon, or one with holes in, the <a href="
http://www.blitzmax.com/codearcs/codearcs.php?code=2037
" target="_blank">scanning method[/url] is the way to go.
But when you've got a convex polygon, things get a lot easier! Remember that the definition of a convex polygon is "A polygon such that every line segment between two vertices of the polygon does not go exterior to the polygon (i.e., it remains inside or on the boundary of the polygon)."
We can use this fact to split a convex polygon into a fan of triangles, originating from one of its vertices. Then the point is inside the polygon if and only if it is inside one of the triangles, which is easy to check with a little bit of <a href="
http://www.blitzmax.com/codearcs/codearcs.php?code=1992
" target="_blank">maths[/url].
Remember that this only works on a *convex* polygon, not just any one, so only use it when you know you've got one, such as a <a href="
http://www.blitzmax.com/codearcs/codearcs.php?code=2050
" target="_blank">convex hull[/url].
Code :
Code: BlitzMax
'little type for keeping track of 2d points
Type
point
Field
x#,y#
Function
create:point
(
x#,y#
)
p:point=
New
point
p.x=x
p.y=y
Return
p
End
Function
End
Type
'returns True if p1 and p2 are on the same side of the line a>b
Function
sameside
(
p1x#,p1y#,p2x#,p2y#,ax#,ay#,bx#,by#
)
cp1# =
(
bxax
)
*
(
p1yay
)

(
p1xax
)
*
(
byay
)
cp2# =
(
bxax
)
*
(
p2yay
)

(
p2xax
)
*
(
byay
)
If
cp1*cp2 >=
0
Then
Return
True
End
Function
'Clever little trick for telling if a point is inside a given triangle
'If for each pair of points AB in the triangle, P is on the same side of AB as
'the other point in the triangle, then P is in the triangle.
Function
pointintriangle
(
px#,py#,ax#,ay#,bx#,by#,cx#,cy#
)
If
sameside
(
px,py,ax,ay,bx,by,cx,cy
)
And
sameside
(
px,py,bx,by,ax,ay,cx,cy
)
And
sameside
(
px,py,cx,cy,ax,ay,bx,by
)
Return
True
Else
Return
False
EndIf
End
Function
'returns True if (x,y) is inside convex polygon defined by list of points
'points must be in clockwise (or anticlockwise) order.
'won't work for just any polygon!
'Works by splitting polygon into triangles, and checking each of those
Function
pointinside
(
x# , y# , points:
tlist
)
p1:point =
Null
p2:point =
Null
For
p:point =
EachIn
points
If
p1
If
p2
If
pointintriangle
(
x , y , p1.x , p1.y , p2.x , p2.y , p.x , p.y
)
Return
True
EndIf
EndIf
p2=p
Else
p1 = p
EndIf
Next
Return
False
End
Function
Comments :
Jesse(Posted 1+ years ago)
I have been using This point in poly function:<a href="
http://www.darwin3d.com/gamedev/articles/col0199.pdf
" target="_blank">
http://www.darwin3d.com/gamedev/articles/col0199.pdf
[/url]when I get a chance I will test and compare both codes. If its significantly faster (wich I am almost shure it is) I will add it to my library. Thanks for sharing.
Warpy(Posted 1+ years ago)
As far as I can tell, that's just talking about general polygons again?
Jesse(Posted 1+ years ago)
Yes, I am not disputing that. There are three sample c programs that illustrate what is being explained. I have converted them to bmax and I am using them in my library. they work efficiently well for my purpose I am also using the npoly lib made in blitzbasic which I have adopted and modified for my personal use. I am not trying to discredit you. I think your example is a great alternative to the said code. I am not a great programmer nor am I trying to reinvent the wheel, I want some code that will prevent me from wasting hours/days by the computer trying to solve. so I leave my doors open to alternative and/or better solutions. I apreciate your sharing so that people like me can leach
. And yes I have contributed. not much of a discovery but stuff I had problems with and figured out. may be usefull for somebody. "I will not give up with out a fight!"
Warpy(Posted 1+ years ago)
Yeah of course, I just thought I was missing something simple there!
spacerat(Posted 1+ years ago)
This seems to be working fine for the concave polygon I just tested it with. Perhaps it works sometimes for concave polygons, but not reliably for all of them.
Warpy(Posted 1+ years ago)
Yep, that's true.
Logged
Print
Pages: [
1
]
Go Up
« previous
next »
SyntaxBomb  Indie Coders
»
Languages & Coding
»
Blitz Code Archives
»
Algorithms
»
[bmx] Point inside convex polygon by Warpy [ 1+ years ago ]
SimplePortal 2.3.6 © 20082014, SimplePortal