FastGEO Frequently Asked Questions (FAQ)

 www.partow.net  .: Home :.   .: Links :.   .: Search :.   .: Contact :. 



[01] What is FastGEO?

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.


[02] Why is it coded in Delphi?

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.


[03] What does FastGEO mean?

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.


[04] What is the history and main motivation behind the development of FastGEO?

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.


[05] How robust are the computations in FastGEO?

In short this is a very difficult question to answer, because robustness as seen from different people has differing degrees


[06] What things effect the robustness of computations in computational geometry?

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.


[07] What kind of inputs do the routines in FastGEO accept?

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.


[08] Why isn't there a strict error checking policy in FastGEO's routines?

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;


[09] Using FastGEO how do I determine if two segments are intersecting each other in 2D?

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;


[10] Using FastGEO how do I clip a segment against a triangle, rectangle, quadix or circle?

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;


[11] Using FastGEO how do I calculate the Torricelli point of a triangle?

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;


[12] Using FastGEO how does one calculate the Incenter of a triangle in 2D?

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.

FastGEO FAQ Last updated 01/01/2005




© Arash Partow. All Rights Reserved.