Convex Hull

Screenshot

Download Model

Download the .scn, .sel and .lse files by clicking on the following link: File:ConvexHull.zip

Model Code Exploration

In the following sections we will examine all of the model files for this model. Note that instead of downloading the zip file above, you could just copy the text in the boxes below into a text editor and save it with the appropriate name (Section title). Opening the resulting .scn file in the SELES simulator would run this model.

MLM.scn

SELES Scenario
$gisData$ = ..\..\CaseStudy_Morice\gisData\cell
StudyArea = $gisData$\BEC
Model Dimensions: StudyArea 
Model.sel
SimPriority Low Priority
//SimStart 100000 1

Model.sel

Seles Model
Time Units: Step kiloStep 1000 100000
Landscape Events:
ConvexHull.lse
Spatial Constants:
StudyArea
Spatial Variables:
ConvexHullPoints[1] <= 0
ConvexHull[1] <= 0
Global Variables:
TRLoc = 0
Output Frequency: 1

ConvexHull.lse

// Sweep-line approach to identifying convex hull using a worker agent
LSAGENT: ConvexHull
DEFINITIONS
 LAYER: StudyArea, ConvexHull, ConvexHullPoints
 GLOBAL VARIABLE: TRLoc
 LOCAL VARIABLE: EndingPivotLoc
 AGENT VARIABLE: PivotLocation, EdgeLocation, EdgeRow, EdgeCol
ENDDEF
INITIALSTATE
  INITIALSTATE = 1
// Find the top-right-most point
  TRLoc = 0
  OVER REGION WHOLE MAP
     DECISION StudyArea > 0
     TRLoc = MAX(TRLoc, Location)
  ENDFN
ConvexHull = 1 // Initialize convex hull layer to all ones (will erase areas outside hull)
ENDIS
NUMAGENTS = 1 // Only need a single worker
// Start on the first pivot vertex on convex hull
AGENTLOCATION
  REGION LOCATION(TRLoc)
ENDAL
PROBINIT
 PROBINIT = 1
// Set up first pivot vertex, and first raster boundary location
 PivotLocation = Location
 EdgeRow = NUMROWS-1
 EdgeCol = COL(Location)
 EdgeLocation = LOCATION(EdgeRow, EdgeCol)
 EndingPivotLoc = -1
ENDPI
TRANSITIONS
 // Continue until we reach the ending pivot location (which is actually second time we hit the second pivot vertex,
 // since the first pivot vertex gets only partially processed on first pass)
 TRANSITIONS = (PivotLocation NEQ EndingPivotLoc)
ConvexHullPoints = 1
// Walk line from boundary to vertex and erase until a new pivot vertex is hit (then move there)
 oldPivot = PivotLocation
 hitPivot = FALSE
 OVER REGION VECTOR(EdgeLocation, PivotLocation)
    DECISION !hitPivot
 IF (StudyArea > 0) // hit new vertex
       hitPivot = TRUE
       IF (EndingPivotLoc EQ -1) AND (Location NEQ PivotLocation)
          EndingPivotLoc = PivotLocation
       ENDFN
       PivotLocation = Location
    ELSE
       ConvexHull = 0 // erase
    ENDFN
 ENDFN
// Move boundary location clockwise around outside edge of raster
 IF (EdgeRow EQ NUMROWS-1) AND (EdgeCol < NUMCOLS-1)
    EdgeCol = EdgeCol + 1
 ELSE IF (EdgeCol EQ NUMCOLS-1) AND (EdgeRow > 0)
    EdgeRow = EdgeRow - 1
 ELSE IF (EdgeRow EQ 0) AND (EdgeCol > 0)
    EdgeCol = EdgeCol - 1
 ELSE
    EdgeRow = EdgeRow + 1
 ENDFN
 EdgeLocation = LOCATION(EdgeRow, EdgeCol)
ENDTR
POPULATIONTIME = 1
// Move to current/new pivot location
MOVELOCATION
 REGION LOCATION(PivotLocation)
ENDML

Suggested Experiments

To explore this cellular automata model further, try the following: