Libraryless. Click here for Pure Java version (10392L/58K).
1 | // from https://www.geeksforgeeks.org/convex-hull-using-jarvis-algorithm-or-wrapping/ |
2 | |
3 | sclass ConvexHull2D { |
4 | settable IDoublePt[] points; |
5 | gettable L<IDoublePt> hull; |
6 | |
7 | *() {} |
8 | *(Cl<IDoublePt> points) { |
9 | this.points = toTypedArray(IDoublePt, points); |
10 | } |
11 | |
12 | // To find orientation of ordered triplet (p, q, r). |
13 | // The function returns following values |
14 | // 0 --> p, q and r are collinear |
15 | // 1 --> Clockwise |
16 | // 2 --> Counterclockwise |
17 | int orientation(IDoublePt p, IDoublePt q, IDoublePt r) |
18 | { |
19 | double val = |
20 | (q.y_double() - p.y_double()) * (r.x_double() - q.x_double()) - |
21 | (q.x_double() - p.x_double()) * (r.y_double() - q.y_double()); |
22 | |
23 | if (val == 0) ret 0; // collinear |
24 | ret val > 0 ? 1 : 2; // clock or counterclock wise |
25 | } |
26 | |
27 | run { |
28 | if (hull != null) ret; |
29 | int n = l(points); |
30 | hull = new L; |
31 | |
32 | // Less than 3 points -> hull is all points |
33 | if (n < 3) |
34 | ret with addAll(hull, points); |
35 | |
36 | // Find the leftmost point |
37 | int l = 0; |
38 | for (int i = 1; i < n; i++) |
39 | if (points[i].x_double() < points[l].x_double()) |
40 | l = i; |
41 | |
42 | // Start from leftmost point, keep moving |
43 | // counterclockwise until we reach the start point |
44 | // again. This loop runs O(h) times where h is the |
45 | // number of points in the hull. |
46 | int p = l, q; |
47 | do { |
48 | // Add current point to result |
49 | hull.add(points[p]); |
50 | |
51 | // Search for a point 'q' such that |
52 | // orientation(p, q, x) is counterclockwise |
53 | // for all points 'x'. The idea is to keep |
54 | // track of last visited most counterclock- |
55 | // wise point in q. If any point 'i' is more |
56 | // counterclock-wise than q, then update q. |
57 | q = (p + 1) % n; |
58 | |
59 | for i to n: { |
60 | // If i is more counterclockwise than |
61 | // current q, then update q |
62 | if (orientation(points[p], points[i], points[q]) == 2) |
63 | q = i; |
64 | } |
65 | |
66 | // Now q is the most counterclockwise with |
67 | // respect to p. Set p as q for next iteration, |
68 | // so that q is added to result 'hull' |
69 | p = q; |
70 | } while (p != l); // While we don't come to first point |
71 | } |
72 | |
73 | L<IDoublePt> get() { |
74 | run(); |
75 | ret hull; |
76 | } |
77 | } |
download show line numbers debug dex old transpilations
Travelled to 2 computer(s): mqqgnosmbjvj, wnsclhtenguj
No comments. add comment
Snippet ID: | #1036529 |
Snippet name: | ConvexHull2D - Convex hull algorithm for 2D points |
Eternal ID of this version: | #1036529/8 |
Text MD5: | 3dfa2220899be33d53d2804d754f6ed6 |
Transpilation MD5: | 04654fd1374b4cad5509ca914d55eebe |
Author: | stefan |
Category: | javax / gazelle 22 |
Type: | JavaX fragment (include) |
Public (visible to everyone): | Yes |
Archived (hidden from active list): | No |
Created/modified: | 2023-01-23 19:11:39 |
Source code size: | 2283 bytes / 77 lines |
Pitched / IR pitched: | No / No |
Views / Downloads: | 174 / 236 |
Version history: | 7 change(s) |
Referenced in: | [show references] |