Computational Geometry

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 


Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa 365 Puzzlers  Calendar 2017

Mensa 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

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.

bulletIntersect

Intersect takes two line definitions as input and returns true if the two line intersect.  An additional parameter, PointOnBorder, is set to true if the lines touch but do not cross, .   This is a faster, but harder-to-understand  version of the IntersectingLines routine presented earlier.

 

bulletPointPerpendicularLine

Given a line and a point not on the line, construct a line through the point and perpendicular to the line.   The trick here is to determine the slope of the given line,  m, and take advantage of the fact that the slope of  a perpendicular line is -1/m.  Given the equations of the two lines we can solve them as decribed in Intersecting Lines to determine the point of intersection.    

 

bulletAngledLineFromLine

Given a line, a point on (or near) the line, an angle, and a length, construct a line through the point with the specified length and at the specified angle from the given line.   The simplest approach to this problem is to draw a line segment of a given length, L, at a given angle, A, through a given point, P.   The new point is defined by P2.X=P1.X+Lcos(A) and P2.Y=P1.Y+Lsin(A).  The only problem remaining is to determine angle A.  The required angle equals the angle of the given line from the horizon   plus the given angle, and the angle of the given line from the horizon is given by the inverse tangent of its slope.  Here's the bit of Delphi code that does that for line L1 with endpoints p1 and p2:
bullet

 With L1 do
begin
     if p1.x<>p2.x then {slope is not infinite}
     theta:=arctan2((p1.y-p2.y),(p2.x-p1.x))
    else {vertical line}  if p2.y>p1.y then theta:=pi/2 else theta:=-pi/2; 
end;

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.     

Polygon inflated by 12 pixels

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:

bulletDegToRad and RadToDegree conversions.
bulletGetTheta to return the angle from point 1 to point 2 of a lassd line.
bulletTranslateLeftTo to translate (move) a line to a new starting point location.
bulletRotateRightTo to rotate the end point of a  line about the start point to a new given angle.
bulletCircleCircleIntersect function to return the intersection points of 2 passed circles.
bulletPointCircleTangentLines function calculates the two tangent lines to a given circle from a given exterior point.
bulletCircleCircleExtTangentLines function calculates the 2 exterior tangent lines, if they exist, between 2 given circles.

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.

    

1. Circle-circle intersection

2. Point-Circle Tangents (using circle-midpoint circle intersection)

3. Exterior Circle-Circle Tangents (using point-circle tangents)

 

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!

 
bulletClick here to download the executable Geometry4 demo program.
bulletClick here to download source code (requires a one time download of DFFFLIBV09 or later)
bulletClick here to download current Library version  DFFLibV15

 

bulletDownload Lazarus Source
bulletDownload current DFF Lazarus Library Source(DFFLazLib01)

 

 

Created: October 24, 2002

Modified: July 29, 2017

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.