Efficient construction method for convex hull of planar point set
Efficient construction method for convex hull of planar point set
 CN 104,751,519 A
 Filed: 04/07/2015
 Published: 07/01/2015
 Est. Priority Date: 04/07/2015
 Status: Active Application
First Claim
1. The characterization step asking for convex hull based on plane point set is as follows:
 Connect and obtain line segment P _{l}p _{r}, calculate point set S middle conductor P _{l}p _{r}apsis P _{m}, connect P successively _{l}p _{m}, P _{r}p _{m}form initial convex hull BCH (S), as shown in figure (3), triangle P _{l}p _{r}p _{m}be initial convex hull BCH (S).
Abstract
The invention provides an efficient construction method for a convex hull of a planar point set. The efficient construction method for the convex hull of the planar point set comprises the following steps of finding out a minimum point and a maximum point of a coordinate value (x); calculating a point which is the farthest to a segment formed by the minimum point and the maximum point; connecting an initial convex hull formed by the point; sequentially calculating points, which are the farthest to edges of the initial convex hull, from point sets of the outer sides of the edges of the initial convex hull; connecting the points and deleting points positioned in the convex hull; updating the initial convex hull; and repeatedly updating the initial convex hull until other discrete points do not exist on the outside of the initial convex hull so that the convex hull is a finally constructed convex hull. On the basis of a test, an analysis result shows that the convex hull generation efficiency is high by the efficient construction method.

3 Citations
Convex hull obtaining method and device  
Patent #
CN 106,373,151 A
Filed 08/26/2016

Current Assignee

Parallel algorithm of computing convex hull based on multinuclear framework  
Patent #
CN 103,116,593 A
Filed 06/08/2012

Current Assignee

Method for quickly structuring threedimensional convex hull  
Patent #
CN 103,530,906 A
Filed 09/27/2013

Current Assignee

3 Claims

1. The characterization step asking for convex hull based on plane point set is as follows:
Connect and obtain line segment P _{l}p _{r}, calculate point set S middle conductor P _{l}p _{r}apsis P _{m}, connect P successively _{l}p _{m}, P _{r}p _{m}form initial convex hull BCH (S), as shown in figure (3), triangle P _{l}p _{r}p _{m}be initial convex hull BCH (S).

2. Remove the interior point of initial convex hull BCH (S), detect outside the every bar limit of BCH (S) whether have exterior point successively:

If do not have a little outside this limit, then directly terminate this limit exterior point detection calculations; If only have a point outside this limit, then connect this point and terminate this limit exterior point detection calculations; If the number of exterior point is more than one outside this limit, then the apsis outside this limit of double counting, connects this apsis successively and forms new initial convex hull, and removes inner point, returns step 3.


3. Abnormality processing
For algorithm that article is carried, when seeking extreme point, may exist multiple, specifically having following several special circumstances: 
, the situation of more than two of extreme point may be there is, if when the extreme point dropping on right boundary exists multiple in 1 extreme point first calculating x coordinate, then get the point that y coordinate figure is minimum respectively, as shown in figure (10), left extreme point exists multiple, then choose the some P that y coordinate figure is minimum _{l1};
2, when calculating apsis, there will be the situation that there is multiple apsis equally, if when existing multiple for apsis required by a line segment, then get 2 points that x coordinate figure is minimum and maximum, as shown in figure (11), then choose P _{m1}p _{m3}2 points, P like this _{m2}limit P will be dropped on _{m1}p _{m3}above become interior point deletion.

Specification(s)