FArrangement2d

Arrangement2d constructs a planar arrangement of a set of 2D line segments.

Choose your operating system:

Windows

macOS

Linux

References

Module

GeometryAlgorithms

Header

/Engine/Plugins/Runtime/GeometryProcessing/Source/GeometryAlgorithms/Public/Arrangement2d.h

Include

#include "Arrangement2d.h"

Syntax

struct FArrangement2d

Remarks

Arrangement2d constructs a planar arrangement of a set of 2D line segments. When a segment is inserted, existing edges are split, and the inserted segment becomes multiple graph edges. So, the resulting FDynamicGraph2d should not have any edges that intersect.

Calculations are performed in double-precision, so there is no guarantee of correctness.

[TODO] multi-level segment has to accelerate find_intersecting_edges() [TODO] maybe smarter handling

Variables

Name Description

Public variable

*void int

 

GID

Public variable

FDynamicGraph2d

 

Graph

Graph of arrangement

Public variable

TPointHashGrid2...

 

PointHash

PointHash for vertices of graph.

Public variable

double

 

VertexSnapTol

Points within this tolerance are merged

Constructors

Name Description

Public function

FArrangement2d

(
    const FAxisAlignedBox2d& BoundsHin...
)

Public function

FArrangement2d

(
    double PointHashCellSize
)

Functions

Name Description

Public function

bool

 

AttemptTriangulate

(
    TArray< FIntVector >& Triangles,
    TArray< int32 >& SkippedEdges,
    int32 BoundaryEdgeGroupID
)

Attempts to triangulates the arrangement with a constrained delaunay triangulation

Public function

int

 

find_existing_vertex

(
    FVector2d Pt
)

Find existing vertex at point, if it exists

Public function

bool

 

find_intersecting_edges

(
    FVector2d A,
    FVector2d B,
    TArray< FIntersection >& Hits,
    double Tol
)

Find set of edges in graph that intersect with edge [A,B]

Public function

bool

 

find_intersecting_floating_vertices

(
    const FSegment2d& SegAB,
    int32 AID,
    int32 BID,
    TArray< FSegmentPoint >& Hits,
    double Tol
)

Public function

int

 

find_nearest_boundary_vertex

(
    FVector2d Pt,
    double SearchRadius,
    int IgnoreVID
)

Find nearest boundary vertex, within SearchRadius

Public function

int

 

find_nearest_vertex

(
    FVector2d Pt,
    double SearchRadius,
    int IgnoreVID
)

Find closest vertex, within SearchRadius

Public function

bool

 

HasSelfIntersections()

Check if current Graph has self-intersections; not optimized, only for debugging

Public function

bool

 

HasVertexNear

(
    FVector2d Point,
    double SearchRadius
)

Check if vertex exists in region

Public function

void

 

Insert

(
    const FSegment2d& Segment,
    int GID
)

Insert segment into the arrangement

Public function

int

 

Insert

(
    const FVector2d& Pt
)

Insert isolated point P into the arrangement

Public function

void

 

Insert

(
    const FVector2d& A,
    const FVector2d& B,
    int GID
)

Insert segment [A,B] into the arrangement

Public function Const

*void

 

Insert

(
    PolyLine2d pline,
    int GID
)

Int N = pline.VertexCount - 1; for (int i = 0; i < N; ++i) { FVector2d A = pline[i]; FVector2d B = pline[i + 1]; insert_segment(A, B, GID); }

Public function

int

 

insert_point

(
    const FVector2d& P,
    double Tol
)

Insert pt P into the arrangement, splitting existing edges as necessary

Public function

bool

 

insert_segment

(
    FVector2d A,
    FVector2d B,
    int GID,
    double Tol
)

Insert edge [A,B] into the arrangement, splitting existing edges as necessary

Public function

int32

 

InsertNewIsolatedPointUnsafe

(
    const FVector2d& Pt
)

Insert isolated point P into the arrangement when you know by construction it's not too close to any vertex or edge Much faster, but will break things if you use it to insert a point that is on top of any existing element!

Public function

FIndex2i

 

split_segment_at_t

(
    int EID,
    double T,
    double Tol
)

Insert new point into segment EID at parameter value T If T is within Tol of endpoint of segment, we use that instead.

Public function

FIndex2i

 

SplitEdgeAtPoint

(
    int EdgeID,
    FVector2d Point
)

Subdivide edge at a given position

Classes

Name

Description

Public struct

FIntersection