CN103116593A - Parallel algorithm of computing convex hull based on multinuclear framework - Google Patents
Parallel algorithm of computing convex hull based on multinuclear framework Download PDFInfo
- Publication number
- CN103116593A CN103116593A CN2012101868830A CN201210186883A CN103116593A CN 103116593 A CN103116593 A CN 103116593A CN 2012101868830 A CN2012101868830 A CN 2012101868830A CN 201210186883 A CN201210186883 A CN 201210186883A CN 103116593 A CN103116593 A CN 103116593A
- Authority
- CN
- China
- Prior art keywords
- directed edge
- convex hull
- point
- algorithm
- point set
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Images
Landscapes
- Image Generation (AREA)
Abstract
The invention provides a parallel algorithm of computing a convex hull based on a multinuclear framework specific to the defect of an existing convex hull algorithm. The parallel algorithm of computing the convex hull based on the multinuclear framework comprises the following steps: (1), finding the initial incomplete convex hull of initial point assembly, indicating edges by counter clockwise direction directed edge; (2), classifying a point set based on the initial incomplete convex hull, finding out all of the outer points of directed edges; (3), iteratively and concurrently breeding each of the directed edge of the initial incomplete convex hull; (4), deleting final acquired non-convex-hull peak on the convex hull. The parallel algorithm of computing the convex hull based on the multinuclear framework effectively optimizes an original algorithm and plenarily saves calculation resources, parallelly expands the classification process of the point set and the iterative process to the original algorithm, and fully utilizes the parallel calculation resources of a multi-core processor; so that parallel speed-up ratio is controlled by controlling parallel mission grain size further by self-adaption selection of the parallel and serial, and possibly produced bottlenecks are eliminated.
Description
Technical field
The present invention relates to the computational geometry field, especially relate to a kind of parallel algorithm of the calculating convex hull based on multicore architecture.
Background technology
Convex hull is a kind of structure general, the most basic in computational geometry, occupies important position in computational geometry.Convex hull not only has numerous characteristics, but also is the effective tool of other geometrical bodies of structure.Convex hull also claims Minimum Convex Closure, is the minimum convex set that comprises all objects in S set.Wherein, convex hull of planar point set is most important, most basic problem, and the Convex Problem of plane line-segment set peace face polygon set can be converted to the Convex Problem of plane point set.The Convex Problem of plane point set is widely used in the various fields such as computer graphics, image processing and pattern-recognition, Geographic Information System.
The convex hull of finding the solution plane point set is namely the minimum convex set that requirement gets point set, and the border of convex hull is a convex polygon.About calculating the serial algorithm of convex hull, mainly contain wraparound pack, Graham Sodd method of investing algorithm, the algorithm of dividing and ruling, delta algorithm, real time algorithm, fast algorithm etc. in early stage achievement in research both domestic and external.Along with the development of parallel computing, many researchists both domestic and external attempt concurrent technique is applied in the calculating of convex hull.In these parallel algorithms, the overwhelming majority has used divide-and-conquer strategy, and being about to former PROBLEM DECOMPOSITION is some subproblems, parallelly independently finds the solution these subproblems, and the solution that then merges all subproblems obtains the solution of former problem.At present, also there are two subject matters in these parallel algorithms.The first, parallel granularity is uncontrolled, and load balance problem is considered not enough, bottleneck might occur; The second, introduced a large amount of extra computation tasks for realizing parallel computation, when former problem is decomposed, usually to sort to the initial point set etc.
The Z that finds the solution convex hull of planar point set with divide and conquer that proposes with Zhou Peide
3-2Algorithm is example, its basic thought is first to obtain a little to concentrate x, y coordinate maximal value, minimum value, then maximal value, corresponding some quadrangularly of minimum value are linked in sequence, this quadrilateral partition point set is 5 subsets, do not consider to be positioned at the subset of quadrilateral, other 4 subsets are deleted iteratively the point that is not the convex hull summit.In this algorithm at first judging point be positioned at which side (being positive and negative division) of directed line segment, re-use Euclidean distance and find out from directed line segment point farthest, algorithm is loaded down with trivial details, has taken a large amount of computational resources.
Summary of the invention
the present invention is directed to the deficiency that above-mentioned existing convex hull algorithm exists, on the basis of traditional planar convex hull algorithm, application request according to the calculating of the real-time of planar convex hull and mass data, proposed a kind of under multicore architecture the parallel algorithm of Calculation Plane point set convex hull, a kind of parallel algorithm of the calculating convex hull based on multicore architecture is provided, division when having abandoned compute euclidian distances and extracting operation, and whole computation process is resolved into some separate subtasks, take full advantage of as far as possible the concurrent computation resource of polycaryon processor, improved the execution efficient of algorithm.
The present invention obtains an initial not exclusively convex hull after the extreme point that finds point set on x direction, y direction.Classify in this initial not exclusively outside of each directed edge of convex hull according to it to putting concentrated all points, make every directed edge all comprise the data of its all exterior points, simultaneously, deleted this initial not exclusively convex hull inside have a few.Iteration all directed edges of growing concurrently, and continue the larger growth task of task resolution granularity according to threshold condition in iterative process, carry out the Intelligence Selection of serial and concurrent operation, constantly the assigned address in the initial not exclusively convex hull inserts new convex hull point, generate new directed edge, and according to newly-generated directed edge, the point in the set of former directed edge exterior point is classified, iteration like this is until the exterior point set of all directed edges is sky.Also will delete at last the non-salient point in all convex hull polygons, these points are on this polygonal limit, rather than its summit.
In order to achieve the above object, the invention provides following technical scheme:
A kind of parallel algorithm of the calculating convex hull based on multicore architecture comprises the following steps:
(1) find the initial not exclusively convex hull of initial point set, its each limit represents with anticlockwise directed edge;
(2) according to initial not exclusively convex hull, a set is classified, find out all exterior points of each directed edge;
(3) each directed edge in the initial not exclusively convex hull of growth concurrently iteratively;
(4) the non-convex hull summit on the final gained convex hull of deletion.
As a kind of preferred version, the implementation method of described step (1) is: find four extreme points along x coordinate, y coordinate direction, delete identical point in these four points, the remaining convex polygon that counterclockwise surrounds of pressing is initial not exclusively convex hull, is designated as LPBCH (S).
As a kind of preferred version, the implementation method of described step (2) is: the definition determinant
Value for a some P (x, y) to vectorial P
1P
2(P
1(x
1, y
1), P
2(x
2, y
2)) the Yan Shi distance, will join a little in the exterior point set of this directed edge greater than 0 institute with the Yan Shi distance of initial not exclusively each directed edge of convex hull, during the deletion point is gathered, those are not at the point on any directed edge right side.
As a kind of preferred version, the implementation method of described step (3) is: for each the directed edge P in incomplete convex hull side chain
iP
i+1Carry out concurrently the iteration growth, the process of described iteration growth is:
(a) if directed edge P
iP
i+1The exterior point set be empty, return to the ignore row;
(b) from directed edge P
iP
i+1The exterior point set in find the Yan Shi of this directed edge apart from the some P of maximum, this P must be the convex hull point of point set;
(c) tie point P
iWith a P, some P and some P
i+1, generate two new directed edge P
iP and PP
i+1, to former directed edge P
iP
i+1The exterior point set press directed edge P
iP and PP
i+1Reclassify, obtain respectively directed edge P
iP and directed edge PP
i+1Exterior point set separately;
(d) if directed edge P
iP
i+1The quantity of exterior point set mid point be not more than 2 times of MAXGROW, turn step (f);
(e) iteration growth directed edge P concurrently
iP and PP
i+1Obtain respectively point range L
1And L
2, make point range L={P
i∪ L
1∪ { P} ∪ L
2∪ { P
i+1, turn step (j);
(f) definition chained list E stores some directed edges, with P
iP and PP
i+1Insert E;
(g) for every in E directed edge e, if its exterior point set is not empty, according to (b) (c) methods in two steps obtain two new directed edge e
1And e
2, and e
1And e
2The exterior point set; Delete e from E, and insert e in the position of original e
1And e
2, e wherein
1Identical with the starting point of e;
(h) if (g), the exterior point set of any newly-generated directed edge is not empty, turn step (g);
(i) article one directed edge in deletion E, and make L arrange by the starting point of each directed edge in E the point range that forms;
(j) point range L is as a result of returned;
Wherein, the MAXGROW in (d) be walk abreast, threshold value that serial is selected.
As a kind of preferred version, the implementation method of step (4) is: the every bit of the convex polygon that obtains of traversal step (3) successively, if P is current traversal point, R is forerunner's (namely upper by what counterclockwise arrange) of P, and Q is follow-up (namely more lower by what counterclockwise arrange) of P; If R, P, Q three point on a straight line, just deletion point P from LPBCH (S); Through to the once traversal of LPBCH (S), delete the point on all non-convex hulls summit, just can obtain the convex hull vertex sequence of point set, surround by these summits the convex hull that convex polygon has just consisted of point set.
The present invention comes the position relationship of judging point and directed line segment with the Yan Shi distance, abandoned former Z
3-2Division and the extracting operation of the employing in algorithm during compute euclidian distances have reduced computational complexity, have fully saved calculation resources thereby effectively former algorithm is optimized.Secondly, former algorithm Point Set assorting process and iterative process have been carried out parallel-expansion, be some subtasks that can executed in parallel with more Task-decomposing consuming time, the coupling of having removed between the subtask makes separate execution between each parallel subtasks, has utilized fully the concurrent computation resource of polycaryon processor; In addition, the process of Task-decomposing can be completed in the time complexity of O (1), and parallel overhead is little.At last, the adaptively selected parallel task granularity of controlling by parallel, serial is to control parallel speed-up ratio, and eliminated issuable bottleneck, in the Real-time solution of convex hull of planar point set and mass data were found the solution, performance was calculated or the higher more outstanding effect of parallel computation of coupling than simple serial.
Description of drawings
Fig. 1 is the parallel algorithm schematic flow sheet of the calculating convex hull based on multicore architecture provided by the invention;
Fig. 2 is the Algorithm for Solving design sketch;
Fig. 3 is former Z
3-2Algorithm, the Z after optimization
3-2The parallel algorithm execution time comparison diagram that algorithm and the present invention adopt;
Fig. 4 is the algorithm speed-up ratio schematic diagram that the present invention adopts.
Embodiment
Below with reference to specific embodiment, technical scheme provided by the invention is elaborated, should understands following embodiment and only be used for explanation the present invention and be not used in and limit the scope of the invention.
Based on the parallel algorithm flow process of the calculating convex hull of multicore architecture as shown in Figure 1, detailed process is described below:
(1) at first find the initial not exclusively convex hull of initial point set, its each limit represents with anticlockwise directed edge: find four extreme points along x coordinate, y coordinate direction, delete identical point in these four points, the remaining convex polygon that counterclockwise surrounds of pressing is initial not exclusively convex hull, is designated as LPBCH (S).
LPBCH (S) comprises NCP (S) and NCE (S); Summit in incomplete convex hull row are designated as NCP (S), each summit P
i(x
i, y
i) expression, 1≤i≤n wherein, i is integer, n is counting that point is concentrated, so in NCP (S), n summit is arranged.The anticlockwise oriented side chain that forms between every two summits is designated as NCE (S), each directed edge P
iP
i+1(P
i(x
i, y
i), P
i+1(x
i+1, y
i+1)) represent; 1≤i≤n wherein, i is integer, n is counting that point is concentrated; When i=n, P
i+1=P
n+1=P
1, so n element also arranged in NCE (S), wherein n bar directed edge is P
nP
n+1, i.e. P
nP
1, n bar directed edge surrounds a closed convex polygon.
(2) all points in a set are classified according to the initial not exclusively right side of which bar directed edge of convex hull that it finds in step (1), find out all exterior points of each directed edge:
Point in the some set represents with P (x, y), the vectorial P of directed edge in initial not exclusively convex hull
1P
2(P
1(x
1, y
1), P
2(x
2, y
2)) represent;
The definition determinant
Value for a some P (x, y) to vectorial P
1P
2(P
1(x
1, y
1), P
2(x
2, y
2)) the Yan Shi distance, be designated as YD (P, P
1P
2 ).All points in a set are classified according to the initial not exclusively right side of each directed edge of convex hull whether it finds in step (1), wherein, to the Yan Shi distance of this directed edge greater than 0 the some right side at this directed edge.With the directed edge right side join a little in the exterior point set of this directed edge.In deletion point set, all are not at the point on any directed edge right side, because they are the points on final convex hull in the initial not exclusively inside of convex hull scarcely.
(3) for each the directed edge P in incomplete convex hull side chain
iP
i+1Carry out concurrently the iteration growth.The process of iteration growth is:
(a) if directed edge P
iP
i+1The exterior point set be empty, return to the ignore row;
(b) from directed edge P
iP
i+1The exterior point set in find the Yan Shi of this directed edge apart from the some P of maximum, this P must be the convex hull point of point set;
(c) tie point P
iWith a P, some P and some P
i+1, generate two new directed edge P
iP and PP
i+1, to former directed edge P
iP
i+1The exterior point set press directed edge P
iP and PP
i+1Reclassify, obtain respectively directed edge P
iP and directed edge PP
i+1Exterior point set separately;
(d) if directed edge P
iP
i+1The quantity of exterior point set mid point be not more than 2 times of MAXGROW, turn step (f);
(e) iteration growth directed edge P concurrently
iP and PP
i+1Obtain respectively point range L
1And L
2, make point range L={P
i∪ L
1∪ { P} ∪ L
2∪ { P
i+1, turn step (j);
(f) definition chained list E stores some directed edges, with P
iP and PP
i+1Insert E;
(g) for every in E directed edge e, if its exterior point set is not empty, according to (b) (c) methods in two steps obtain two new directed edge e
1And e
2, and e
1And e
2The exterior point set; Delete e from E, and insert e in the position of original e
1And e
2, e wherein
1Identical with the starting point of e;
(h) if (g), the exterior point set of any newly-generated directed edge is not empty, turn step (g);
(i) article one directed edge in deletion E, and make L arrange by the starting point of each directed edge in E the point range that forms;
(j) point range L is as a result of returned.
Wherein, the MAXGROW in (d) be walk abreast, threshold value that serial is selected, only when the exterior point quantity of the directed edge of growing is abundant, just select parallel algorithm.Along with going deep into of iteration, the quantity of exterior point constantly reduces, and is down to the twice of threshold value when following when exterior point quantity, and parallel algorithm will no longer have superiority, and will select the serial strategy to come finishing iteration this moment, and obtain a result in limited number of time circulates.This step is controlled the parallel task granularity controlling parallel speed-up ratio by parallel, serial adaptively selected, and has eliminated issuable bottleneck.
(4) every bit in the convex polygon that obtains of traversal step (3) successively, establishing P is current traversal point, and R is forerunner's (namely upper by what counterclockwise arrange) of P, and Q is follow-up (namely more lower by what counterclockwise arrange) of P.If R, P, Q three point on a straight line, just deletion point P from LPBCH (S).Through to the once traversal of LPBCH (S), delete the point on all non-convex hulls summit, just can obtain the convex hull vertex sequence of point set, surround by these summits the convex hull that convex polygon has just consisted of point set.
Utilize convex hull parallel algorithm provided by the invention to carry out test for fusion, what fusion experiment adopted is the meteorological sampling number certificate that represents China province, and as shown in Figure 2, intensive point set is the sample distribution of weather data, and this is distributed as the website of all precipitation in this zone.Polygonal region in Fig. 2 is the convex hull that utilizes this point set that parallel algorithm provided by the invention tries to achieve.
As shown in Figure 3, the algorithm and the former Z that the present invention are adopted
3-2The execution efficient of algorithm has been carried out comparative analysis.For further testing the parallel performance of algorithm of the present invention, the present invention is to former Z
3-2Algorithm is optimized and makes itself and algorithm of the present invention have comparability.To former Z
3-2The optimal way of algorithm is: with the class of algorithms of the present invention seemingly, apart from having replaced Euclidean distance, eliminated former Z with stack architexture with Yan Shi
3-2Recurrence in algorithm makes the Z of optimization
3-2Performance when algorithm and the serial of this algorithm are carried out approaches.Fig. 3 is algorithm, the former Z that the present invention adopts
3-2The Z of algorithm and optimization
3-2The execution time comparison diagram of algorithm, the performance boost that produces respectively to distinguish optimization and concurrent operation.
As shown in Figure 3: algorithm of the present invention is to 10
6The convex hull of the point set of the order of magnitude find the solution 200 milliseconds around, proved absolutely the high efficiency of this algorithm; After optimization, Algorithm Performance is greatly improved; Further reduced computing time by parallel computation.When the processor number was more, algorithm execution time was shorter.
Fig. 4 is the speed-up ratio after algorithm improvement of the present invention and optimization, wherein, optimize speed-up ratio refer to optimize before and after the execution time ratio of algorithm, parallel speed-up ratio refers to optimize the execution time ratio of rear algorithm and algorithm of the present invention, total speed-up ratio refers to the execution time ratio of former algorithm and algorithm of the present invention.Experiment draws the average parallel speed-up ratio of algorithm in 1.55 left and right, and overall speed-up ratio is in 3.89 left and right.Wherein parallel speed-up ratio converges on 2 when larger counting, and this parallel overhead that algorithm has been described is less.It can also be seen that the increase of counting along with computing from Fig. 4, parallel speed-up ratio has comparatively stable trend, and it is larger to optimize the speed-up ratio shake.This is because the optimizing process of algorithm has changed the Data Structures of algorithm and carried out flow process, and the process of parallelization does not change the algorithm self structure.As shown in Figure 4, this algorithm is to former Z
3-2Algorithm has stronger accelerating effect, thereby has significantly saved calculation resources, promotes overall performance.
The disclosed technological means of the present invention program is not limited only to the disclosed technological means of above-mentioned technological means, also comprises the technical scheme that is comprised of above technical characterictic combination in any.
Claims (5)
1. parallel algorithm based on the calculating convex hull of multicore architecture is characterized in that comprising the following steps:
(1) find the initial not exclusively convex hull of initial point set, its each limit represents with anticlockwise directed edge;
(2) according to initial not exclusively convex hull, a set is classified, find out all exterior points of each directed edge;
(3) each directed edge in the initial not exclusively convex hull of growth concurrently iteratively;
(4) the non-convex hull summit on the final gained convex hull of deletion.
2. the parallel algorithm of the calculating convex hull based on multicore architecture according to claim 1, it is characterized in that, the implementation method of described step (1) is: find four extreme points along x coordinate, y coordinate direction, delete identical point in these four points, the remaining convex polygon that counterclockwise surrounds of pressing is initial not exclusively convex hull, is designated as LPBCH (S).
3. the parallel algorithm of the calculating convex hull based on multicore architecture according to claim 1, is characterized in that, the implementation method of described step (2) is: the definition determinant
Value for a some P (x, y) to vectorial P
1P
2(P
1(x
1, y
1), P
2(x
2, y
2)) the Yan Shi distance, will join a little in the exterior point set of this directed edge greater than 0 institute with the Yan Shi distance of initial not exclusively each directed edge of convex hull, during the deletion point is gathered, those are not at the point on any directed edge right side.
4. the parallel algorithm of the described calculating convex hull based on multicore architecture of any one according to claim 1～3, is characterized in that, the implementation method of described step (3) is: for each the directed edge P in incomplete convex hull side chain
iP
i+1Carry out concurrently the iteration growth, the process of described iteration growth is:
(a) if directed edge P
iP
i+1The exterior point set be empty, return to the ignore row;
(b) from directed edge P
iP
i+1The exterior point set in find the Yan Shi of this directed edge apart from the some P of maximum, this P must be the convex hull point of point set;
(c) tie point P
iWith a P, some P and some P
i+1, generate two new directed edge P
iP and PP
i+1, to former directed edge P
iP
i+1The exterior point set press directed edge P
iP and PP
i+1Reclassify, obtain respectively directed edge P
iP and directed edge PP
i+1Exterior point set separately;
(d) if directed edge P
iP
i+1The quantity of exterior point set mid point be not more than 2 times of MAXGROW, turn step (f);
(e) iteration growth directed edge P concurrently
iP and PP
i+1Obtain respectively point range L
1And L
2, make point range L={P
i∪ L
1∪ { P} ∪ L
2∪ { P
i+1, turn step (j);
(f) definition chained list E stores some directed edges, with P
iP and PP
i+1Insert E;
(g) for every in E directed edge e, if its exterior point set is not empty, according to (b) (c) methods in two steps obtain two new directed edge e
1And e
2, and e
1And e
2The exterior point set; Delete e from E, and insert e in the position of original e
1And e
2, e wherein
1Identical with the starting point of e;
(h) if (g), the exterior point set of any newly-generated directed edge is not empty, turn step (g);
(i) article one directed edge in deletion E, and make L arrange by the starting point of each directed edge in E the point range that forms;
(j) point range L is as a result of returned;
Wherein, the MAXGROW in (d) be walk abreast, threshold value that serial is selected.
5. the parallel algorithm of the calculating convex hull based on multicore architecture according to claim 1, it is characterized in that, the implementation method of described step (4) is: the every bit in the convex polygon point range that obtains of traversal step (3) successively, if P is current traversal point, R is the forerunner of P, Q is the follow-up of P, if R, P, Q three point on a straight line, just a deletion point P from the convex polygon point range; Through to the once traversal of convex polygon point range, delete the point on all non-convex hulls summit.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210186883.0A CN103116593B (en) | 2012-06-08 | 2012-06-08 | A kind of parallel method of the calculating convex hull based on multicore architecture |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201210186883.0A CN103116593B (en) | 2012-06-08 | 2012-06-08 | A kind of parallel method of the calculating convex hull based on multicore architecture |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103116593A true CN103116593A (en) | 2013-05-22 |
| CN103116593B CN103116593B (en) | 2016-02-10 |
Family
ID=48414970
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201210186883.0A Expired - Fee Related CN103116593B (en) | 2012-06-08 | 2012-06-08 | A kind of parallel method of the calculating convex hull based on multicore architecture |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103116593B (en) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104751519A (en) * | 2015-04-07 | 2015-07-01 | 兰州交通大学 | Efficient construction method for convex hull of planar point set |
| CN106326539A (en) * | 2016-08-17 | 2017-01-11 | 钦州学院 | Variable-takt operation method for simulating two-dimensional product compact layout by using convex hull and rubber band |
| CN106373151A (en) * | 2016-08-26 | 2017-02-01 | 四川大学 | Convex hull obtaining method and device |
| CN110378922A (en) * | 2019-06-10 | 2019-10-25 | 五邑大学 | Smoothed image generation method and device based on auto-thresholding algorithm |
| CN111006638A (en) * | 2019-12-18 | 2020-04-14 | 中国人民解放军海军大连舰艇学院 | Method for optimally selecting territorial sea base points |
Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020050990A1 (en) * | 1998-02-17 | 2002-05-02 | Henry Sowizral | Visible-object determination for interactive visualization |
| CN101377857A (en) * | 2008-07-30 | 2009-03-04 | 电子科技大学 | Method for simplifying three-dimensional model based on octree space division and culmination deletion |
| CN102200962A (en) * | 2011-07-25 | 2011-09-28 | 杭州电子科技大学 | Finite difference stencil parallelizing method based on iteration space sticks |
-
2012
- 2012-06-08 CN CN201210186883.0A patent/CN103116593B/en not_active Expired - Fee Related
Patent Citations (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20020050990A1 (en) * | 1998-02-17 | 2002-05-02 | Henry Sowizral | Visible-object determination for interactive visualization |
| CN101377857A (en) * | 2008-07-30 | 2009-03-04 | 电子科技大学 | Method for simplifying three-dimensional model based on octree space division and culmination deletion |
| CN102200962A (en) * | 2011-07-25 | 2011-09-28 | 杭州电子科技大学 | Finite difference stencil parallelizing method based on iteration space sticks |
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN104751519A (en) * | 2015-04-07 | 2015-07-01 | 兰州交通大学 | Efficient construction method for convex hull of planar point set |
| CN106326539A (en) * | 2016-08-17 | 2017-01-11 | 钦州学院 | Variable-takt operation method for simulating two-dimensional product compact layout by using convex hull and rubber band |
| CN106373151A (en) * | 2016-08-26 | 2017-02-01 | 四川大学 | Convex hull obtaining method and device |
| CN106373151B (en) * | 2016-08-26 | 2019-02-05 | 四川大学 | Convex closure acquisition methods and device |
| CN110378922A (en) * | 2019-06-10 | 2019-10-25 | 五邑大学 | Smoothed image generation method and device based on auto-thresholding algorithm |
| CN110378922B (en) * | 2019-06-10 | 2022-11-08 | 五邑大学 | Smooth image generation method and device based on adaptive threshold segmentation algorithm |
| CN111006638A (en) * | 2019-12-18 | 2020-04-14 | 中国人民解放军海军大连舰艇学院 | Method for optimally selecting territorial sea base points |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103116593B (en) | 2016-02-10 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103116593B (en) | A kind of parallel method of the calculating convex hull based on multicore architecture | |
| WO2023087893A1 (en) | Object processing method and apparatus, computer device, storage medium and program product | |
| CN107977756A (en) | Solve the ternary tree planning computational methods of Three-Dimensional Packing Problem | |
| CN102393826A (en) | Multi-core parallel processing based flexible scene continuous collision detection method | |
| CN115311483A (en) | Incomplete multi-view clustering method and system based on local structure and balance perception | |
| Bai et al. | Pointnet on fpga for real-time lidar point cloud processing | |
| Kim et al. | Efficient multi-GPU memory management for deep learning acceleration | |
| Poostchi et al. | Efficient GPU implementation of the integral histogram | |
| Alimo et al. | Optimization combining derivative-free global exploration with derivative-based local refinement | |
| CN106484532B (en) | GPGPU parallel calculating method towards SPH fluid simulation | |
| CN108256182A (en) | A kind of layout method of dynamic reconfigurable FPGA | |
| CN108108251B (en) | Reference point k nearest neighbor classification method based on MPI parallelization | |
| Kosuge et al. | An object-pose estimation acceleration technique for picking robot applications by using graph-reusing k-nn search | |
| Chaudhary et al. | Parallelism in computer vision: A review | |
| CN103942788A (en) | Hyperspectral remote sensing image characteristic extraction method and device | |
| Feng et al. | Enrich features for few-shot point cloud classification | |
| CN105760478A (en) | Large-scale distributed data clustering method based on machine learning | |
| CN111444007B (en) | Remote sensing big data automatic processing method based on cloud computing | |
| Dass et al. | Distributed QR decomposition framework for training support vector machines | |
| Pasarella et al. | Comparing MapReduce and pipeline implementations for counting triangles | |
| CN116227615A (en) | Quantum search simulation method and system for super computing | |
| CN111860818B (en) | SOM neural network algorithm processing method based on intelligent chip | |
| Ovalle et al. | Distributed Cache Strategies for Machine Learning Classification Tasks over Cluster Computing Resources | |
| CN109003222B (en) | Asynchronous energy-efficient graph calculation accelerator | |
| Xu et al. | A heterogeneous system for real-time detection with AdaBoost |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant | ||
| CF01 | Termination of patent right due to non-payment of annual fee |
Granted publication date: 20160210 Termination date: 20180608 |
|
| CF01 | Termination of patent right due to non-payment of annual fee |