BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  polygon manipulation questions          BorlandTalk.com Forum Index -> Delphi Graphics View previous topic :: View next topic   Author Message Jon Lennart Aasenden Guest Posted: Fri Aug 05, 2005 12:28 pm    Post subject: polygon manipulation questions Here goes: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. I guess "projection" is a keyword here :) 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Could anyone help me out with this? Kind regards Jon Lennart Aasenden Back to top Avatar Zondertau Guest Posted: Fri Aug 05, 2005 12:43 pm    Post subject: Re: polygon manipulation questions Quote: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. I guess "projection" is a keyword here :) 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Could anyone help me out with this? In both cases first determine the center of the operation. The center is arbitrary and could be considered a parameter to these operations. What you say is indeed a possible choice, but not the only one. Every point is a valid center for these operations, enven those outdside the polygon can make sense as center in some situations. Consider a point (X, Y) in a polygon. We're performing a scale with factor F and a rotation over an angle Alpha (in radians!) using (XC, YC) as the center point. The result of mapping this point is then (XR, YR) with: XR := F * (Cos(Alpha) * (X - XC) - Sin(Alpha) * (Y - YC)) + XC; YR := F * (Sin(Alpha) * (X - XC) + Cos(Alpha) * (Y - YC)) + YC; This code is untested and optimizable (for example by using SinCos). This basically comes down to the following: - Translate the point so, that the center is (0, 0) (because it is the only point which is invariant under rotation and scaling) - Apply a rotation and scaling matrix to the point - Translate again to restore the original center Back to top Nils Haeck Guest Posted: Fri Aug 05, 2005 12:43 pm    Post subject: Re: polygon manipulation questions Hi JL, I don't see exactly what you mean by "6 pixels larger in diameter". Normally you can either scale a polygon from one specific point (e.g. center of gravity). But this does not mean that the result will be visually pleasing. Another way is to outline (also called) stroke the polygon. Quote: 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Check out affine transforms. You can create an affine transformation as a matrix of the form [A B C] [D E F] For rotation, use A = cos(Rot), B = sin(Rot), C=1 D = -sin(Rot), E=Cos(Rot) F = 1 Multiply each point like this: Xnew = A * Xold + B * Yold + C Ynew = D * Xold + E * Yold + F "Rot" above is the rotation angle (in radians!) You can use the same transform also for translation, scaling, shearing, etc. Btw check out the Graphics32 lib, it has a superb TPolygon32 class which implements a lot of this stuff. Nils "Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> wrote Quote: Here goes: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. I guess "projection" is a keyword here :) 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Could anyone help me out with this? Kind regards Jon Lennart Aasenden Back to top somebody Guest Posted: Fri Aug 05, 2005 8:14 pm    Post subject: Re: polygon manipulation questions "Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> wrote Quote: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? I think what you are looking for is under the term "polygon/polyline offset" in CAD-speak, but other disciplines have their own terminology. It can get quite involved to do properly, unless your polygon is convex. You'll see lots of references to Voronoi diagrams, medial axis and/or straight skeleton... etc. Quote: My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. No, they won't - they will look rather bad, in all but some singular cases. Again, if your polygon is convex, and you decide on what you want to do with reflex corners, I can post an outline. Otherwise, GIYF and let me know if you come across any Pascal source, especially using FP and handling islands. Robust polygon offset code in Pascal doesn't exist in cyberspace, AFAIK. Back to top Arash Partow Guest Posted: Fri Aug 05, 2005 11:35 pm    Post subject: Re: polygon manipulation questions Hi Jon, 1.) Find the bounding circle (ie: center and radius) 2.) Translate polygon relative from bounding circle center to origin 3.) Scale points in x and y directions by desired amount 4.) Translate polygon back to previously calculated bounding center Note: instead of the bounding circle's center you can use the polygon centroid. There is a computational geometry library written in object pascal called FastGEO which has all the above described routines url: http://fastgeo.partow.net Arash Partow __________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net "Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> wrote: Quote: Here goes: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. I guess "projection" is a keyword here :) 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Could anyone help me out with this? Kind regards Jon Lennart Aasenden Back to top somebody Guest Posted: Sat Aug 06, 2005 1:14 am    Post subject: Re: polygon manipulation questions "Arash Partow" <arashp (AT) hotmail (DOT) com> wrote Quote: 1.) Find the bounding circle (ie: center and radius) 2.) Translate polygon relative from bounding circle center to origin 3.) Scale points in x and y directions by desired amount 4.) Translate polygon back to previously calculated bounding center Note: instead of the bounding circle's center you can use the polygon centroid. There is a computational geometry library written in object pascal called FastGEO which has all the above described routines url: http://fastgeo.partow.net Just had a quick look at your code: "CircularHull" is either not what it says or doesn't do what it's supposed to do. Back to top Arash Partow Guest Posted: Sat Aug 06, 2005 7:28 am    Post subject: Re: polygon manipulation questions Hi Somebody, The circular hull presented isn't the most optimal circular hull aka not the perfect bounding circle. But is enough for most things. The only problem I see was that the final result of the radius was being passed back as the square of the radius, hence: Result.Radius := LLen; Now becomes: Result.Radius := sqrt(LLen); If you find anymore please don't hesitate to inform me... Arash Partow ________________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net "somebody" <somebody (AT) somewhere (DOT) com> wrote: Quote: "Arash Partow" <arashp (AT) hotmail (DOT) com> wrote 1.) Find the bounding circle (ie: center and radius) 2.) Translate polygon relative from bounding circle center to origin 3.) Scale points in x and y directions by desired amount 4.) Translate polygon back to previously calculated bounding center Note: instead of the bounding circle's center you can use the polygon centroid. There is a computational geometry library written in object pascal called FastGEO which has all the above described routines url: http://fastgeo.partow.net Just had a quick look at your code: "CircularHull" is either not what it says or doesn't do what it's supposed to do. Back to top somebody Guest Posted: Sun Aug 07, 2005 11:18 pm    Post subject: Re: polygon manipulation questions "Arash Partow" <arashp (AT) hotmail (DOT) com> wrote Quote: The circular hull presented isn't the most optimal circular hull aka not the perfect bounding circle. But is enough for most things. True, but not making it clear that it's not the circular hull but a circular hull can create hard to resolve problems for unsuspecting users downstream. Common convention with hulls and BBs is that we always speak of "the", not "a". A function called AABB, fi, is expected to return the AABB, not an AABB. Likewise for convex hull, or else you can return an AABB as a convex hull and be done with it. Back to top Arash Partow Guest Posted: Mon Aug 08, 2005 1:58 am    Post subject: Re: polygon manipulation questions Hi Somebody, An AABB is the axis aligned bounding box (a rectangle) in the case of AABB functions available in FastGEO, as far as I can tell they produce the correct AABB for the primitives passed into them. That said in the situation of scaling polygons, the bounding circle helps in 2 ways: 1.) It provides a center point to translate in a neat'n'tidy manner to origin and back from origin the vertices of the polygon. 2.) The radius length obtained from the bounding circle can be used in order to provide the user of a possible "scale polygon" routine the ability to enter in their scaling amount as a percentage of the polygon's current bounding circle. which in some cases may seem a bit more logical than some arbitrary scaling factor. ie: I want to scale 1.5 times I would say a positive scaling of 150% or I want to half I would say scale %50 etc... well the terms bounding circle and circular hull are used interchangeably. they basically mean the same thing, unlike convex hull etc... The point here is the "efficiency" of the bounding circle. The intuitive algorithm can calculate the exact bounding circle in O(n^2), the approximation can do it in O(n) but will not always return the same result but is usually within ~99."(5+(n/2))9"s of the optimal result. The really nice yet not intuitive algorithm "bounding ball" finds the optimal in o(nlogn) for 2D, its highly complicated and requires a priority container which sort of takes it out of the simple one-liner league of routines of FastGEO. I think the current circular hull routine is pretty intuitive. Its based on the fact that there is no other kind of mean for a given set of points in 2D which will have a distance to the true bounding circle center than the one provided by polygon centroid. using that center, we just scan the points modifying the radius if a point is found to be further "out" than the current calculated radius. at the end your guaranteed that at least one point will be on the circumference of the bounding circle and all the other points will be in the ball. The area of the ball will obviously not be optimal, but its good enough for most things that would involve a bounding circle which have a bias towards speed rather than precise accuracy. Arash Partow ________________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net "somebody" <somebody (AT) somewhere (DOT) com> wrote: Quote: "Arash Partow" <arashp (AT) hotmail (DOT) com> wrote The circular hull presented isn't the most optimal circular hull aka not the perfect bounding circle. But is enough for most things. True, but not making it clear that it's not the circular hull but a circular hull can create hard to resolve problems for unsuspecting users downstream. Common convention with hulls and BBs is that we always speak of "the", not "a". A function called AABB, fi, is expected to return the AABB, not an AABB. Likewise for convex hull, or else you can return an AABB as a convex hull and be done with it. Back to top Arash Partow Guest Posted: Mon Aug 08, 2005 3:37 am    Post subject: Re: polygon manipulation questions From the previous post: Its based on the fact that there is no other kind of mean for a given set of points in 2D which will have a distance to the true bounding circle center than the one provided by polygon centroid. Should have been: Its based on the fact that there is no other kind of mean for a given set of points in 2D which will have a distance less to the true bounding circle center than the one provided by polygon centroid (in general). Arash Partow ________________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net Back to top Daniel Guest Posted: Mon Aug 08, 2005 7:19 am    Post subject: Re: polygon manipulation questions As I wonder, you want to get polygons buffer. I asked this before, and I do it well now in my project. What I did is ... Step1: make all segments in polygon shift out or in by a distance. Step2: Connect all segments with Arcs ( acute angle in polygon) or get insertion points ( obtuse angle). Step3: Erase inserted odd polygons and get a new one. Regards, Daniel "Jon Lennart Aasenden" <post_nospam_nojunk (AT) jurasoft (DOT) no> ¼¶¼g©ó¶l¥ó·s»D:42f35b73 (AT) newsgroups (DOT) borland.com... Quote: Here goes: All questions refer to pascal only code, no winapi or QT calls. Does anyone have code to do the following: 1. Inflate a polygon? Lets say i have a polygon that spans an area of 320x320 pixels, and i want to make it 6 pixels in diameter larger? My initial idea would be to sort the points to get the maxwidth/height values or the area, divide this by 2 and i have the center. But how to use that information to expand or contract each point? Perhaps i could divide the area into 8 zones (directly above, directly below, right, left, topleft etc..) and add or subtract to each point, but i doubt that would be very accurate.. I guess "projection" is a keyword here :) 2. Rotating a polygon? I have a polygon of X points, and would like to rotate it 45 degrees? Could anyone help me out with this? Kind regards Jon Lennart Aasenden 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.