正交船体算法 [英] Orthogonal hull algorithm

问题描述

我正在尝试找到一种方法来从一组整数中确定

我只需要定义直线多边形边界的最小点集。我可以找到的大多数船体算法都不能满足此问题的正交性，例如

如何获取一组定义图像 1中显示的边界的点。？

已更新：

图1.不再称为凸形。

解决方案

我认为您想要计算是点集的直线凸包（或正交凸包）。直线形凸包是一个正凸形状，也就是说，该形状与任何水平或垂直线的交集都将导致一个空集，一个点或一个线段。

直线凸包的顶点是向量优势下的最大点集。然后可以在最佳O（n log n）时间中计算直线凸包。 Preparata的书中提供了一种非常简单的算法计算几何（请参阅第4.1.3节）。

I am trying to find a way to determine the rectilinear polygon from a set of integer points (indicated by the red dots in the pictures below). The image below shows what I would like to achieve:

1.

I need only the minimal set of points that define the boundary of the rectilinear polygon. Most hull algorithms I can find do not satisfy the orthogonal nature of this problem, such as the gift-wrapping algorithm, which produce the following result (which is not what I want)...

2.

How can I get the set of points that defines the boundary shown in image 1.?

Updated:

Figure 1. is no longer refereed to as convex..

解决方案

I think what you want to compute is the Rectilinear Convex Hull (or Orthogonal Convex Hull) of the set of points. The rectilinear convex hull is an ortho-convex shape, that is, the intersection of the shape with any horizontal or vertical line results in an empty set, a point, or a line segment.

The vertices of the rectilinear convex hull are the set of maximal points under vector dominance. The rectilinear convex hull can then be computed in optimal O(n log n) time. A very simple algorithm is presented in Preparata's book on Computational Geometry (see the section 4.1.3).

这篇关于正交船体算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！