View Full Version : Point inside a closed spline?
suvakas 02 February 2009, 08:36 PM Hey guys,
I've been trying to figure out how to detect if a point is inside a closed spline shape or not. I remember I did this once, but I've lost the script and I can't figure it out how I did it.
If anyone could point me to some direction, then I would be very thankful.
Suvakas


ZeBoxx2
02 February 2009, 11:54 PM
use nearestPathParam to get the distance along the spline that is closest to your world point3
use pathInterp to get the world position of that point in the spline
use pathTangent to get the direction of that point in the spline
apply a 90 degree rotation to that direction and you've got the vector that points inward ( or outward? If the latter, 90 degree ;) )
get the direction from the world position of that earlier point to your point3
use dot to check whether your point3 is along the lines of that vector (inside) or the opposite (outside)

Could also mesh your spline, move your your point3 above that mesh a bit, fire a ray down at the shape.. if it hits, it's inside.. otherwise, outside.

Probably other methods... I swear I saw an easier one somewhere, but I might be imagining things / thinking of another app (in fact, I probably am.. Rhino3D, perhaps)

Edit: At least I remember what the problem with the first method was... Glorgle.
1. sometimes the pathtangent points one way, other times it points the opposite way (thus affecting what's inside and what's outside after you rotate the vector)
2. consider the letter O. That's a closed shape, but it's not a solid shape. You'd have to bugger around with testing all of the splines, check which is inside what, etc.
meshing it and hittesting it sounds a lot more appealing already ;\
For the curious anyway...
 the below code is likely to fail (flipped results, doesn't work on nonsolid shapes)
fn BROKENisPointInsideShape thePoint theShape splineIndex = (
local pathParam = nearestPathParam theShape splineIndex thePoint
local closestPoint = pathInterp theShape splineIndex pathParam
local tangentVector = pathTangent theShape splineIndex pathParam
local perpendicularVector = tangentVector * (rotateZMatrix 90)
local thePointVector = normalize (closestPoint  thePoint)
local theDot = dot perpendicularVector thePointVector
theDot > 0.001
)
suvakas
02 February 2009, 10:29 AM
Awesome, thanks!
Yes, now i remember, that i had this inside/outside issue in the past too. So I probably used something similar as your nearestPathParam idea.
But meshing the spline and using rays  that could really work. Thanks for the tip ! I'll try both and see what works better.
Ps. I'm wondering if you can mesh a spline that is not coplanar? Will have to test this if i get near to Max.
Suvakas
ZeBoxx2
02 February 2009, 12:59 PM
you can mesh/extrude a noncoplanar splineshape, but keep in mind that you're then transforming it into the third dimension and the whole question of "is it inside?" becomes a bit iffy :)
Gravey
02 February 2009, 01:15 PM
i have an alternative solution. i found a C function on the net that determined whether a point was inside a polygon and converted it into maxscript. I used this for a script that takes the currently selected polys in an unwrap uvw mod selection and writes out a javascript file which can be used to recreate that selection in photoshop. I needed to test for donut style selections and that's where the isInsidePolygon function came in.
Now it doesn't take curves into account but it's very fast so i wrote a small function to collect the points of a spline, interpolating the curves when needed. The new point array is passes to the isInsidePolygon function which of course returns true / false. Needless to say the resulting accuracy is determined by the number of interp samples passed to the function. I find the default of 10 is fine for 99.9% of the cases that i tested.
Here's the code with an example: I converted the following function into maxscript from the C function found at:
 http://ozviz.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
fn isInsidePolygon pointArr p =
(
local cnt = 0
local n = pointArr.count
p, p1, p2 are coplanar point2s or point3s. z is irrelevant
p1 = pointArr[1]
for i = 1 to n do
(
p2 = pointArr[(mod i n)+1]  +1 since maxscript is 1 based
if p.y > amin #(p1.y,p2.y) AND p.y <= amax #(p1.y,p2.y) AND p.x <= amax #(p1.x,p2.x) AND p1.y != p2.y then
(
xinters = (p.yp1.y)*(p2.xp1.x)/(p2.yp1.y)+p1.x
if (p1.x == p2.x OR p.x <= xinters) then cnt += 1
)
p1 = p2
)
if mod cnt 2 == 0.0 then false else true
)
fn isInsideSpline spl pnt interp:10 index:1 =  arguments: SplineShape, Point, [No. interp samples for curved segments], [Spline Index]
(
if NOT isClosed spl index do return false
interp = if interp < 0 then 0.0 else interp + 1.0
cnt = numKnots spl index
interpSegs = for k = 1 to cnt where getKnotType spl index k != #corner OR getKnotType spl index ((mod k cnt)+1) != #corner collect k
pointArr = #()
for k = 1 to cnt do
(
append pointArr (getKnotPoint spl index k)
if finditem interpSegs k > 0 do
join pointArr ( for i = 1 to interp collect interpBezier3D spl index k (i/interp) )
)
isInsidePolygon pointArr pnt
)
 EXAMPLE
myShape = splineshape wirecolor:blue steps:10
addNewSpline myShape
addKnot myShape 1 #bezierCorner #curve [50,50,0] [0,10,0] [70,20,0]
addKnot myShape 1 #corner #curve [50,0,0]
addKnot myShape 1 #corner #curve [50,50,0]
addKnot myShape 1 #corner #curve [50,50,0]
addKnot myShape 1 #smooth #curve [50,50,0]
close myShape 1
updateShape myShape
myPoint1 = point pos:[15,45,0] wirecolor:red
myPoint2 = point pos:[55,25,0] wirecolor:green
myPoint3 = point pos:[0,0,0] wirecolor:green
isInsideSpline myShape myPoint1.pos
isInsideSpline myShape myPoint2.pos
isInsideSpline myShape myPoint3.pos
for i = 1 to 5 do
(
myPos = random [70,70,0] [70,70,0]
result = isInsideSpline myShape myPos
p = point pos:myPos wirecolor:(if result then green else red)
print result
)At the moment the isInsidePolygon functions expects that all the points are on a simple 2D XY plane. You could easily adapt the script by transforming the points into the spline's local space or some arbitrary plane if needed.
ZeBoxx2
02 February 2009, 01:28 PM
Unfortunately that does still leave you with the 'O' problem case. You'd have to run it three times...
1. get all points inside the outer ring > set A
2. determine that the inner ring lays within* the outer ring
3. get all points inside the inner ring > set B
4. result = set A  set B
repeat for other splines, and splines within those splines, etc.
* That's hoping there isn't any intersections between the shapes, although that messes up meshing just as well.
suvakas
02 February 2009, 04:00 PM
Thank you for the fresh idea Gravey (http://forums.cgsociety.org/member.php?u=203065), very cool. I'll keep it, if you don't mind?
I currently went with the meshing and ray shooting method.
Seems to work Ok so far. Haven't really tested it in real situations though so i don't know how fast it is. I know that shooting ray's to heavy meshes can get very slow.
eek
02 February 2009, 05:20 PM
If you already know the point is on the same 'plane' as the shape you can turn the shape into a mesh, then for each face, get the angle between the point and the faces edge verts. Add up these angles and if they equal 360 the point is in the face, if not then it isn't. You can also do secondary checks using a dot product.
for f = 1 to obj.faces.count do
(
local sum = 0
local faceEdges = (polyOp.getFaceEdges obj f)
for i = 1 to facesEdges.count do
(
local edgeVerts = polyOp.getEdgeVerts obj faceEdges[i]
local n1 = normalize (obj.verts[edgeVerts[1]].pos  point.transform.pos)
local n2 = normalize (obj.verts[edgeVerts[2]].pos  point.transform.pos)
sum += acos (dot n1 n2)
)
if sum == 360 do
(
return f
exit
)
sum = 0
)
CGTalk Moderation
02 February 2009, 05:20 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.