FastGEO is a computational geometry library written in the object pascal language.
FastGEO contains a wide range of computational geometry algorithms and routines
for many different types of geometrical operations such as geometrical primitives
and predicates.
Using these primitives and predicates one can establish more complex computational
geometry routines such as convex hulls, triangulations and many more.
FastGEO was written using Delphi's IDE but was not written in a language called Delphi,
because no such language exists. FastGEO was written in the object pascal language because
of the serious lack in computational geometry code for the language. FastGEO is merely a
seed to hopefully a larger expanse of future developers willing to invest time and technical
ability in order to bring value to the object pascal language.
FastGEO basically stands for Fast Geometry. In short its a no frills, hassel free
implementation of real-world computational geometry using real-world coordinates
and data with a very predictable interface.
All these properties help provide the "Fast Geometry" experience which FastGEO was
intended to provide the end user.
FastGEO (version 0.0.1) was compiled for the first time on a cold winter's night
in July 1997 using the Borland Pascal 7.0 compiler. The first release contained
only about 15 routines all up. Simple point in/on rectangle routines, distance
calculations and a very buggy 2D segment intersection routine.
As time went by and requests and code snippets came in from different sources
FastGEO began to grow, and as the sun began to set upon the world of Borland
Pascal, it was decided that FastGEO be transferred to Delphi.
Function overloading, was the key to the next major step in the development of FastGEO.
The idea that a person could provide the necessary input data and request a particular
form of geometric functionality was the aim and with function overloading this was achieved
easily. With the function overloading feature that Delphi provided with its object pascal
compiler, all the most intuitive combinations of parameters for types of geometric
functionality were implemented and provided as the new interface for FastGEO, and it has
remained that way ever since.
In the development process of software intended on performing computational geometry
the following points are of great concern and must be dealt with at the earlist
possible instances during both the design and development stages:
1. Proliferation : If the input to a geometric operation has k-digit precision,
the output may require higher precision
2. Irrationality : Some operations result in coordinates that have no finite
precision (sqrt(3), pi/3 etc...)
An excerpt from the abstract of "Robustness In Geometric Computations" Christoph M. Hoffman (2001)
Geometric computation software tends to be fragile and fails occasionally.
This robustness problem is rooted in the difficulty of making unambiguous
decisions about incidence and nonincidence, fundamentally impairing
layering the geometry software reliably. Additionally, geometric operations
tend to have a large number of special and singular cases, further adding
to the difficulty of creating dependable geometric software.
The only type of input accepted by FastGEO routines are fixed precision type inputs.
FastGEO is not an algebraic system hence irrational elements which require either
inifinite precision or symbolic representations are deemed unacceptable forms of
input hence no interface is made available to support such types.
The way people use the results from computational geometry greatly varies based upon their needs.
In some situations the input data is known to be of a certain type, hence additional checking for
that particular type is not needed and would cause a great deal of inefficiency in the code.
An example of this situation is in the calculation of a circumcenter based on three unique points.
The base requirements for the routine are that the three points used as input not be collinear to each
other. The routine assumes the points passed are not collinear and completes its calculations with
that assumption in mind (there is still minor division by zero error checking done, which relates
to the points being collinear).
However in a situation where you can't be sure that the three points will be unique and will not be collinear
to each other error-checking must be done manually. The amount of error checking you do will determine how
robust your sequence of routines will be and in the end how accurate the result will be but also it will
determine the speed at which your calculation will occur. In computational theory accuracy/robustness and
speed of calculations are usually inverse proportional to each other. Below is a simple example of how to increase
the level of robustness and accuracy of the circumcenter routine:
uses FastGEO;
var
x1,y1,x2,y2,x3,y3 : Double;
CenterX : Double;
CenterY : Double;
begin
if not Collinear(x1,y1,x2,y2,x3,y3) then
begin
Circumcenter(x1,y1,x2,y2,x3,y3,CenterX,CenterY);
Writeln('The circumcenter is (x:',CenterX:5:3,' y:',CenterY:5:3,')');
end
else
Writeln('The circumcenter could not be calculated.')
end;
uses FastGEO;
var
Triangle : TTriangle2D;
Center : TPoint2D;
begin
if not IsDegenerate(Triangle) then
begin
Center := Circumcenter(Triangle);
Writeln('The circumcenter is (x:',Center.x:5:3,' y:',Center.y:5:3,')');
end
else
Writeln('The circumcenter could not be calculated.')
end;
The first thing you have to do is determine your input parameters, segments are usually defined with two
sets of coordinates A(x1,y1)B(x2,y2). FastGEO also provides a 2D and 3D segment type. The routines for
intersection can take both cartesian coordinates and TSegment2D. Below are two examples of determining
whether or not two segments intersect each other:
uses FastGEO;
var
S1x1,S1y1,S1x2,S1y2 : Double;
S2x1,S2y1,S2x2,S2y2 : Double;
begin
S1x1 := 9.464523810;
S1y1 := 11.756150790;
S1x2 := 10.401904760;
S1y2 := 11.801507940;
S2x1 := 8.663882195;
S2y1 := 17.184738960;
S2x2 := 10.299410980;
S2y2 := 11.570896920;
if Intersect(S1x1,S1y1,S1x2,S1y2,S2x1,S2y1,S2x2,S2y2) then
WriteLn('Segments Intersect!')
else
WriteLn('Segments do not intersect!');
end;
uses FastGEO;
var
Segment1 : TSegment2D;
Segment2 : TSegment2D;
begin
Segment1 := EquateSegment(9.464523810, 11.75615079, 10.40190476, 11.80150794);
Segment2 := EquateSegment(8.663882195, 17.18473896, 10.29941098, 11.57089692);
if Intersect(Segment1,Segment2) then
WriteLn('Segments Intersect!')
else
WriteLn('Segments do not intersect!');
end;
FastGEO natively supports clipping of segments against triangles, rectangles and quadii.
The input paramater types can be either cartesian coordinates or types native geometric
types such as TSegment2D, TTriangle2D and/or TRectangle.
Below are three examples of clipping a segment against a triangle, a rectangle and a quadix
respectively.
uses FastGEO;
var
Segment : TSegment2D;
ClippedSegment : TSegment2D;
Triangle : TTriangle2D;
begin
Segment := EquateSegment(120.0,80.0,430.0,300.0);
Triangle := EquateTriangle(100.0,300.0,200.0,50.0,400.0,300.0);
if Clip(Segment,Triangle,ClippedSegment) then
WriteLn('Segment has been clipped!')
else
WriteLn('Segment has NOT been clipped');
end;
uses FastGEO;
var
Segment : TSegment2D;
ClippedSegment : TSegment2D;
Rectangle : TRectangle;
begin
Segment := EquateSegment(200.0,30.0,200.0,350.0);
Rectangle := EquateRectangle(100.0,50.0,400.0,300.0);
if Clip(Segment,Rectangle,ClippedSegment) then
WriteLn('Segment has been clipped!')
else
WriteLn('Segment has NOT been clipped');
end;
uses FastGEO;
var
Segment : TSegment2D;
ClippedSegment : TSegment2D;
Quadix : TQuadix;
begin
Segment := EquateSegment(20.0,80.0,430.0,230.0);
Quadix := EquateQuadix(100.0,50.0,400.0,100.0,300.0,200.0,100.0,150.0);
if Clip(Segment,Quadix,ClippedSegment) then
WriteLn('Segment has been clipped!')
else
WriteLn('Segment has NOT been clipped');
end;
uses FastGEO;
var
Segment : TSegment2D;
ClippedSegment : TSegment2D;
Circle : TCircle;
begin
Segment := EquateSegment(20.0,80.0,430.0,230.0);
Circle := EquateCircle(225.0,155.0,100.0);
if Clip(Segment,Circle,ClippedSegment) then
WriteLn('Segment has been clipped!')
else
WriteLn('Segment has NOT been clipped');
end;
The Torricelli point of a triangle is said to exist at the intersection of the Simpson lines. If the triangle has a vertex greater than
or equal to 120 degrees, then it is said that the Torricelli point of the triangle exists at that particular vertex.
FastGEO provides a set of interfaces for calculating the Torricelli point. The interfaces accept both cartesian coordinates and the
native geometric types TTriangle2D. Below is an example demonstrating the calculation of the Torricelli point.
uses FastGEO;
var
Triangle : TTriangle2D;
Point : TPoint2D;
begin
Triangle := EquateTriangle(200.0,100.0,300.0,200.0,200.0,300.0);
TorricelliPoint(Triangle,Point);
end;
FastGEO provides a set of interfaces for calculating the incenter of a triangle in 2D. The interfaces accept a combination of
cartesian coordinates and the native geometric types TTriangle2D and TPoint2D. Below is an example demonstrating the calculation
of an incenter.
uses FastGEO;
var
Triangle : TTriangle2D;
Point : TPoint2D;
begin
Triangle := EquateTriangle(200.0,100.0,300.0,200.0,200.0,300.0);
Point := Incenter(Triangle);
end;
uses FastGEO;
var
Point : TPoint2D;
begin
Point := Incenter(EquateTriangle(200.0,100.0,300.0,200.0,200.0,300.0));
end;
If you have any questions you think are suitable for this FAQ, please feel free to contact me.
Depending on the type of question and its relevance to FastGEO it may be answered and
placed on this FAQ.
