Convex hull: Difference between revisions
(Created page with "Find the points which form a convex hull from a set of arbitrary two dimensional points. For example, given the points (16,3), (12,17), (0,6), (-4,-6), ...") |
m (J) |
||
Line 2: | Line 2: | ||
For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15). |
For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15). |
||
=={{header|J}}== |
|||
Restated from the implementation at http://kukuruku.co/hub/funcprog/introduction-to-j-programming-language-2004 |
|||
<lang J>counterclockwise =: ({. , }. /: 12 o. }. - {.) @ /:~ |
|||
crossproduct =: 11"_ o. [: (* +)/ }. - {. |
|||
removeinner =: #~ 1 , 0 > 3 crossproduct\ ] , 1: |
|||
hull =: [: removeinner^:_ counterclockwise</lang> |
|||
Example use: |
|||
<lang J> hull 16j3 12j17 0j6 _4j_6 16j6 16j_7 16j_3 17j_4 5j19 19j_8 3j16 12j13 3j_4 17j5 _3j15 _3j_9 0j11 _9j_3 _4j_2 12j10 |
|||
_9j_3 _3j_9 19j_8 17j5 12j17 5j19 _3j15</lang> |
Revision as of 14:36, 1 June 2015
Find the points which form a convex hull from a set of arbitrary two dimensional points.
For example, given the points (16,3), (12,17), (0,6), (-4,-6), (16,6), (16,-7), (16,-3), (17,-4), (5,19), (19,-8), (3,16), (12,13), (3,-4), (17,5), (-3,15), (-3,-9), (0,11), (-9,-3), (-4,-2) and (12,10) the convex hull would be (-9,-3), (-3,-9), (19,-8), (17,5), (12,17), (5,19) and (-3,15).
J
Restated from the implementation at http://kukuruku.co/hub/funcprog/introduction-to-j-programming-language-2004
<lang J>counterclockwise =: ({. , }. /: 12 o. }. - {.) @ /:~ crossproduct =: 11"_ o. [: (* +)/ }. - {. removeinner =: #~ 1 , 0 > 3 crossproduct\ ] , 1: hull =: [: removeinner^:_ counterclockwise</lang>
Example use:
<lang J> hull 16j3 12j17 0j6 _4j_6 16j6 16j_7 16j_3 17j_4 5j19 19j_8 3j16 12j13 3j_4 17j5 _3j15 _3j_9 0j11 _9j_3 _4j_2 12j10 _9j_3 _3j_9 19j_8 17j5 12j17 5j19 _3j15</lang>