RedCV: Convex Hull

The convex hull problem in geometry applied to image processing tries to find the smallest convex set containing the points. This is useful to process shapes in images for example.

There are many approaches for handling this problem, but for RedCV we focused on the Quick Hull algorithm, which is one of the easiest to implement and has a reasonable expected running time of O(n log n). A clear explanation of the algorithm can be found here: http://www.ahristov.com/tutorial/geometry-games/convex-hull.html. Thanks to Alexander Hristov for the original Java code.

Red CV rcvQuickHull Function

rcvQuickHull

Finds the convex hull of a point set

rcvQuickHull: function [points [block!] return: [block!] /cw/ccw]

points: Input 2D point set as pair!

Returns output convex hull as a block of pair

/cw/ccw : Orientation flag. If cw, the output convex hull is oriented clockwise. Otherwise, it is oriented counter-clockwise. The assumed coordinate system has its X axis pointing to the right, and its Y axis pointing upwards.

Code Sample calling rcvQuickHull

Code uses  generatePoints function to create the set of points as pair!

Code also uses rcvContourArea which calculates the area of polygon generated by rcvQuickHull function.

Data visualization is made with Red Draw DSL in showHull function.

Red [
    Title:   "Test images Red VID "
    Author:  "Francois Jouen"
    File:    %convexArea.red
    Needs:   'View
]

{Quick Hull implementation
Based on Alexander Hristov's Java code
http://www.ahristov.com/tutorial/geometry-games/convex-hull.html}

; all we need for computer vision with red
#include %../../libs/redcv.red ; for red functions

margins: 10x10      
isize: 256x256
nbpMax: 100
nbp: 3
radius: 2.5
cg: 0x0
img: rcvCreateImage isize

plot: copy []
points: copy []

random/seed now/time/precise

generatePoints: does [
    nbp: random nbpMax
    if nbp < 3 [nbp: 3]
    nbpf2/text: form nbp
    canvas/image/rgb: 0.0.0
    plot: copy [fill-pen green]
    canvas/image: draw img plot
    points: copy []
    i: 1
    while [i < (nbp + 1)] [
        p: random 128x128 
        p:  64x64 + p
        append points p
        append plot 'circle 
        append plot p
        append plot radius
        i: i + 1
    ]
    append plot [fill-pen off line-width 1 pen red]
]


showHull: does [
    clear list/data 
    either cb2/data [chull: rcvQuickHull/ccw points] [chull: rcvQuickHull/cw points]
    n: length? chull
    append plot 'polygon
    sumX: 0
    sumY: 0
    ; for centroid
    foreach p chull [append plot p sumX: sumX + p/x sumY: sumY + p/y]
    cg/x: sumX / n
    cg/y: sumY / n 
    
    if cb1/data [i: 1 foreach p chull [append plot reduce ['text p form (i)] i: i + 1]]
    i: 1
    foreach p chull [s: form i append append  s " : " to string! p
                    append list/data s i: i + 1]
    
    if cb3/data [append plot reduce ['fill-pen red 'circle (cg) radius + 1]]
    if cb4/data [
        append plot [fill-pen off line-width 1 pen green line 0x128 256x128 
        pen off pen green line 128x0 128x256]
    ]
    
    canvas/image: draw img plot
    if cb5/data [areaF/text: form rcvContourArea/signed chull]
]


view win: layout [
    title "Quick Convex Hull Area"
    origin margins space margins
    text "Max Number of points"
    nbpf: field 50 data nbpMax [if error? try [nbpMax: to integer! face/data] [nbp: nbp]]
    
    button 80x30 "Generate" [if error? try [nbpMax: to integer! nbpf/data] [nbpMax: nbpMax] 
                          generatePoints canvas/image: draw img plot showHull]
    nbpf2: field 50
    pad 180x0
    button 50 "Quit"    [Quit]
    return
    cb1: check "Show Numbers"
    cb2: check 50 "CCW"
    cb3:  check "Centroid"
    cb4: check 50 "Axes"
    cb5:  check 60 "Area"
    areaF: field 100
    return 
    canvas: base 512x512 img
    list: text-list 100x512 data []
]