Unit uLazQuadTreeGeometry

Description

uLazQuadTreeGeometry.pas

Geometrical functions for the use with (but not limited to) the lazQuadTree

License: The same modified LGPL as the Free Pascal RTL See the file COPYING.modifiedLGPL for more details

Author: Ekkehard Domning (ekkehard@domning.eu)

Overview

The unit operates with 2D-objects on flat and flatened surfaces. The used coordinate system for all functions is orthogonal. The basic functions assume a default direction of the increment in the X- and Y-Axis. The progressive function gives the opportunity to change this. There are three word models to use: flat, cylindrical and toroidal. The latter two allows a seamless wrap-around from the right to the left edges (and vice versa), toroidal also on the top and bottom edges.

The most specific functions are the point in rectangle, point in polygon and the calculation of the kind of overlapping of two rectangles, including the covered areas.

Details are explained in the comments above the specific declarations.

Overview

Classes, Interfaces, Objects and Records

Name Description
Class ELQTGException  
Record TLQTPoint  
Record TLQTRect  

Functions and Procedures

procedure RemoveNotAreaRectanglesFromArray(var ARectangles: TLQTRectArray);
procedure TransformPoint(const AInX, AInY : Double; const ASourceWorld, ATargetWorld : TLQTRect; out AOutX, AOutY : Double);
procedure NormatePointToWorld(const AInX, AInY : Double; const AWorldRect: TLQTRect; const AWorldModel : TLQTWorldModel; out AOutX, AOutY : Double);
function LineIntersection( const AP0X, AP0Y, AP1X, AP1Y, AP2X, AP2Y, AP3X, AP3Y : Double; out AIX, AIY : Double) : Boolean;
function LineIntersection( const AP0, AP1, AP2, AP3 : TLQTPoint; out AI : TLQTPoint) : Boolean;
function LineRectInteraction( const ALeft, ATop, ARight, ABottom : Double; const AP0X, AP0Y, AP1X, AP1Y : Double) : TLineRectInteraction;
function LineRectInteraction( const ARect : TLQTRect; const AP0, AP1 : TLQTPoint) : TLineRectInteraction;
function LineRectInteractionSimple( const ALeft, ATop, ARight, ABottom : Double; const AP0X, AP0Y, AP1X, AP1Y : Double ) : TLineRectInteraction;
function PolylineRectangleInterAction( const ALeft, ATop, ARight, ABottom : Double; const APolyline; const APolylinePointCount: Integer; const AFirstValueIsY: Boolean = False; const AXAxisLeftPlus : Boolean = False; const AYAxisUpPlus : Boolean = False; const AFullInsideCheck : Boolean = False ) : TLineRectInteraction;
function RectanglesOverlap(const ALeft, ATop, ARight, ABottom : Double; const BLeft, BTop, BRight, BBottom : Double; out CLeft, CTop, CRight, CBottom : Double; const AWorldRect : TLQTRect ) : TLQTRectOverlapKind;
function RectanglesOverlap(const ARect, BRect : TLQTRect; out CRect : TLQTRect; const AWorldRect : TLQTRect ) : TLQTRectOverlapKind;
procedure NormalizeRectangle(const ARect: TLQTRect; const AWorldRect: TLQTRect; const AWorldModel: TLQTWorldModel; out ANormalizedRectangles : TLQTRectArray; out ANormalizedWorldRect : TLQTRect );
procedure UnNormalizeRectangles(const ANormalizedRectangles : TLQTRectArray; const AUnNormalizedWorldRect: TLQTRect; const AUnNormalizedWorldModel: TLQTWorldModel; out AUnNormalizedRectangles : TLQTRectArray );
function RectanglesOverlap(const ARect, BRect : TLQTRect; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; out CRectangles : TLQTRectArray ) : Boolean;
function RectanglesOverlapEx(const ARect, BRect : TLQTRect; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; out CRectangles : TLQTRectArray ) : TLQTRectOverlapKind;
function PointInRectangle(const ARect: TLQTRect; const APoint : TLQTPoint; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel) : Boolean;

Types

TLineRectInteraction = (...);
TLQTPointArr = array of TLQTPoint;
TLQTDynDoubleArr = array of Double;
TLQTWorldModel = (...);
TLQTRectArray = array of TLQTRect;
TLQTRectOverlapKind = (...);

Constants

LQTWorldModelString : array[TLQTWorldModel ] of String = ('Flat', 'Cylindrical', 'Toroidal');
LineRectInteractionString : array[TLineRectInteraction] of String = ('Outside','Inside','Intersecting');
LQTRectEmpty : TLQTRect = (Left: 0.0; Top : 0.0; Right : 0.0; Bottom : 0.0);
LQTRectInfinite : TLQTRect = ( Left: NegInfinity; Top : NegInfinity; Right : Infinity; Bottom : Infinity);
LQTRectMinValue = -(MaxDouble/2.0);
LQTRectMaxValue = LQTRectMinValue+MaxDouble;
LQTRectMaximum : TLQTRect = ( Left: LQTRectMinValue; Top : LQTRectMinValue; Right : LQTRectMaxValue; Bottom : LQTRectMaxValue);
RectOverlapKindString : array[TLQTRectOverlapKind] of String = ( 'None', 'Partly', 'Inside', 'Equal', 'Full');

Description

Functions and Procedures

procedure RemoveNotAreaRectanglesFromArray(var ARectangles: TLQTRectArray);

procedure RemoveNotAreaRectanglesFromArray will remove rectangles from the passed array, if the area is zero.

procedure TransformPoint(const AInX, AInY : Double; const ASourceWorld, ATargetWorld : TLQTRect; out AOutX, AOutY : Double);

procedure TransformPoint transforms the location of a point in one world to the corresponding location in the other world. Parameters : Inputs AInX, AInY the coordinates in the source world ASourceWorld, ATargetWorld the extension of the two worlds Outputs AOutX, AOutY the coordinates in the target world Remarks : If both worlds are equal the input is copied to the output without any further processing. If not equal the following processing is performed: - If at least one two worlds is empy an exception is thrown. - If one of the worlds in infinite, while the other is not an exception is thrown. Care must be taken if points from a complex world (toroidal, cylindric) transformed into a simpler world (flat). Creating gemometric objects (Rectangles, Polygons) from those transformed points may change the layout dramaticaly.

procedure NormatePointToWorld(const AInX, AInY : Double; const AWorldRect: TLQTRect; const AWorldModel : TLQTWorldModel; out AOutX, AOutY : Double);

procedure NormatePointToWorld will force the point to be valid in the given World. Parameters Inputs AInX, AInY the coordinates to be normated AWorldRect: The rectangle which describes the extensions of the world. AWorldModel : The world model (flat, cylindrical or toroidal) to be used. Outputs AOutX, AOutY the coordinates in the target world Remarks The passed world must be valid. The signs of the axes of the world are used. The right and bottom values of the rectangle equal to the correspondent of the world, are treated as valid in the meaning, that a rectangle may have the same size as the world. But if the values are bigger than this assumption is not longer used! Caution: if AWorldRect is not valid, an exception is thrown.

function LineIntersection( const AP0X, AP0Y, AP1X, AP1Y, AP2X, AP2Y, AP3X, AP3Y : Double; out AIX, AIY : Double) : Boolean;

function LineIntersection checks wether two lines intersects. Parameter: AP0X, AP0Y, AP1X, AP1Y, AP2X, AP2Y, AP3X, AP3Y The 4 points forming the two lines AIX, AIY the coords of the intersection (if found) Result: True if the lines intersect, otherwise False. Source: https://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect

function LineIntersection( const AP0, AP1, AP2, AP3 : TLQTPoint; out AI : TLQTPoint) : Boolean;
 
function LineRectInteraction( const ALeft, ATop, ARight, ABottom : Double; const AP0X, AP0Y, AP1X, AP1Y : Double) : TLineRectInteraction;

function LineRectIntersection will test whether a line intersects or overlap with a rectangle. The rectangle is seen as a solid block and the right and bottom coord is *not* included in rectangles area. Thus if the rectangle is (0,0,100,100) a line (100,-1,100,101) which is overlaying the right border of the rectangle will tested as false. But a line (0,-1,0,101) which is overlaying to the left side is tested as true.

Parameters ALeft, ATop, ARight, ABottom: The coords of the two points forming the rectangle. AP0X, AP0Y, AP1X, AP1Y: The coords forming the two points of the line. Result: One of the TLineRectInteractio values (lriOutSide, lriInside, lriIntersecting) Remark: The used Coordinatesystem is Right bigger Than Left and Bottom bigger than Top! CAUTION: If the line is part of a polygon, the function may may give a false positive result if the right / bottom side of the polygon is touching the left / top side of the rectangle, since the function has no knowledge about the orientation of the segment. The Code is complexer/larger than the function LineRectInteractionSimple, but the performance is 50% faster.

function LineRectInteraction( const ARect : TLQTRect; const AP0, AP1 : TLQTPoint) : TLineRectInteraction;
 
function LineRectInteractionSimple( const ALeft, ATop, ARight, ABottom : Double; const AP0X, AP0Y, AP1X, AP1Y : Double ) : TLineRectInteraction;

function LineRectIntersectionSimple is given for curiosity only. It will test whether a line intersects or overlap with a rectangle. Parameters ALeft, ATop, ARight, ABottom: The coords of the two points forming the rectangle. AP0X, AP0Y, AP1X, AP1Y: The coords forming the two points of the line. Result: One of the TLineRectInteractio values (lriOutSide, lriInside, lriIntersecting) Remark: The used Coordinatesystem is Right bigger Than Left and Bottom bigger than Top! CAUTION: The right and bottom border of the rectangle is treated to be part of the rectangle! REMARK: The Code is simpler/smaller than the function LineRectInteraction, but the performance is 35% slower.

function PolylineRectangleInterAction( const ALeft, ATop, ARight, ABottom : Double; const APolyline; const APolylinePointCount: Integer; const AFirstValueIsY: Boolean = False; const AXAxisLeftPlus : Boolean = False; const AYAxisUpPlus : Boolean = False; const AFullInsideCheck : Boolean = False ) : TLineRectInteraction;

function PolylineRectangleInterAction will test whether the rectangle and polygon intersects or overlap The function work on regular infinite planes. The sign of X and Y-Axis could be changed Parameters ALeft, ATop, ARight, ABottom: The coords of the two points forming the rectangle. APolyline: vertex points of a polyline or a polygon with V[n]=V[0]. The Polyline is defined by pairs of Double values. The method of passing an untyped reference allows the usage of several datatype like packed records etc. A dynamic Array is passed by referencing the first item The last point of the Polygon must be identical to the first point, to close the polygon. Self-Overlapping of the polygon is *not* allowed APolylinePointCount: The Number of points in the polyline = half the number of doubles passed in APolygon. AFirstValueIsY: If True, the first double value in APolygon is the Y-Value of the coordinate. If False, the first value is the X-Value (default). AXAxisLeftPlus : If True the values of X increasing when going direction left. If False, they increase to the right (default) AYAxisUpPlus : If True the values of Y increasing when going in direction top. If false they decreases (default). AFullInsideCheck: If True the the Result lriInside is valid for the full polygon. In other words, if the Polygon is completely inside the rectangle If False, the Result lriInside might be valid only for the first linesegment and an intersecting may occour later, but is not checked. Result: One of the TLineRectInteractio values (lriOutside, lriInside, lriIntersecting) The meaning is as follows lriOutside : All parts of the polygon are outside of the rectangle lriInside : If AFullInsideCheck is False (default): At least one part of the polygon is located in the rectangle. If AFullInsideCheck is True: All Parts of the polygon are inside the rectangle. lriIntersecting : The polygon intersects with the rectangle (thus, some parts are inside, others outside the rectangle). Remark: To reduce the computation load, the function should only be called, if the bounding rectangle of the Polygon is overlapping the test rectangle. This test is not performed by the function to avoid code duplication.

function RectanglesOverlap(const ALeft, ATop, ARight, ABottom : Double; const BLeft, BTop, BRight, BBottom : Double; out CLeft, CTop, CRight, CBottom : Double; const AWorldRect : TLQTRect ) : TLQTRectOverlapKind;

function RectanglesOverlap checks whether two rectangles are overlapping and if so which are the common part. Caution: works only for flat (nonwrapping) rectangles parameters ALeft, ATop, ARight, ABottom : The Rectangle A BLeft, BTop, BRight, BBottom : The Rectangle B variable CLeft, CTop, CRight, CBottom : The overlapping Rectangle return value: True if the rectangles overlapping (and the CLeft ...CBottom values are valid) False if the rectangle are not overlapping. Remarks: If parts of the right side of one of the rectangle are identical to parts the left side or top side and bottom side, the rectangles are *not* overlapping!

function RectanglesOverlap(const ARect, BRect : TLQTRect; out CRect : TLQTRect; const AWorldRect : TLQTRect ) : TLQTRectOverlapKind;

function RectanglesOverlap checks whether two rectangles are overlapping and if so which are the common part. Caution: works only for flat (nonwrapping) rectangles parameters ARect : The Rectangle A BRect : The Rectangle B outout CRect : The overlapping Rectangle return value: True if the rectangles overlapping (and the CRect is valid) False if the rectangle are not overlapping. Remarks: If parts of the right side of one of the rectangle are identical to parts the left side or top side and bottom side, the rectangles are *not* overlapping!

procedure NormalizeRectangle(const ARect: TLQTRect; const AWorldRect: TLQTRect; const AWorldModel: TLQTWorldModel; out ANormalizedRectangles : TLQTRectArray; out ANormalizedWorldRect : TLQTRect );

procedure NormalizeRectangle normalize the passed Rectangle and World rectangle. Parameters Input parameter ARect: The rectangle to be normalized AWorldModel: The world model, flat, cylindric or toroidial AWorldRect: The rectangle with the world borders Output parameters ANormalizedRectangles: An array containing the normalized rectangle(s) ANormalizedWorldRect: The normalized world rectangle Remarks The normalized rectangle has smaller values for top and left and bigger for right and bottom. The world rectangle defines the world, but also the sign of the X- and Y-Axis. The normalization will - ensure that the sign of the X- and Y-Axis is positive, in the meaning of Increasing values while travel to the right and to the bottom - adjust the sign of the borders in coordination with the world rectangle - if nesesarry split the rectangle to fit into the worlds border without overlapping If the world model ist flat, no splitting will occour. If the world model is cylindrical, a split into two rectangles may occour If the world model is toroidial, a split into two or four rectangles may occour

procedure UnNormalizeRectangles(const ANormalizedRectangles : TLQTRectArray; const AUnNormalizedWorldRect: TLQTRect; const AUnNormalizedWorldModel: TLQTWorldModel; out AUnNormalizedRectangles : TLQTRectArray );

procedure UnNormalizeRectangles invertes the process of normalization of the rectangles Parameters Input ANormalizedRectangles: An array containing normalized rectangles (all rectangles must be inside or equal to the normalized word-borders). AUnNormalizedWorldModel: The world model to transformed to AUnNormalizedWorldRect: The borders of the world to be transformed in Output AUnNormalizedRectangles : An array of the transformed, unnormalized rectangles Remarks The input are assumed to be in a flat world with rectangles left, top values smaller than right, bottom values. And also all values laying within the world borders. In a flat world model the signs of the rectangles are adjusted and the result placed into the output rectangle array In a cylindrical world model the input rectangles are merged, if they share the same top and bottom values and having the same values for the left and right edges, vice versa. Additionally the left and right border of the world are treated as identical, thus rectangle who share the east-west-border are combined as well. In a toroidial world model additional to the cylidrical world the top and bottom values of the rectangles are also merged, if fit. This may collapse up to four rectangles in on single bigger rectangle.

function RectanglesOverlap(const ARect, BRect : TLQTRect; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; out CRectangles : TLQTRectArray ) : Boolean;
 
function RectanglesOverlapEx(const ARect, BRect : TLQTRect; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel; out CRectangles : TLQTRectArray ) : TLQTRectOverlapKind;

function RectanglesOverlapEx checks whether two rectangles are overlapping and if so, what kind of overlapping is found and which areas are shared between the two rectangles. The function works on all world models (flat, cylindrical and toroidal) and on all axis orientations. parameters Input ARect, BRect the two rectangles which may overlapping AWorldModel the world model (flat, cylindrical and toroidal) AWorldRect the world definition used for the determination of the axis orientation Output CRectangles an array of rectangles containing the common/shared areas in the orientation of the given world. The array will has always one of the follwing length 0: No overlapping area 1: One overlapping area (all world models) 2: Two overlapping areas (cylindrical and toroidal worlds) 4: Four overlapping areas (toroidal worlds) Remark: The returned areas in the cylindrical and toroidal worlds may wrap around the worlds border. Return value is the TLQTRectOverlapKind type.

function PointInRectangle(const ARect: TLQTRect; const APoint : TLQTPoint; const AWorldRect : TLQTRect; const AWorldModel : TLQTWorldModel) : Boolean;

function PointInRectangle tests whether a point is inside a rectangle on a curved world. It decapsulate the function ARect.ContainsPoint(....). See details there.

Types

TLineRectInteraction = (...);

TLineRectInteraction defines the three possible interactions between a line and a rectangle.

Values
  • lriOutside
  • lriInside: The line is located outside the rectangle
  • lriIntersecting: The line is located inside the rectangle
TLQTPointArr = array of TLQTPoint;

TLQTPointArr contains 0 to some TLQTPoint records

TLQTDynDoubleArr = array of Double;

TLQTDynDoubleArr an ordinary dynamic double array, to allow out parameters to set the length within the called function

TLQTWorldModel = (...);

TLQTWorldModel

This unit covers three world models: flat, cylindrical and toroidal.

*On a flat world* - Rectangles could be up to infinity size. Using infinity is not recommended, due to several limitations. - Two rectangles may form only one single overlapping area. - A straight line is defined by it's two points, a Polyline is performed by a an ordered list of points, a Polygon is closed by the last point of a line having the same value as the first.

*On a cylindrical world* - Rectangles could be up to infinity size. Using infinity is not recommended, due to several limitations. - Rectangles could pass the right and left border of the world, by extent on the opposite part of the world. Since (as defined) the upper-left corner is always above and left from the bottom-right corner, a rectangle (following the world map example as above) with left = +5 and right = -3 is valid. Starting with X = 5 and increasing the value to move right(!) until X = 179, we will soon pass 180 = -180 and traveling further until the right(!) border at -3. - Two rectangles may form one or two overlapping areas. Under which circumstances a secondary overlapping area exists? Example: The Y-Axis could be ignored in the explanation, assuming that the height of the two rectangles are same as the world heights.

The rectangle A covers: Dublin (X: -7) to Hamburg (X: +10). The rectangle B covers: Amsterdam (X: +5) to Liverpool (X: -3). Be aware that the rectangle B is very long and reaches around the east-west-border. So there exists one overlapping area from Dublin (X: -7) to Liverpool (X: -3) and a second one from Amsterdam (X: +5) to Hamburg (X: +10). Dublin Liverp. Amstd. Hamburg -180 =========== -7 == -3 ===== +5 ==== +10 ================ 180 Rect A AAAAAAAAAAAAAAAAAAAAAAAAAA Rect B BBBBBBBBBBBBBBBBBBBBBBBBB BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB Overlap 1 11111111111 Overlap 2 22222222 - A straight line is defined by it's two points, a Polygon is performed by a an ordered list of points. WARNING: In contrast to rectangles, lines between two points can not pass the world's border! It is not possible to create straight lines (and subsequently polygons) passing the worlds border like the rectangles above. This is caused by the fact, that e.g. a line between New York and Sydney could be drawn in two ways, one across Africa, one across the Pacific Ocean. While on a single line it would be possible to define that the first point should be always left of the second point, this approach failed in polygons. To avoid any ambiguity, line points are only allowed to be within range of the world's extension. Thus polygons are also not allowed to pass the east-west-border. Forming the rectangle B in the example above by a polygon, it is necesarry to define two separate polygons.

*On a toroid-World* the capabilities of the cylindrical-World are extent in the Y-axis (Top to Bottom). - Rectangles could pass the top and bottom border of the world, by extent on the opposite part of the world. - Two rectangles may form up to four overlapping rectangles Example:

Diagram 1 shows Rectangle A: (Left, Top, Right, Bottom) 2,2, 7,7 Diagram 2 shows Rectangle B: (Left, Top, Right, Bottom) 6,6, 3,3

0123456789 0123456789 0123456789 0123456789 +———-+ +———-+ +———-+ +———-+ 0 | | 0 |BBB BBBB| 0 |... ....| 0 | | 1 | | 1 |BBB BBBB| 1 |... ....| 1 | | 2 | AAAAA | 2 |BBB BBBB| 2 |..1***2...| 2 | 1 2 | 3 | AAAAA | 3 | | 3 | ***** | 3 | | 4 | AAAAA | 4 | | 4 | ***** | 4 | | 5 | AAAAA | 5 | | 5 | ***** | 5 | | 6 | AAAAA | 6 |BBB BBBB| 6 |..3***4...| 6 | 3 4 | 7 | AAAAA | 7 |BBB BBBB| 7 |... ....| 7 | | 8 | | 8 |BBB BBBB| 8 |... ....| 8 | | 9 | | 9 |BBB BBBB| 9 |... ....| 9 | | +———-+ +———-+ +———-+ +———-+ Diagram 1 Diagram 2 Diagram 3 Diagram 4

Be aware that going from the upper-left corner (6,6) of the rectangle B to the lower right corner, after reaching the point 9,9 (the lower right corner of the world), the next more right an more downward(!) point is the overflow to 0,0, which is the upper left corner of the world! Diagram 3 shows all rectangles (A = '*', B = '.' and the four overlapping rectangles '1' to '4'. Diagram 4 only the overlapping rectangles '1' to '4'.

- The limitations of Lines and Polygons are the same as for the cylindrical world!

Values
  • lqtwmFlat
  • lqtwmCylindrical
  • lqtwmToroidal
TLQTRectArray = array of TLQTRect;

TLQTRectArray an open array of TLQTRect

TLQTRectOverlapKind = (...);

TLazQuadNodeAreaOverlap kind of overlapping between two rectangles A and B Overlapping: None Partly Inside Equal Fully +–+ +—+ +—–+ +—+ +—–+ |A | | A+–+ |A+-+ | | a | |B... | +–+ +–+ +- |B | | |B| | | B | | .a. | |B | +–+ | +-+ | +—+ | ... | +–+ +—- + +—- +

Values
  • qroNone
  • qroPartly: no overlap
  • qroInside: the A is partly overlayed by B
  • qroEqual: the B is located inside A
  • qroFull: the A and B are equal

Constants

LQTWorldModelString : array[TLQTWorldModel ] of String = ('Flat', 'Cylindrical', 'Toroidal');
 
LineRectInteractionString : array[TLineRectInteraction] of String = ('Outside','Inside','Intersecting');
 
LQTRectEmpty : TLQTRect = (Left: 0.0; Top : 0.0; Right : 0.0; Bottom : 0.0);

Definition of an empty rectangle

LQTRectInfinite : TLQTRect = ( Left: NegInfinity; Top : NegInfinity; Right : Infinity; Bottom : Infinity);

LQTRectInfinite of an infinite rectangle

LQTRectMinValue = -(MaxDouble/2.0);

LQTRectMinValue the absolute minimum value that could be used within this unit

LQTRectMaxValue = LQTRectMinValue+MaxDouble;

LQTRectMaxValue the absolute maximum value that could be used within this unit

LQTRectMaximum : TLQTRect = ( Left: LQTRectMinValue; Top : LQTRectMinValue; Right : LQTRectMaxValue; Bottom : LQTRectMaxValue);

LQTRectInfinite of an maximum rectangle

RectOverlapKindString : array[TLQTRectOverlapKind] of String = ( 'None', 'Partly', 'Inside', 'Equal', 'Full');
 

Generated by PasDoc 0.16.0.