[Home] [Puzzles & Projects] [Delphi Techniques] [Math Topics] [Library] [Utilities]
Here are three functions that come in handy when working with geometrical figures.
All three use a TLine type defined as a record containing two endpoints P1 and P2.
Addendum June 11, 2004:
Point In Polygon
Given an arbitrary polygon and a point, determine if the point is inside or outside of the polygon. (The red point in the image at left is outside of the polygon.)
The algorithm extends a line from the point to "infinity: and counts how many times it intersects the polygon. If odd, the point is internal; if even, the point is external to the polygon. There are a few messy details here in detecting cases where the point is on an edge or vertex of the polygon or when the extension line passes through a vertex.
Addendum October 27,2005: I finally came across an application that required several of the subroutines described above. As a result, the routines have been moved to a separate unit in version 4 (or later) of our common library file (DFFLibV04).
I also discovered that the Intersect function described above, returns incorrect results under some conditions. I've replaced it with another version (LinesIntersect), which seems to be more bulletproof but does not have the PointOnBorder feature. Intersect will return when I find that elusive bug.
Addendum January 14, 2007: Three new routines were added to the UGeometry unit today and Version 3 of the Geometry test program illustrates their use. The routines, PolygonArea, InflatePolygon, and PolygonClockwise help to "inflate" (or deflate) a given polygon by given amount. The value is the distance which the edges are to be moved while retaining their slope. In order to decide which direction to move each edge, we need to know whether the polygon was built in a clockwise or counterclockwise direction. A common algorithm for calculating the area of a general polygon happens to produce a value which is negative if the direction were clockwise and positive otherwise. So PolygonArea is called mainly to determine which direction to shift the edges, and the area is provided as a "freebie" side effect.
Two bugs were corrected in UGeometry also. The Intersect bug described previously has been corrected (intersection points which fell exactly on the other line were not identified as such when the 2nd line ended on the 1st line). And in the AngledLineFromLine procedure, right and left side directions were reversed when the line was vertical.
The updated UGeometry is located in DFFLibV09 (or later) versions of our library file. For this release only, in order to avoid downloading the entire library for this one changed unit, UGeometry is also included in the source code download for the Geometry test program.
Addendum December 19,2008: Here are several more extensions to the UGeometry unit and the Version 4 of the Geometry test program. The additions are most related to circles and computing tangents in preparation for some upcoming projects that will need that sort of stuff.
New functions are:
The Geometry4 test program contains 4 new pages, one to test line translate rotate and one for each of the 3 circle operation functions. These latter 3 also present brief descriptions of the algorithms used.
Addendum March 11,2010: A small bug was reported and fixed in the Geometry4 test program today; the "Draw point perpendicular to line" demo page (PerpSheet) did not allow the initial line to be drawn due to a rookie coding error. In the mouse move procedure, the statement: if (activepage=PerpSheet) or (activepage=AngleSheet) and (dragval=1) then begin needed an extra set of parentheses to look like this: if ((activepage=PerpSheet) or (activepage=AngleSheet)) and (dragval=1) then begin
This is the coding equivalent of writing the algebra expression A + B * C when you meant (A + B) * C. Results in both cases are wrong!
Copyright © 2000-2013, Gary Darby
All rights reserved.