The class of polygon in 2-D. 更多...

#include <polygon2d.h>

类 apollo::common::math::Polygon2d 继承关系图:

apollo::common::math::Polygon2d 的协作图:

Public 成员函数
	Polygon2d ()=default
	Empty constructor.

	Polygon2d (const Box2d &box)
	Constructor which takes a box.

	Polygon2d (std::vector< Vec2d > points, bool check_area=true)
	Constructor which takes a vector of points as its vertices.

const std::vector< Vec2d > &	points () const
	Get the vertices of the polygon.

const std::vector< LineSegment2d > &	line_segments () const
	Get the edges of the polygon.

int	num_points () const
	Get the number of vertices of the polygon.

bool	is_convex () const
	Check if the polygon is convex.

double	area () const
	Get the area of the polygon.

double	DistanceToBoundary (const Vec2d &point) const
	Compute the distance from a point to the boundary of the polygon.

double	DistanceTo (const Vec2d &point) const
	Compute the distance from a point to the polygon.

double	DistanceTo (const LineSegment2d &line_segment) const
	Compute the distance from a line segment to the polygon.

double	DistanceTo (const Box2d &box) const
	Compute the distance from a box to the polygon.

double	DistanceTo (const Polygon2d &polygon) const
	Compute the distance from another polygon to the polygon.

double	DistanceSquareTo (const Vec2d &point) const
	Compute the square of distance from a point to the polygon.

bool	IsPointIn (const Vec2d &point) const
	Check if a point is within the polygon.

bool	IsPointOnBoundary (const Vec2d &point) const
	Check if a point is on the boundary of the polygon.

bool	Contains (const LineSegment2d &line_segment) const
	Check if the polygon contains a line segment.

bool	Contains (const Polygon2d &polygon) const
	Check if the polygon contains another polygon.

bool	HasOverlap (const LineSegment2d &line_segment) const
	Check if a line segment has overlap with this polygon.

bool	GetOverlap (const LineSegment2d &line_segment, Vec2d const first, Vec2d const last) const
	Get the overlap of a line segment and this polygon.

void	GetAllVertices (std::vector< Vec2d > *const vertices) const
	Get all vertices of the polygon

std::vector< Vec2d >	GetAllVertices () const
	Get all vertices of the polygon

std::vector< LineSegment2d >	GetAllOverlaps (const LineSegment2d &line_segment) const
	Get all overlapped line segments of a line segment and this polygon.

bool	HasOverlap (const Polygon2d &polygon) const
	Check if this polygon has overlap with another polygon.

bool	ComputeOverlap (const Polygon2d &other_polygon, Polygon2d *const overlap_polygon) const
	Compute the overlap of this polygon and the other polygon if any.

double	ComputeIoU (const Polygon2d &other_polygon) const
	Compute intersection over union ratio of this polygon and the other polygon.

AABox2d	AABoundingBox () const
	Get the axis-aligned bound box of the polygon.

Box2d	BoundingBoxWithHeading (const double heading) const
	Get the bound box according to a heading.

Box2d	MinAreaBoundingBox () const
	Get the bounding box with the minimal area.

void	ExtremePoints (const double heading, Vec2d const first, Vec2d const last) const
	Get the extreme points along a heading direction.

Polygon2d	ExpandByDistance (const double distance) const
	Expand this polygon by a distance.

Polygon2d	PolygonExpandByDistance (const double distance) const

void	CalculateVertices (const Vec2d &shift_vec)

std::string	DebugString () const
	Get a string containing essential information about the polygon for debugging purpose.

double	min_x () const

double	max_x () const

double	min_y () const

double	max_y () const

LineSegment2d	MinLineSegment () const

静态 Public 成员函数
static bool	ComputeConvexHull (const std::vector< Vec2d > &points, Polygon2d *const polygon, bool check_area=true)
	Compute the convex hull of a group of points.

Protected 成员函数
void	BuildFromPoints (bool check_area=true)

int	Next (int at) const

int	Prev (int at) const

静态 Protected 成员函数
static bool	ClipConvexHull (const LineSegment2d &line_segment, std::vector< Vec2d > *const points)

Protected 属性
std::vector< Vec2d >	points_

int	num_points_ = 0

std::vector< LineSegment2d >	line_segments_

bool	is_convex_ = false

double	area_ = 0.0

double	min_x_ = 0.0

double	max_x_ = 0.0

double	min_y_ = 0.0

double	max_y_ = 0.0

详细描述

The class of polygon in 2-D.

在文件 polygon2d.h 第 42 行定义.

构造及析构函数说明

◆ Polygon2d() [1/3]

apollo::common::math::Polygon2d::Polygon2d ( )

default

Empty constructor.

◆ Polygon2d() [2/3]

apollo::common::math::Polygon2d::Polygon2d ( const Box2d & box )

explicit

Constructor which takes a box.

参数

box	The box to construct the polygon.

在文件 polygon2d.cc 第 35 行定义.

                                     {
  box.GetAllCorners(&points_);
  BuildFromPoints();
}

◆ Polygon2d() [3/3]

apollo::common::math::Polygon2d::Polygon2d	(	std::vector< Vec2d >	points,
		bool	check_area = `true`
	)

explicit

Constructor which takes a vector of points as its vertices.

参数

points The points to construct the polygon.

在文件 polygon2d.cc 第 40 行定义.

    : points_(std::move(points)) {
  BuildFromPoints(check_area);
}

成员函数说明

◆ AABoundingBox()

AABox2d apollo::common::math::Polygon2d::AABoundingBox ( ) const

Get the axis-aligned bound box of the polygon.

返回: The axis-aligned bound box of the polygon.

在文件 polygon2d.cc 第 522 行定义.

                                       {
  return AABox2d({min_x_, min_y_}, {max_x_, max_y_});
}

◆ area()

double apollo::common::math::Polygon2d::area ( ) const

inline

Get the area of the polygon.

返回: The area of the polygon.

在文件 polygon2d.h 第 91 行定义.

91{ return area_; }

apollo::common::math::Polygon2d::area_

double area_

Definition polygon2d.h:337

◆ BoundingBoxWithHeading()

Box2d apollo::common::math::Polygon2d::BoundingBoxWithHeading ( const double heading ) const

Get the bound box according to a heading.

参数

heading The specified heading of the bounding box.

返回: The bound box according to the specified heading.

在文件 polygon2d.cc 第 526 行定义.

                                                                  {
  CHECK_GE(points_.size(), 3U);
  const Vec2d direction_vec = Vec2d::CreateUnitVec2d(heading);
  Vec2d px1;
  Vec2d px2;
  Vec2d py1;
  Vec2d py2;
  ExtremePoints(heading, &px1, &px2);
  ExtremePoints(heading - M_PI_2, &py1, &py2);
  const double x1 = px1.InnerProd(direction_vec);
  const double x2 = px2.InnerProd(direction_vec);
  const double y1 = py1.CrossProd(direction_vec);
  const double y2 = py2.CrossProd(direction_vec);
  return Box2d(
      (x1 + x2) / 2.0 * direction_vec +
          (y1 + y2) / 2.0 * Vec2d(direction_vec.y(), -direction_vec.x()),
      heading, x2 - x1, y2 - y1);
}

◆ BuildFromPoints()

void apollo::common::math::Polygon2d::BuildFromPoints ( bool check_area = true )

protected

在文件 polygon2d.cc 第 214 行定义.

                                               {
  num_points_ = static_cast<int>(points_.size());
  CHECK_GE(num_points_, 3);
 
  // Make sure the points are in ccw order.
  area_ = 0.0;
  for (int i = 1; i < num_points_; ++i) {
    area_ += CrossProd(points_[0], points_[i - 1], points_[i]);
  }
  if (area_ < 0) {
    area_ = -area_;
    std::reverse(points_.begin(), points_.end());
  }
  area_ /= 2.0;
  if (check_area) {
    CHECK_GT(area_, kMathEpsilon);
  }
 
  // Construct line_segments.
  line_segments_.reserve(num_points_);
  for (int i = 0; i < num_points_; ++i) {
    line_segments_.emplace_back(points_[i], points_[Next(i)]);
  }
 
  // Check convexity.
  is_convex_ = true;
  for (int i = 0; i < num_points_; ++i) {
    if (CrossProd(points_[Prev(i)], points_[i], points_[Next(i)]) <=
        -kMathEpsilon) {
      is_convex_ = false;
      break;
    }
  }
 
  // Compute aabox.
  min_x_ = points_[0].x();
  max_x_ = points_[0].x();
  min_y_ = points_[0].y();
  max_y_ = points_[0].y();
  for (const auto &point : points_) {
    min_x_ = std::min(min_x_, point.x());
    max_x_ = std::max(max_x_, point.x());
    min_y_ = std::min(min_y_, point.y());
    max_y_ = std::max(max_y_, point.y());
  }
}

◆ CalculateVertices()

void apollo::common::math::Polygon2d::CalculateVertices ( const Vec2d & shift_vec )

在文件 polygon2d.cc 第 672 行定义.

                                                        {
  for (size_t i = 0; i < num_points_; ++i) {
    points_[i] += shift_vec;
  }
  for (auto &point : points_) {
    max_x_ = std::fmax(point.x(), max_x_);
    min_x_ = std::fmin(point.x(), min_x_);
    max_y_ = std::fmax(point.y(), max_y_);
    min_y_ = std::fmin(point.y(), min_y_);
  }
}

◆ ClipConvexHull()

bool apollo::common::math::Polygon2d::ClipConvexHull	(	const LineSegment2d &	line_segment,
		std::vector< Vec2d > *const	points
	)

staticprotected

在文件 polygon2d.cc 第 314 行定义.

                                                               {
  if (line_segment.length() <= kMathEpsilon) {
    return true;
  }
  CHECK_NOTNULL(points);
  const size_t n = points->size();
  if (n < 3) {
    return false;
  }
  std::vector<double> prod(n);
  std::vector<int> side(n);
  for (size_t i = 0; i < n; ++i) {
    prod[i] = CrossProd(line_segment.start(), line_segment.end(), (*points)[i]);
    if (std::abs(prod[i]) <= kMathEpsilon) {
      side[i] = 0;
    } else {
      side[i] = ((prod[i] < 0) ? -1 : 1);
    }
  }
 
  std::vector<Vec2d> new_points;
  for (size_t i = 0; i < n; ++i) {
    if (side[i] >= 0) {
      new_points.push_back((*points)[i]);
    }
    const size_t j = ((i == n - 1) ? 0 : (i + 1));
    if (side[i] * side[j] < 0) {
      const double ratio = prod[j] / (prod[j] - prod[i]);
      new_points.emplace_back(
          (*points)[i].x() * ratio + (*points)[j].x() * (1.0 - ratio),
          (*points)[i].y() * ratio + (*points)[j].y() * (1.0 - ratio));
    }
  }
 
  points->swap(new_points);
  return points->size() >= 3U;
}

◆ ComputeConvexHull()

bool apollo::common::math::Polygon2d::ComputeConvexHull	(	const std::vector< Vec2d > &	points,
		Polygon2d *const	polygon,
		bool	check_area = `true`
	)

static

Compute the convex hull of a group of points.

参数

points	The target points. To compute the convex hull of them.
polygon	The convex hull of the points.

返回: If successfully compute the convex hull.

在文件 polygon2d.cc 第 261 行定义.

                                                                             {
  CHECK_NOTNULL(polygon);
  const int n = static_cast<int>(points.size());
  if (n < 3) {
    return false;
  }
  std::vector<int> sorted_indices(n);
  for (int i = 0; i < n; ++i) {
    sorted_indices[i] = i;
  }
  std::sort(sorted_indices.begin(), sorted_indices.end(),
            [&](const int idx1, const int idx2) {
              const Vec2d &pt1 = points[idx1];
              const Vec2d &pt2 = points[idx2];
              const double dx = pt1.x() - pt2.x();
              if (std::abs(dx) > kMathEpsilon) {
                return dx < 0.0;
              }
              return pt1.y() < pt2.y();
            });
  int count = 0;
  std::vector<int> results;
  results.reserve(n);
  int last_count = 1;
  for (int i = 0; i < n + n; ++i) {
    if (i == n) {
      last_count = count;
    }
    const int idx = sorted_indices[(i < n) ? i : (n + n - 1 - i)];
    const Vec2d &pt = points[idx];
    while (count > last_count &&
           CrossProd(points[results[count - 2]], points[results[count - 1]],
                     pt) <= kMathEpsilon) {
      results.pop_back();
      --count;
    }
    results.push_back(idx);
    ++count;
  }
  --count;
  if (count < 3) {
    return false;
  }
  std::vector<Vec2d> result_points;
  result_points.reserve(count);
  for (int i = 0; i < count; ++i) {
    result_points.push_back(points[results[i]]);
  }
  *polygon = Polygon2d(result_points, check_area);
  return true;
}

◆ ComputeIoU()

double apollo::common::math::Polygon2d::ComputeIoU ( const Polygon2d & other_polygon ) const

Compute intersection over union ratio of this polygon and the other polygon.

Note: this function only works for computing overlap between two convex polygons.

参数

other_polygon The target polygon. To compute its overlap with this polygon.

返回: A value between 0.0 and 1.0, meaning no intersection to fully overlaping

在文件 polygon2d.cc 第 367 行定义.

                                                                 {
  Polygon2d overlap_polygon;
  if (!ComputeOverlap(other_polygon, &overlap_polygon)) {
    return 0.0;
  }
  double intersection_area = overlap_polygon.area();
  double union_area = area_ + other_polygon.area() - overlap_polygon.area();
  return intersection_area / union_area;
}

◆ ComputeOverlap()

bool apollo::common::math::Polygon2d::ComputeOverlap	(	const Polygon2d &	other_polygon,
		Polygon2d *const	overlap_polygon
	)		const

Compute the overlap of this polygon and the other polygon if any.

Note: this function only works for computing overlap between two convex polygons.

参数

other_polygon	The target polygon. To compute its overlap with this polygon.
overlap_polygon	The overlapped polygon.
If	there is an overlapped polygon.

在文件 polygon2d.cc 第 353 行定义.

                                                                       {
  CHECK_GE(points_.size(), 3U);
  CHECK_NOTNULL(overlap_polygon);
  ACHECK(is_convex_ && other_polygon.is_convex());
  std::vector<Vec2d> points = other_polygon.points();
  for (int i = 0; i < num_points_; ++i) {
    if (!ClipConvexHull(line_segments_[i], &points)) {
      return false;
    }
  }
  return ComputeConvexHull(points, overlap_polygon, false);
}

◆ Contains() [1/2]

bool apollo::common::math::Polygon2d::Contains ( const LineSegment2d & line_segment ) const

Check if the polygon contains a line segment.

参数

line_segment The target line segment. To check if the polygon contains it.

返回: Whether the polygon contains the line segment or not.

在文件 polygon2d.cc 第 173 行定义.

                                                                {
  if (line_segment.length() <= kMathEpsilon) {
    return IsPointIn(line_segment.start());
  }
  CHECK_GE(points_.size(), 3U);
  if (!IsPointIn(line_segment.start())) {
    return false;
  }
  if (!IsPointIn(line_segment.end())) {
    return false;
  }
  if (!is_convex_) {
    std::vector<LineSegment2d> overlaps = GetAllOverlaps(line_segment);
    double total_length = 0;
    for (const auto &overlap_seg : overlaps) {
      total_length += overlap_seg.length();
    }
    return total_length >= line_segment.length() - kMathEpsilon;
  }
  return true;
}

◆ Contains() [2/2]

bool apollo::common::math::Polygon2d::Contains ( const Polygon2d & polygon ) const

Check if the polygon contains another polygon.

参数

polygon The target polygon. To check if this polygon contains it.

返回: Whether this polygon contains another polygon or not.

在文件 polygon2d.cc 第 195 行定义.

                                                       {
  CHECK_GE(points_.size(), 3U);
  if (area_ < polygon.area() - kMathEpsilon) {
    return false;
  }
  if (!IsPointIn(polygon.points()[0])) {
    return false;
  }
  const auto &line_segments = polygon.line_segments();
  return std::all_of(line_segments.begin(), line_segments.end(),
                     [&](const LineSegment2d &line_segment) {
                       return Contains(line_segment);
                     });
}

◆ DebugString()

std::string apollo::common::math::Polygon2d::DebugString ( ) const

Get a string containing essential information about the polygon for debugging purpose.

返回: Essential information about the polygon for debugging purpose.

在文件 polygon2d.cc 第 695 行定义.

                                       {
  return absl::StrCat("polygon2d (  num_points = ", num_points_, "  points = (",
                      absl::StrJoin(points_, " ", util::DebugStringFormatter()),
                      " )  ", is_convex_ ? "convex" : "non-convex",
                      "  area = ", area_, " )");
}

◆ DistanceSquareTo()

double apollo::common::math::Polygon2d::DistanceSquareTo ( const Vec2d & point ) const

Compute the square of distance from a point to the polygon.

If the point is within the polygon, return 0. Otherwise, this square of distance is the minimal square of distance from the point to the edges of the polygon.

参数

point The point to compute whose square of distance to the polygon.

返回: The square of distance from the point to the polygon.

在文件 polygon2d.cc 第 57 行定义.

                                                           {
  CHECK_GE(points_.size(), 3U);
  if (IsPointIn(point)) {
    return 0.0;
  }
  double distance_sqr = std::numeric_limits<double>::infinity();
  for (int i = 0; i < num_points_; ++i) {
    distance_sqr =
        std::min(distance_sqr, line_segments_[i].DistanceSquareTo(point));
  }
  return distance_sqr;
}

◆ DistanceTo() [1/4]

double apollo::common::math::Polygon2d::DistanceTo ( const Box2d & box ) const

Compute the distance from a box to the polygon.

If the box is within the polygon, or it has overlap with the polygon, return 0. Otherwise, this distance is the minimal distance among the distances from the edges of the box to the polygon.

参数

box	The box to compute whose distance to the polygon.

返回: The distance from the box to the polygon.

在文件 polygon2d.cc 第 93 行定义.

                                                   {
  CHECK_GE(points_.size(), 3U);
  return DistanceTo(Polygon2d(box));
}

◆ DistanceTo() [2/4]

double apollo::common::math::Polygon2d::DistanceTo ( const LineSegment2d & line_segment ) const

Compute the distance from a line segment to the polygon.

If the line segment is within the polygon, or it has intersect with the polygon, return 0. Otherwise, this distance is the minimal distance between the distances from the two ends of the line segment to the polygon.

参数

line_segment The line segment to compute whose distance to the polygon.

返回: The distance from the line segment to the polygon.

在文件 polygon2d.cc 第 70 行定义.

                                                                    {
  if (line_segment.length() <= kMathEpsilon) {
    return DistanceTo(line_segment.start());
  }
  CHECK_GE(points_.size(), 3U);
  if (IsPointIn(line_segment.center())) {
    return 0.0;
  }
  if (std::any_of(line_segments_.begin(), line_segments_.end(),
                  [&](const LineSegment2d &poly_seg) {
                    return poly_seg.HasIntersect(line_segment);
                  })) {
    return 0.0;
  }
 
  double distance = std::min(DistanceTo(line_segment.start()),
                             DistanceTo(line_segment.end()));
  for (int i = 0; i < num_points_; ++i) {
    distance = std::min(distance, line_segment.DistanceTo(points_[i]));
  }
  return distance;
}

◆ DistanceTo() [3/4]

double apollo::common::math::Polygon2d::DistanceTo ( const Polygon2d & polygon ) const

Compute the distance from another polygon to the polygon.

If the other polygon is within this polygon, or it has overlap with this polygon, return 0. Otherwise, this distance is the minimal distance among the distances from the edges of the other polygon to this polygon.

参数

polygon The polygon to compute whose distance to this polygon.

返回: The distance from the other polygon to this polygon.

在文件 polygon2d.cc 第 98 行定义.

                                                           {
  CHECK_GE(points_.size(), 3U);
  CHECK_GE(polygon.num_points(), 3);
 
  if (IsPointIn(polygon.points()[0])) {
    return 0.0;
  }
  if (polygon.IsPointIn(points_[0])) {
    return 0.0;
  }
  double distance = std::numeric_limits<double>::infinity();
  for (int i = 0; i < num_points_; ++i) {
    distance = std::min(distance, polygon.DistanceTo(line_segments_[i]));
  }
  return distance;
}

◆ DistanceTo() [4/4]

double apollo::common::math::Polygon2d::DistanceTo ( const Vec2d & point ) const

Compute the distance from a point to the polygon.

If the point is within the polygon, return 0. Otherwise, this distance is the minimal distance from the point to the edges of the polygon.

参数

point The point to compute whose distance to the polygon.

返回: The distance from the point to the polygon.

在文件 polygon2d.cc 第 45 行定义.

                                                     {
  CHECK_GE(points_.size(), 3U);
  if (IsPointIn(point)) {
    return 0.0;
  }
  double distance = std::numeric_limits<double>::infinity();
  for (int i = 0; i < num_points_; ++i) {
    distance = std::min(distance, line_segments_[i].DistanceTo(point));
  }
  return distance;
}

◆ DistanceToBoundary()

double apollo::common::math::Polygon2d::DistanceToBoundary ( const Vec2d & point ) const

Compute the distance from a point to the boundary of the polygon.

This distance is equal to the minimal distance from the point to the edges of the polygon.

参数

point The point to compute whose distance to the polygon.

返回: The distance from the point to the polygon's boundary.

在文件 polygon2d.cc 第 115 行定义.

                                                             {
  double distance = std::numeric_limits<double>::infinity();
  for (int i = 0; i < num_points_; ++i) {
    distance = std::min(distance, line_segments_[i].DistanceTo(point));
  }
  return distance;
}

◆ ExpandByDistance()

Polygon2d apollo::common::math::Polygon2d::ExpandByDistance ( const double distance ) const

Expand this polygon by a distance.

参数

distance The specified distance. To expand this polygon by it.

返回: The polygon after expansion.

在文件 polygon2d.cc 第 604 行定义.

                                                                 {
  if (!is_convex_) {
    Polygon2d convex_polygon;
    ComputeConvexHull(points_, &convex_polygon);
    ACHECK(convex_polygon.is_convex());
    return convex_polygon.ExpandByDistance(distance);
  }
  const double kMinAngle = 0.1;
  std::vector<Vec2d> points;
  for (int i = 0; i < num_points_; ++i) {
    const double start_angle = line_segments_[Prev(i)].heading() - M_PI_2;
    const double end_angle = line_segments_[i].heading() - M_PI_2;
    const double diff = WrapAngle(end_angle - start_angle);
    if (diff <= kMathEpsilon) {
      points.push_back(points_[i] +
                       Vec2d::CreateUnitVec2d(start_angle) * distance);
    } else {
      const int count = static_cast<int>(diff / kMinAngle) + 1;
      for (int k = 0; k <= count; ++k) {
        const double angle = start_angle + diff * static_cast<double>(k) /
                                               static_cast<double>(count);
        points.push_back(points_[i] + Vec2d::CreateUnitVec2d(angle) * distance);
      }
    }
  }
  Polygon2d new_polygon;
  ACHECK(ComputeConvexHull(points, &new_polygon));
  return new_polygon;
}

◆ ExtremePoints()

void apollo::common::math::Polygon2d::ExtremePoints	(	const double	heading,
		Vec2d *const	first,
		Vec2d *const	last
	)		const

Get the extreme points along a heading direction.

参数

heading	The specified heading.
first	The point on the boundary of this polygon with the minimal projection onto the heading direction.
last	The point on the boundary of this polygon with the maximal projection onto the heading direction.

在文件 polygon2d.cc 第 500 行定义.

                                                       {
  CHECK_GE(points_.size(), 3U);
  CHECK_NOTNULL(first);
  CHECK_NOTNULL(last);
 
  const Vec2d direction_vec = Vec2d::CreateUnitVec2d(heading);
  double min_proj = std::numeric_limits<double>::infinity();
  double max_proj = -std::numeric_limits<double>::infinity();
  for (const auto &pt : points_) {
    const double proj = pt.InnerProd(direction_vec);
    if (proj < min_proj) {
      min_proj = proj;
      *first = pt;
    }
    if (proj > max_proj) {
      max_proj = proj;
      *last = pt;
    }
  }
}

◆ GetAllOverlaps()

std::vector< LineSegment2d > apollo::common::math::Polygon2d::GetAllOverlaps ( const LineSegment2d & line_segment ) const

Get all overlapped line segments of a line segment and this polygon.

There are possibly multiple overlapped line segments if this polygon is not convex.

参数

line_segment The target line segment. To get its all overlapped line segments with this polygon.

返回: A group of overlapped line segments.

在文件 polygon2d.cc 第 446 行定义.

                                             {
  CHECK_GE(points_.size(), 3U);
 
  if (line_segment.length() <= kMathEpsilon) {
    std::vector<LineSegment2d> overlaps;
    if (IsPointIn(line_segment.start())) {
      overlaps.push_back(line_segment);
    }
    return overlaps;
  }
  std::vector<double> projections;
  if (IsPointIn(line_segment.start())) {
    projections.push_back(0.0);
  }
  if (IsPointIn(line_segment.end())) {
    projections.push_back(line_segment.length());
  }
  for (const auto &poly_seg : line_segments_) {
    Vec2d pt;
    if (poly_seg.GetIntersect(line_segment, &pt)) {
      projections.push_back(line_segment.ProjectOntoUnit(pt));
    }
  }
  std::sort(projections.begin(), projections.end());
  std::vector<std::pair<double, double>> overlaps;
  for (size_t i = 0; i + 1 < projections.size(); ++i) {
    const double start_proj = projections[i];
    const double end_proj = projections[i + 1];
    if (end_proj - start_proj <= kMathEpsilon) {
      continue;
    }
    const Vec2d reference_point =
        line_segment.start() +
        (start_proj + end_proj) / 2.0 * line_segment.unit_direction();
    if (!IsPointIn(reference_point)) {
      continue;
    }
    if (overlaps.empty() ||
        start_proj > overlaps.back().second + kMathEpsilon) {
      overlaps.emplace_back(start_proj, end_proj);
    } else {
      overlaps.back().second = end_proj;
    }
  }
  std::vector<LineSegment2d> overlap_line_segments;
  for (const auto &overlap : overlaps) {
    overlap_line_segments.emplace_back(
        line_segment.start() + overlap.first * line_segment.unit_direction(),
        line_segment.start() + overlap.second * line_segment.unit_direction());
  }
  return overlap_line_segments;
}

◆ GetAllVertices() [1/2]

std::vector< Vec2d > apollo::common::math::Polygon2d::GetAllVertices ( ) const

Get all vertices of the polygon

在文件 polygon2d.cc 第 444 行定义.

444{ return points_; }

◆ GetAllVertices() [2/2]

void apollo::common::math::Polygon2d::GetAllVertices ( std::vector< Vec2d > *const vertices ) const

Get all vertices of the polygon

参数

All	vertices of the polygon

在文件 polygon2d.cc 第 437 行定义.

                                                                     {
  if (vertices == nullptr) {
    return;
  }
  *vertices = points_;
}

◆ GetOverlap()

bool apollo::common::math::Polygon2d::GetOverlap	(	const LineSegment2d &	line_segment,
		Vec2d *const	first,
		Vec2d *const	last
	)		const

Get the overlap of a line segment and this polygon.

If they have overlap, output the two ends of the overlapped line segment.

参数

line_segment	The target line segment. To get its overlap with this polygon.
first	First end of the overlapped line segment.
second	Second end of the overlapped line segment.

返回: If the target line segment has overlap with this polygon.

在文件 polygon2d.cc 第 395 行定义.

                                                                        {
  CHECK_GE(points_.size(), 3U);
  CHECK_NOTNULL(first);
  CHECK_NOTNULL(last);
 
  if (line_segment.length() <= kMathEpsilon) {
    if (!IsPointIn(line_segment.start())) {
      return false;
    }
    *first = line_segment.start();
    *last = line_segment.start();
    return true;
  }
 
  double min_proj = line_segment.length();
  double max_proj = 0;
  if (IsPointIn(line_segment.start())) {
    *first = line_segment.start();
    min_proj = 0.0;
  }
  if (IsPointIn(line_segment.end())) {
    *last = line_segment.end();
    max_proj = line_segment.length();
  }
  for (const auto &poly_seg : line_segments_) {
    Vec2d pt;
    if (poly_seg.GetIntersect(line_segment, &pt)) {
      const double proj = line_segment.ProjectOntoUnit(pt);
      if (proj < min_proj) {
        min_proj = proj;
        *first = pt;
      }
      if (proj > max_proj) {
        max_proj = proj;
        *last = pt;
      }
    }
  }
  return min_proj <= max_proj + kMathEpsilon;
}

◆ HasOverlap() [1/2]

bool apollo::common::math::Polygon2d::HasOverlap ( const LineSegment2d & line_segment ) const

Check if a line segment has overlap with this polygon.

参数

line_segment The target line segment. To check if it has overlap with this polygon.

返回: Whether the target line segment has overlap with this polygon or not.

在文件 polygon2d.cc 第 377 行定义.

                                                                  {
  CHECK_GE(points_.size(), 3U);
  if ((line_segment.start().x() < min_x_ && line_segment.end().x() < min_x_) ||
      (line_segment.start().x() > max_x_ && line_segment.end().x() > max_x_) ||
      (line_segment.start().y() < min_y_ && line_segment.end().y() < min_y_) ||
      (line_segment.start().y() > max_y_ && line_segment.end().y() > max_y_)) {
    return false;
  }
 
  if (std::any_of(line_segments_.begin(), line_segments_.end(),
                  [&](const LineSegment2d &poly_seg) {
                    return poly_seg.HasIntersect(line_segment);
                  })) {
    return true;
  }
  return false;
}

◆ HasOverlap() [2/2]

bool apollo::common::math::Polygon2d::HasOverlap ( const Polygon2d & polygon ) const

Check if this polygon has overlap with another polygon.

参数

polygon The target polygon. To check if it has overlap with this polygon.

返回: If this polygon has overlap with another polygon.

在文件 polygon2d.cc 第 149 行定义.

                                                         {
  CHECK_GE(points_.size(), 3U);
  CHECK_GE(polygon.num_points(), 3);
  if (polygon.max_x() < min_x() || polygon.min_x() > max_x() ||
      polygon.max_y() < min_y() || polygon.min_y() > max_y()) {
    return false;
  }
 
  if (IsPointIn(polygon.points()[0])) {
    return true;
  }
 
  if (polygon.IsPointIn(points_[0])) {
    return true;
  }
 
  for (int i = 0; i < polygon.num_points(); ++i) {
    if (HasOverlap(polygon.line_segments()[i])) {
      return true;
    }
  }
  return false;
}

◆ is_convex()

bool apollo::common::math::Polygon2d::is_convex ( ) const

inline

Check if the polygon is convex.

返回: Whether the polygon is convex or not.

在文件 polygon2d.h 第 85 行定义.

85{ return is_convex_; }

◆ IsPointIn()

bool apollo::common::math::Polygon2d::IsPointIn ( const Vec2d & point ) const

Check if a point is within the polygon.

参数

point The target point. To check if it is within the polygon.

返回: Whether a point is within the polygon or not.

在文件 polygon2d.cc 第 130 行定义.

                                                  {
  CHECK_GE(points_.size(), 3U);
  if (IsPointOnBoundary(point)) {
    return true;
  }
  int j = num_points_ - 1;
  int c = 0;
  for (int i = 0; i < num_points_; ++i) {
    if ((points_[i].y() > point.y()) != (points_[j].y() > point.y())) {
      const double side = CrossProd(point, points_[i], points_[j]);
      if (points_[i].y() < points_[j].y() ? side > 0.0 : side < 0.0) {
        ++c;
      }
    }
    j = i;
  }
  return c & 1;
}

◆ IsPointOnBoundary()

bool apollo::common::math::Polygon2d::IsPointOnBoundary ( const Vec2d & point ) const

Check if a point is on the boundary of the polygon.

参数

point The target point. To check if it is on the boundary of the polygon.

返回: Whether a point is on the boundary of the polygon or not.

在文件 polygon2d.cc 第 123 行定义.

                                                          {
  CHECK_GE(points_.size(), 3U);
  return std::any_of(
      line_segments_.begin(), line_segments_.end(),
      [&](const LineSegment2d &poly_seg) { return poly_seg.IsPointIn(point); });
}

◆ line_segments()

const std::vector< LineSegment2d > & apollo::common::math::Polygon2d::line_segments ( ) const

inline

Get the edges of the polygon.

返回: The edges of the polygon.

在文件 polygon2d.h 第 71 行定义.

                                                        {
    return line_segments_;
  }

◆ max_x()

double apollo::common::math::Polygon2d::max_x ( ) const

inline

在文件 polygon2d.h 第 320 行定义.

320{ return max_x_; }

◆ max_y()

double apollo::common::math::Polygon2d::max_y ( ) const

inline

在文件 polygon2d.h 第 322 行定义.

322{ return max_y_; }

◆ min_x()

double apollo::common::math::Polygon2d::min_x ( ) const

inline

在文件 polygon2d.h 第 319 行定义.

319{ return min_x_; }

◆ min_y()

double apollo::common::math::Polygon2d::min_y ( ) const

inline

在文件 polygon2d.h 第 321 行定义.

321{ return min_y_; }

◆ MinAreaBoundingBox()

Box2d apollo::common::math::Polygon2d::MinAreaBoundingBox ( ) const

Get the bounding box with the minimal area.

返回: The bounding box with the minimal area.

在文件 polygon2d.cc 第 545 行定义.

                                          {
  CHECK_GE(points_.size(), 3U);
  if (!is_convex_) {
    Polygon2d convex_polygon;
    ComputeConvexHull(points_, &convex_polygon);
    ACHECK(convex_polygon.is_convex());
    return convex_polygon.MinAreaBoundingBox();
  }
  double min_area = std::numeric_limits<double>::infinity();
  double min_area_at_heading = 0.0;
  int left_most = 0;
  int right_most = 0;
  int top_most = 0;
  for (int i = 0; i < num_points_; ++i) {
    const auto &line_segment = line_segments_[i];
    double proj = 0.0;
    double min_proj = line_segment.ProjectOntoUnit(points_[left_most]);
    while ((proj = line_segment.ProjectOntoUnit(points_[Prev(left_most)])) <
           min_proj) {
      min_proj = proj;
      left_most = Prev(left_most);
    }
    while ((proj = line_segment.ProjectOntoUnit(points_[Next(left_most)])) <
           min_proj) {
      min_proj = proj;
      left_most = Next(left_most);
    }
    double max_proj = line_segment.ProjectOntoUnit(points_[right_most]);
    while ((proj = line_segment.ProjectOntoUnit(points_[Prev(right_most)])) >
           max_proj) {
      max_proj = proj;
      right_most = Prev(right_most);
    }
    while ((proj = line_segment.ProjectOntoUnit(points_[Next(right_most)])) >
           max_proj) {
      max_proj = proj;
      right_most = Next(right_most);
    }
    double prod = 0.0;
    double max_prod = line_segment.ProductOntoUnit(points_[top_most]);
    while ((prod = line_segment.ProductOntoUnit(points_[Prev(top_most)])) >
           max_prod) {
      max_prod = prod;
      top_most = Prev(top_most);
    }
    while ((prod = line_segment.ProductOntoUnit(points_[Next(top_most)])) >
           max_prod) {
      max_prod = prod;
      top_most = Next(top_most);
    }
    const double area = max_prod * (max_proj - min_proj);
    if (area < min_area) {
      min_area = area;
      min_area_at_heading = line_segment.heading();
    }
  }
  return BoundingBoxWithHeading(min_area_at_heading);
}

◆ MinLineSegment()

LineSegment2d apollo::common::math::Polygon2d::MinLineSegment ( ) const

在文件 polygon2d.cc 第 684 行定义.

                                              {
  double min_length_of_line_segment = 10e3;
  LineSegment2d line_segment;
  for (auto &line_segment_ : line_segments_) {
    if (line_segment_.length() < min_length_of_line_segment) {
      line_segment = line_segment_;
    }
  }
  return line_segment;
}

◆ Next()

int apollo::common::math::Polygon2d::Next ( int at ) const

protected

在文件 polygon2d.cc 第 210 行定义.

210{ return at >= num_points_ - 1 ? 0 : at + 1; }

◆ num_points()

int apollo::common::math::Polygon2d::num_points ( ) const

inline

Get the number of vertices of the polygon.

返回: The number of vertices of the polygon.

在文件 polygon2d.h 第 79 行定义.

79{ return num_points_; }

◆ points()

const std::vector< Vec2d > & apollo::common::math::Polygon2d::points ( ) const

inline

Get the vertices of the polygon.

返回: The vertices of the polygon.

在文件 polygon2d.h 第 65 行定义.

65{ return points_; }

◆ PolygonExpandByDistance()

Polygon2d apollo::common::math::Polygon2d::PolygonExpandByDistance ( const double distance ) const

在文件 polygon2d.cc 第 634 行定义.

                                                                        {
  if (!is_convex_) {
    Polygon2d convex_polygon;
    ComputeConvexHull(points_, &convex_polygon);
    ACHECK(convex_polygon.is_convex());
    return convex_polygon.PolygonExpandByDistance(distance);
  }
  std::vector<Vec2d> points;
  for (int i = 0; i < num_points_; ++i) {
    double v1x = points_[Prev(i)].x() - points_[i].x();
    double v1y = points_[Prev(i)].y() - points_[i].y();
    double n1 = std::sqrt(v1x * v1x + v1y * v1y);
    v1x /= n1;
    v1y /= n1;
 
    double v2x = points_[Next(i)].x() - points_[i].x();
    double v2y = points_[Next(i)].y() - points_[i].y();
    double n2 = std::sqrt(v2x * v2x + v2y * v2y);
    v2x /= n2;
    v2x /= n2;
 
    double l = distance / sqrt((1 - (v1x * v2x + v1y * v2y)) / 2);
 
    double vx = v1x + v2x;
    double vy = v1y + v2y;
    double n = l / sqrt(vx * vx + vy * vy);
 
    vx *= n;
    vy *= n;
 
    Vec2d point(vx + points_[i].x(), vy + points_[i].y());
    points.push_back(point);
  }
  Polygon2d new_polygon;
  ACHECK(ComputeConvexHull(points, &new_polygon));
  return new_polygon;
}

◆ Prev()

int apollo::common::math::Polygon2d::Prev ( int at ) const

protected

在文件 polygon2d.cc 第 212 行定义.

212{ return at == 0 ? num_points_ - 1 : at - 1; }

类成员变量说明

◆ area_

double apollo::common::math::Polygon2d::area_ = 0.0

protected

在文件 polygon2d.h 第 337 行定义.

◆ is_convex_

bool apollo::common::math::Polygon2d::is_convex_ = false

protected

在文件 polygon2d.h 第 336 行定义.

◆ line_segments_

std::vector<LineSegment2d> apollo::common::math::Polygon2d::line_segments_

protected

在文件 polygon2d.h 第 335 行定义.

◆ max_x_

double apollo::common::math::Polygon2d::max_x_ = 0.0

protected

在文件 polygon2d.h 第 339 行定义.

◆ max_y_

double apollo::common::math::Polygon2d::max_y_ = 0.0

protected

在文件 polygon2d.h 第 341 行定义.

◆ min_x_

double apollo::common::math::Polygon2d::min_x_ = 0.0

protected

在文件 polygon2d.h 第 338 行定义.

◆ min_y_

double apollo::common::math::Polygon2d::min_y_ = 0.0

protected

在文件 polygon2d.h 第 340 行定义.

◆ num_points_

int apollo::common::math::Polygon2d::num_points_ = 0

protected

在文件 polygon2d.h 第 334 行定义.

◆ points_

std::vector<Vec2d> apollo::common::math::Polygon2d::points_

protected

在文件 polygon2d.h 第 333 行定义.

该类的文档由以下文件生成:

modules/common/math/polygon2d.h
modules/common/math/polygon2d.cc

Public 成员函数

静态 Public 成员函数

Protected 成员函数

静态 Protected 成员函数

Protected 属性

详细描述

构造及析构函数说明

◆ Polygon2d() [1/3]

◆ Polygon2d() [2/3]

◆ Polygon2d() [3/3]

成员函数说明

◆ AABoundingBox()

◆ area()

◆ BoundingBoxWithHeading()

◆ BuildFromPoints()

◆ CalculateVertices()

◆ ClipConvexHull()

◆ ComputeConvexHull()

◆ ComputeIoU()

◆ ComputeOverlap()

◆ Contains() [1/2]

◆ Contains() [2/2]

◆ DebugString()

◆ DistanceSquareTo()

◆ DistanceTo() [1/4]

◆ DistanceTo() [2/4]

◆ DistanceTo() [3/4]

◆ DistanceTo() [4/4]

◆ DistanceToBoundary()

◆ ExpandByDistance()

◆ ExtremePoints()

◆ GetAllOverlaps()

◆ GetAllVertices() [1/2]

◆ GetAllVertices() [2/2]

◆ GetOverlap()

◆ HasOverlap() [1/2]

◆ HasOverlap() [2/2]

◆ is_convex()

◆ IsPointIn()

◆ IsPointOnBoundary()

◆ line_segments()

◆ max_x()

◆ max_y()

◆ min_x()

◆ min_y()

◆ MinAreaBoundingBox()

◆ MinLineSegment()

◆ Next()

◆ num_points()

◆ points()

◆ PolygonExpandByDistance()

◆ Prev()

类成员变量说明

◆ area_

◆ is_convex_

◆ line_segments_

◆ max_x_

◆ max_y_

◆ min_x_

◆ min_y_

◆ num_points_

◆ points_