Aleph::ShortestPathInPolygon Class Reference

Compute the shortest Euclidean path between two points inside a simple polygon. More...

#include <geom_algorithms.H>

Collaboration diagram for Aleph::ShortestPathInPolygon:

Classes
struct	ITri

Public Member Functions
DynList< Point >	operator() (const Polygon &polygon, const Point &source, const Point &target) const
	Compute the shortest path between two points in a simple polygon.

Static Private Member Functions
static size_t	find_index (const Array< Point > &pts, const Point &p)
	Match a Point from a Triangle to an index in pts (exact comparison).
static Array< ITri >	build_tris (const Array< Point > &pts, const DynList< Triangle > &tl)
	Build indexed triangulation with adjacency.
static bool	point_in_triangle (const Array< Point > &pts, const ITri &t, const Point &p)
	Point-in-triangle test.
static size_t	find_tri (const Array< Point > &pts, const Array< ITri > &tris, const Point &p)
	Find a triangle containing point p.
static Array< size_t >	find_sleeve (const Array< ITri > &tris, const size_t src, const size_t dst)
	BFS on dual graph → sleeve.
static Geom_Number	cross (const Point &a, const Point &b, const Point &c)
	Cross product (b-a) x (c-a).

Static Private Attributes
static constexpr size_t	NONE = ~static_cast<size_t>(0)

Detailed Description

Compute the shortest Euclidean path between two points inside a simple polygon.

Uses ear-cutting triangulation, BFS on the dual graph to find the triangle sleeve, and the Lee-Preparata funnel algorithm.

Complexity

• Time: O(n²) dominated by CuttingEarsTriangulation
• Space: O(n)

Example

Polygon poly;
poly.add_vertex(Point(0,0)); poly.add_vertex(Point(5,0));
poly.add_vertex(Point(5,5)); poly.add_vertex(Point(0,5));
poly.close();
ShortestPathInPolygon sp;
auto path = sp(poly, Point(1,1), Point(4,4));

Definition at line 9940 of file geom_algorithms.H.

Member Function Documentation

build_tris()

static Array< ITri > Aleph::ShortestPathInPolygon::build_tris ( const Array< Point > &  pts, const DynList< Triangle > &  tl  )

inlinestaticprivate

Build indexed triangulation with adjacency.

Definition at line 9960 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::divide_and_conquer_partition_dp(), find_index(), Aleph::Triangle::get_p1(), Aleph::Triangle::get_p2(), Aleph::Triangle::get_p3(), Aleph::HTList::Iterator::has_curr(), l1, l2, NONE, Aleph::quicksort_op(), Aleph::Array< T >::reserve(), Aleph::Array< T >::size(), and Aleph::ShortestPathInPolygon::ITri::v.

Referenced by operator()().

cross()

static Geom_Number Aleph::ShortestPathInPolygon::cross ( const Point &  a, const Point &  b, const Point &  c  )

inlinestaticprivate

Cross product (b-a) x (c-a).

Definition at line 10123 of file geom_algorithms.H.

References Aleph::Point::get_x(), and Aleph::Point::get_y().

Referenced by operator()().

find_index()

static size_t Aleph::ShortestPathInPolygon::find_index ( const Array< Point > &  pts, const Point &  p  )

inlinestaticprivate

Match a Point from a Triangle to an index in pts (exact comparison).

Definition at line 9951 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), and NONE.

Referenced by build_tris().

find_sleeve()

static Array< size_t > Aleph::ShortestPathInPolygon::find_sleeve ( const Array< ITri > &  tris, const size_t  src, const size_t  dst  )

inlinestaticprivate

BFS on dual graph → sleeve.

Definition at line 10073 of file geom_algorithms.H.

References Aleph::and, Aleph::Array< T >::append(), Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), Aleph::HTList::is_empty(), NONE, Aleph::DynList< T >::remove_first(), Aleph::Array< T >::reserve(), and Aleph::Array< T >::size().

Referenced by operator()().

find_tri()

static size_t Aleph::ShortestPathInPolygon::find_tri ( const Array< Point > &  pts, const Array< ITri > &  tris, const Point &  p  )

inlinestaticprivate

Find a triangle containing point p.

Definition at line 10063 of file geom_algorithms.H.

References Aleph::divide_and_conquer_partition_dp(), NONE, and point_in_triangle().

Referenced by operator()().

operator()()

DynList< Point > Aleph::ShortestPathInPolygon::operator() ( const Polygon &  polygon, const Point &  source, const Point &  target  ) const

inline

Compute the shortest path between two points in a simple polygon.

Parameters

polygon	A closed simple polygon.
source	Start point (inside or on the boundary).
target	End point (inside or on the boundary).

Returns

Ordered sequence of waypoints from source to target.

Definition at line 10140 of file geom_algorithms.H.

References ah_domain_error_if, Aleph::and, Aleph::Array< T >::append(), Aleph::DynList< T >::append(), build_tris(), Aleph::PointInPolygonWinding::contains(), cross(), Aleph::divide_and_conquer_partition_dp(), find_sleeve(), find_tri(), Aleph::DynList< T >::get_last(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::Dlink::Iterator::has_curr(), Aleph::Segment::intersects_properly_with(), Aleph::Polygon::is_closed(), NONE, Aleph::Polygon::size(), and Aleph::Array< T >::size().

point_in_triangle()

static bool Aleph::ShortestPathInPolygon::point_in_triangle ( const Array< Point > &  pts, const ITri &  t, const Point &  p  )

inlinestaticprivate

Point-in-triangle test.

Definition at line 10048 of file geom_algorithms.H.

References Aleph::and, Aleph::CCW, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), Aleph::orientation(), and Aleph::ShortestPathInPolygon::ITri::v.

Referenced by find_tri().

Member Data Documentation

NONE

constexpr size_t Aleph::ShortestPathInPolygon::NONE = ~static_cast<size_t>(0)

staticconstexprprivate

Definition at line 9942 of file geom_algorithms.H.

Referenced by build_tris(), find_index(), find_sleeve(), find_tri(), and operator()().

---

The documentation for this class was generated from the following file:

• geom_algorithms.H