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 []
]
