Welcome to the MacNN Forums.

Ghoser777 · Jun 6, 2001, 12:49 AM

This one is kind of stumping me. I know there's a method in NSBezierPath that lets u check if a NSBezierPath contains a NSPoint, but does anyone know an efficient way to check if two NSBezierPath's intersect? I'm not looking necessarially for code (although I won't stop you), just a good hard kick in the right direction.

Thanks,
F-bacher

parallax · Jun 6, 2001, 05:53 AM

I was looking for that too at some point, but couldn't find any info

I suppose that _if_ there's a non-approx. formula for this, it'll be in some complex (and time-consuming) form.

DaGuy · Jun 6, 2001, 08:08 AM

Warning this is not an answer. I am just curious to see why it's inefficient to use the "NSBezierPath to check for NSPoint" approach? Is it because one would end up looping through all points in both sets (one for each curve) to identify the one(s) that lie in the intersection?

Ghoser777 · Jun 6, 2001, 09:30 AM

Well considering there are infinetely many points on a line, that method isn't very efficient. I could take a sampling of points, but that just sounds like statistics again, a class I despised. I could end up missing important points, and that algorithm sounds like a b*tch to me. Hmm... I hope there is a better way...

F-bacher

DaGuy · Jun 6, 2001, 03:39 PM

If you are looking for the intersection of two straight lines, then one solution would be to reconstruct the equations y=mx+b given two points for each one of the lines. You would just need to solve a 2x2 linear system two find the intersection. No algorithm required, it's just applying the formula. I could post the details but I don't know if you want to take this route.

If on the other hand, you need to find the intersection of two curves then the solution given above may still be the best route if you can determine the equations for the curves exactly. If approximations are sufficient, then bear in mind that if you choose a small enough neighborhood around where the curves intersect, the curves look linear and all the above apply even in the case of curves.

My two cents. It's a hairy beast depending on what your paths look like. Let me know if you want me to post the y=mx+b deal.

[ 06-06-2001: Message edited by: DaGuy ]

Ghoser777 · Jun 6, 2001, 04:19 PM

I really need it for generic closed curves. What I've got are shape objects that I want to move around, but I don't want them to pass over other shape objects. Every shape is going to be defined by a simple closed curve, so I need to make sure that the interior and bounds of no two closed curves overlap. I'm a math major, so doing brute force math isn't a problem. Because my lines aren't straight lines, and I really don't want to know what the lines are (because of abstraction) when I'm checking, using slope intercept form isn't going to be particularly useful. These are the methods I have already implemented: I can find an objects NSBezierPath and if a certain point is inside the closed path or on the border. I suppose I could derive a formula to get 100 or so random NSPoints from one of the Path's and see if one of them is in the bounds of the other path, but that's not particularly accurate. Oh well...

F-bacher

DaGuy · Jun 6, 2001, 04:47 PM

Dude, that's rough...

Anyway, what if you shift to a different approach. I was just thinking about roll-overs and how do images know when the cursor intersects them?
Images can have highly irregular closed boundaries and so can the cursors.
Maybe if you look at how those things are implemented in Cocoa, you may get some other ideas. I just got my Learning Cooca so I won't be of much help. Cheers.

Ghoser777 · Jun 6, 2001, 05:00 PM

Originally posted by DaGuy:
<STRONG>Dude, that's rough...

Anyway, what if you shift to a different approach. I was just thinking about roll-overs and how do images know when the cursor intersects them?
Images can have highly irregular closed boundaries and so can the cursors.
Maybe if you look at how those things are implemented in Cocoa, you may get some other ideas. I just got my Learning Cooca so I won't be of much help. Cheers.</STRONG>

That's the easy part - I already have roll-over like stuff implemented. That was the check if NSPoint is in bounds of closed NSBezierPath method I referenced above. That's easy enough (took me a day to figure out how to do it for a rotated rectangle though), but now the trick is to be given an infinte number of NSPoints and see how many I have to check to be sufficiently sure that the two closed NSBezierPath's don't intersect.

Thanks for the ideas though,
F-bacher