BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  How test if a Bezier spline intersects with a rectangle?          BorlandTalk.com Forum Index -> Delphi Graphics View previous topic :: View next topic   Author Message Edwin Guest Posted: Sat Apr 14, 2007 5:02 pm    Post subject: How test if a Bezier spline intersects with a rectangle? Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin Back to top David Ninnes Guest Posted: Sun Apr 15, 2007 6:00 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? "Edwin" <nospam (AT) domain (DOT) com> wrote in message news:4620c283 (AT) newsgroups (DOT) borland.com... Quote: Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin Not as far as I know, There is no analytic solution to the intersection of a line (and a rect) with a Bezier. There are a couple of functions that could help you:- Draw the bezier to a path Get the boundsrect of the path (GetBounds) - not sure how fast this would be with a curve, haven't tried it See if the boundrect and your rect intersects, if not you're done If the start and end points are inside and outside the rectangle then it does intersect and you're done otherwise it gets harder Method 1) The most exact way I can think of off hand is use the flatten method to turn the curve into a sequence of polylines. then iterate over the polylines to see if any intersect your rect, if so then you have a candidate for intersection, repeat this at finer resolution for each candidate line to see if it actually does intersect. To test for intersection you'd have to fatten each line a bit because the approximation to the curve will miss any grazing intersections. Method 2) Or you could just draw the bezier and then scan around the borders of the rectangle, to see if any of the pixels have changed near the border of the rectangle. Method 3) Draw the bezier to a path, then iterate over each point using getpathdata to see if they're in you're rectangle. 2 and 3 are probably easiest but depending on your application the slowest. Method 1 is probably the fastest, but the hardest. There's probably a better way. hth, Dave Back to top Nils Haeck Guest Posted: Mon Apr 16, 2007 12:36 am    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Test 1: If the convex polygon around the control points doesn't lie within the rectangle, then also the bezier doesn't lie within it. Test 2: If one of the end points (not the control points) lies within the rectangle, then the bezier curve lies within it, obviously. You can use this strategy to make a quick intersection test. If the convex polygon *does* intersect with the rectangle (test 1), and no endpoint lies within the rectangle (test 2), then you must investigate further. The easiest is to subdivide the bezier curve into two sub bezier curves, and repeat above test iteratively. You can google for geometric subdivision methods of bezier curves. I have written code for all this (also line-bezier curve intersection, distance of a point to a bezier curve, and a lot of other useful stuff), but, unlike the idea above, I can't give that away for free to you. Nils "Edwin" <nospam (AT) domain (DOT) com> schreef in bericht news:4620c283 (AT) newsgroups (DOT) borland.com... Quote: Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin Back to top Angus Johnson Guest Posted: Mon Apr 16, 2007 4:36 am    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Quote: How test if a Bezier spline intersects with a rectangle? 1. "Flatten" the bezier into an array of points using the FlattenPath() & GetPath() APIs. 2. Enumerate the array of points testing each with PtInRect(). If all return true or all return false then the bezier doesn't intersect the rectangle. *You can see some code that uses FlattenPath() & GetPath() here: http://angusj.com/delphitips/beziertext.php Back to top Edwin Guest Posted: Mon Apr 16, 2007 4:49 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? David Ninnes wrote: Quote: "Edwin" <nospam (AT) domain (DOT) com> wrote in message news:4620c283 (AT) newsgroups (DOT) borland.com... Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin Not as far as I know, There is no analytic solution to the intersection of a line (and a rect) with a Bezier. There are a couple of functions that could help you:- Draw the bezier to a path Get the boundsrect of the path (GetBounds) - not sure how fast this would be with a curve, haven't tried it See if the boundrect and your rect intersects, if not you're done If the start and end points are inside and outside the rectangle then it does intersect and you're done otherwise it gets harder Method 1) The most exact way I can think of off hand is use the flatten method to turn the curve into a sequence of polylines. then iterate over the polylines to see if any intersect your rect, if so then you have a candidate for intersection, repeat this at finer resolution for each candidate line to see if it actually does intersect. To test for intersection you'd have to fatten each line a bit because the approximation to the curve will miss any grazing intersections. Method 2) Or you could just draw the bezier and then scan around the borders of the rectangle, to see if any of the pixels have changed near the border of the rectangle. Method 3) Draw the bezier to a path, then iterate over each point using getpathdata to see if they're in you're rectangle. 2 and 3 are probably easiest but depending on your application the slowest. Method 1 is probably the fastest, but the hardest. There's probably a better way. hth, Dave Thanks Dave, Finally I solved this problem with the help of the Graphics32 Extension called g32_interface.pas, the algorithm is similar to Method 1 you provided. Back to top Edwin Guest Posted: Mon Apr 16, 2007 4:49 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Nils Haeck wrote: Quote: Test 1: If the convex polygon around the control points doesn't lie within the rectangle, then also the bezier doesn't lie within it. Test 2: If one of the end points (not the control points) lies within the rectangle, then the bezier curve lies within it, obviously. You can use this strategy to make a quick intersection test. If the convex polygon *does* intersect with the rectangle (test 1), and no endpoint lies within the rectangle (test 2), then you must investigate further. The easiest is to subdivide the bezier curve into two sub bezier curves, and repeat above test iteratively. You can google for geometric subdivision methods of bezier curves. I have written code for all this (also line-bezier curve intersection, distance of a point to a bezier curve, and a lot of other useful stuff), but, unlike the idea above, I can't give that away for free to you. Nils "Edwin" <nospam (AT) domain (DOT) com> schreef in bericht news:4620c283 (AT) newsgroups (DOT) borland.com... Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin thanks Nils, have your drawing engine released? Back to top Edwin Guest Posted: Mon Apr 16, 2007 4:50 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Nils Haeck wrote: Quote: Test 1: If the convex polygon around the control points doesn't lie within the rectangle, then also the bezier doesn't lie within it. Test 2: If one of the end points (not the control points) lies within the rectangle, then the bezier curve lies within it, obviously. You can use this strategy to make a quick intersection test. If the convex polygon *does* intersect with the rectangle (test 1), and no endpoint lies within the rectangle (test 2), then you must investigate further. The easiest is to subdivide the bezier curve into two sub bezier curves, and repeat above test iteratively. You can google for geometric subdivision methods of bezier curves. I have written code for all this (also line-bezier curve intersection, distance of a point to a bezier curve, and a lot of other useful stuff), but, unlike the idea above, I can't give that away for free to you. Nils "Edwin" <nospam (AT) domain (DOT) com> schreef in bericht news:4620c283 (AT) newsgroups (DOT) borland.com... Dear all, How test if a Bezier spline intersects with a rectangle? Dose GDI+ have any function can do this for me, or any tips? Many thanks. Edwin thanks Nils, is your drawing engine released? Back to top Edwin Guest Posted: Mon Apr 16, 2007 4:50 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Angus Johnson wrote: Quote: How test if a Bezier spline intersects with a rectangle? 1. "Flatten" the bezier into an array of points using the FlattenPath() & GetPath() APIs. 2. Enumerate the array of points testing each with PtInRect(). If all return true or all return false then the bezier doesn't intersect the rectangle. *You can see some code that uses FlattenPath() & GetPath() here: http://angusj.com/delphitips/beziertext.php Thanks Angus Johnson, Finally I solved this problem with the help of the Graphics32 Extension called g32_interface.pas, the algorithm is similar to what you describe. thanks. Back to top Edwin Guest Posted: Mon Apr 16, 2007 4:51 pm    Post subject: Re: How test if a Bezier spline intersects with a rectangle? Angus Johnson wrote: Quote: How test if a Bezier spline intersects with a rectangle? 1. "Flatten" the bezier into an array of points using the FlattenPath() & GetPath() APIs. 2. Enumerate the array of points testing each with PtInRect(). If all return true or all return false then the bezier doesn't intersect the rectangle. *You can see some code that uses FlattenPath() & GetPath() here: http://angusj.com/delphitips/beziertext.php Thanks Angus Johnson, Finally I solved this problem with the help of the Graphics32 Extension called g32_interface.pas, the algorithm is similar to what you describe. thanks. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Graphics All times are GMT Page 1 of 1   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.