Re: [Flashcoders] efficient line segment intersection algorithm?
I think HitTest only works with the bounding box of the MovieClip. So it's not appropriate for what you're doing. Try this Metanet Tutorial: Beyond HitTest() http://www.harveycartel.org/metanet/tutorials.html Collision Detection in Flash. cheers, JulianG Millie Niss wrote: It occurred to me that possibly hitTest doesn't work to check whether a point intersects with a clip that has strokes but no fills (ie my edges)... Does hitTest use the pixels of strokes or does it only use the insides of fills as the area it checks the test point against? ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] efficient line segment intersection algorithm?
Hi I test myself with only lines in the two movieClips, hitTest works fine without fills... David Buff - Original Message - From: Millie Niss [EMAIL PROTECTED] To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com Sent: Thursday, November 09, 2006 4:01 AM Subject: [Flashcoders] efficient line segment intersection algorithm? As part of an app I'm writing, I need users to be able to manipulate a drawing of a graph: Specifically, I have a bunch of circles (nodes) connected to each other by line segments (edges). Users can drag the nodes around within a fixed area (this part works), but I need to stop them from making the edges intersect each other (except where they meet at the nodes). I tried to do this using MovieClip.hitTest (each edge is its own MovieClip, and I know the coordinates of all the nodes) but it didn't work. I am sure there is a bug in my code, which I need to find. Even if I fix it, however, the stupid algorithm that goes through every node and checks if it hits any edge in the obvious (2 nested for loops) way is horribly inefficient -- I probably need to do the math myself rather than relying on hitTest. The number of nodes is user-configurable so even if I get the stupid algorithm to work on my baby test case, I am worried that it won't scale. It occurred to me that possibly hitTest doesn't work to check whether a point intersects with a clip that has strokes but no fills (ie my edges)... Does hitTest use the pixels of strokes or does it only use the insides of fills as the area it checks the test point against? Millie Niss [EMAIL PROTECTED] http://www.sporkworld.org ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] efficient line segment intersection algorithm?
hitTest has a version that tests a point against the actual shape of a MovieClip. The other varaiation tests two MovieClips, but only compares their bounding boxes, not the actual shapes. I found a useful segment intersection algorithm in the book _Computational Geometry: Algorithms and Applications_, by Mark de Berg http://www.amazon.com/Computational-Geometry-Algorithms-Applications-Second/dp/3540656200/ref=pd_ys_qtk_rvi_img/102-1020427-4119337 which I bought (will be shipped tomorrow). The algorithm is quite understandable and efficient. It does use binary trees, so I have to code a binary tree class before I can implement the algorithm. I guess that is good practice for me because I just started doing AS 2.0 OOP stuff. (I did C++ in the Bad Old Days, so I am not an OO neophyte, but the bad old days were a long time ago. I don't even think design patterns were invented. If they were, they were not taught at my university.) ObGripe: I was impatient so I also bought the online electronic edition ($10 after buying the book at regular price) from Amazon and was able to get the algorithm I needed (good explanation with background, discussion of time/space issues, and pseudocode; no sample source but that's the way I prefer it). I was annoyed to discover that one has to print the pages in the e-book one at a time (and they come up slowly -- on DSL -- and print slowly...) rather than by specifying a range of pages. The ad about the online book said it was printable, and it never occurred to me that the printing would be so difficult and slow. Also, the pubisher has a limit on how many pages you are allowed to print (not specified either, so I guess it will just stop printing when I reach the limit). Aaagh. Millie Niss [EMAIL PROTECTED] http://www.sporkworld.org - Original Message - From: JulianG [EMAIL PROTECTED] To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com Sent: Thursday, November 09, 2006 8:00 AM Subject: Re: [Flashcoders] efficient line segment intersection algorithm? I think HitTest only works with the bounding box of the MovieClip. So it's not appropriate for what you're doing. Try this Metanet Tutorial: Beyond HitTest() http://www.harveycartel.org/metanet/tutorials.html Collision Detection in Flash. cheers, JulianG Millie Niss wrote: It occurred to me that possibly hitTest doesn't work to check whether a point intersects with a clip that has strokes but no fills (ie my edges)... Does hitTest use the pixels of strokes or does it only use the insides of fills as the area it checks the test point against? ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] efficient line segment intersection algorithm?
Millie Niss wrote: I found a useful segment intersection algorithm in the book _Computational Geometry: Algorithms and Applications_, by Mark de Berg http://www.amazon.com/Computational-Geometry-Algorithms-Applications-Second/dp/3540656200/ref=pd_ys_qtk_rvi_img/102-1020427-4119337 The algorithm is quite understandable and efficient. It does use binary trees, so I have to code a binary tree class before I can implement the algorithm. Haven't read it, but this book has a good reputation. If memory serves, it's a sweep line algorithm which uses a priority queue -- you can get an AS 2 version from Arul's blog -- http://www.shockwave-india.com/blog/actionscript2/?asfile=PriorityQueue.as . good luck and enjoy the book! - jim -- Singularity Flash :: Flex :: Math :: www.2112fx.com/blog TechNotes Computational Geometry :: www.2112fx.com/technotes.html ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] efficient line segment intersection algorithm?
Hi, If the movie clips are circular, you may be faster using your own maths... Hit test will see if a point is in a clip, but you only want to see if 2 circles are touching. Jobe Makar's book Macromedia Flash MX Game Design Demystified gives this solution - called Circle to Circle detection. To summarise: It you have circle_1 and circle_2 distance from circle_1 to circle_2 centre is found with Pythagoras. Math.sqrt( x * x + y * y) If distance = (circle_1.radius - circle_2.radius) (the circles are touching / overlapping) Hope this helps. Glen ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
Re: [Flashcoders] efficient line segment intersection algorithm?
I want to see if a circle hits a network of line segments. Alternatively, I need to test for self-intersections in the nework of line segments. The problem is to allow the user to drag nodes of the network but not let them make the lines cross or drag nodes on top of each other. The circle is small enough (it's just a small circle on top of the node (places where segements meet) that it would be enough to test if the center hits a line segment, which is why I initially tried to do it with hitTest. I think the sweep algorithm is what I need. The book does seem to be good at least in that one chapter. Thanks to the person who recommended an AS 2.0 implementation of the priority queue. I just looked and it is a better implementation than I would have done. I am lazy and would have a tendency to implement only the methods I need in a stupid inefficient manner, thus going against the whole modularity/reusability goal of OO. (On the other hand, that is what Extreme Programming gurus advocate -- they say most code never gets reused and that you should code only to specs you actually need for the specific problem you are solving. In my case, the network of line segments has to be pretty small because it will be drawn and manipulated by the user on the screen.) Are there comprehensive graphics libraries for AS 2.0.? I am interested only in 2d, but it would be cool to have a lib that does image processing stuff along with 2d shape stuff. Of course 3d would be cool also, but my guess is that fake 3d in Flash would be too slow to make it worthwhile to have a really serious 3d library ala OpenGL. (Such a thing wasn't even conceivable prior to Flash 8 because you need the bitmap classes to do shading and lighting, let alone texture mapping. BTW (off-topic): What is the standard comprehensive computer graphics text these days? When I was in grad school, it was Foley-Van Dam (and some of my friends worked for Andy Van Dam so they considered no other book) but I have heard it is quite out-of-date. Millie Niss [EMAIL PROTECTED] http://www.sporkworld.org - Original Message - From: Glen Pike [EMAIL PROTECTED] To: Flashcoders mailing list flashcoders@chattyfig.figleaf.com Sent: Thursday, November 09, 2006 3:57 PM Subject: Re: [Flashcoders] efficient line segment intersection algorithm? Hi, If the movie clips are circular, you may be faster using your own maths... Hit test will see if a point is in a clip, but you only want to see if 2 circles are touching. Jobe Makar's book Macromedia Flash MX Game Design Demystified gives this solution - called Circle to Circle detection. To summarise: It you have circle_1 and circle_2 distance from circle_1 to circle_2 centre is found with Pythagoras. Math.sqrt( x * x + y * y) If distance = (circle_1.radius - circle_2.radius) (the circles are touching / overlapping) Hope this helps. Glen ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
[Flashcoders] efficient line segment intersection algorithm?
As part of an app I'm writing, I need users to be able to manipulate a drawing of a graph: Specifically, I have a bunch of circles (nodes) connected to each other by line segments (edges). Users can drag the nodes around within a fixed area (this part works), but I need to stop them from making the edges intersect each other (except where they meet at the nodes). I tried to do this using MovieClip.hitTest (each edge is its own MovieClip, and I know the coordinates of all the nodes) but it didn't work. I am sure there is a bug in my code, which I need to find. Even if I fix it, however, the stupid algorithm that goes through every node and checks if it hits any edge in the obvious (2 nested for loops) way is horribly inefficient -- I probably need to do the math myself rather than relying on hitTest. The number of nodes is user-configurable so even if I get the stupid algorithm to work on my baby test case, I am worried that it won't scale. It occurred to me that possibly hitTest doesn't work to check whether a point intersects with a clip that has strokes but no fills (ie my edges)... Does hitTest use the pixels of strokes or does it only use the insides of fills as the area it checks the test point against? Millie Niss [EMAIL PROTECTED] http://www.sporkworld.org ___ Flashcoders@chattyfig.figleaf.com To change your subscription options or search the archive: http://chattyfig.figleaf.com/mailman/listinfo/flashcoders Brought to you by Fig Leaf Software Premier Authorized Adobe Consulting and Training http://www.figleaf.com http://training.figleaf.com
