## drawing a polygon around objects

Got a LiveCode personal license? Are you a beginner, hobbyist or educator that's new to LiveCode? This forum is the place to go for help getting started. Welcome!

Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller

danielrr
Posts: 117
Joined: Mon Mar 04, 2013 4:03 pm

### drawing a polygon around objects

Hi all,

I need to build a polygon around an irregullarly distributed group of fields (any number of fields), and make this polygon as fit as possible. I know this is a beautiful exercise in coding, but before giving it the time it really deserves I'll dare to ask: Is there already an algorithm to do that?

best,

Daniel

[-hh]
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

### Re: drawing a polygon around objects

You are asking for Computing the convex hull of a set of points (you could take the topleft, topright, bottomleft and bottomright of each field as points).
There are several algorithms, see
https://en.wikipedia.org/wiki/Convex_hull_algorithms

I have implemented Andrew's monotone chain algorithm in LCS.
You can download a demo stack in the Raspi stack's collection or use (soon) a LCB snippet. Here is the algorithm in LC-Script.

Code: Select all

``````-- Andrew's monotone chain algorithm, see
-- https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
-- This version made by [-hh], Nov 2016.
function convexHull pts0
-- remove empty or duplicates lines
repeat for each line L in pts0
if L is not empty then add 1 to pts1[L]
end repeat
put the keys of pts1 into pts
put the number of lines of pts into N
-- lexicographical sort
sort pts descending numeric by item 2 of each  -- 2nd coord is flipped!
sort pts numeric by item 1 of each
-- split pts for fast access
split pts by cr
-- select upper part of hull
put 0 into k
repeat with i=1 to N
repeat while (k > 1 and crossProduct(H[k-1],H[k],pts[i]) <= 0)
subtract 1 from k
end repeat
add 1 to k; put pts[i] into H[k]
end repeat
-- select lower part of hull
put k into t
repeat with i=N-1 down to 1
repeat while (k > t and crossProduct(H[k-1],H[k],pts[i]) <= 0)
subtract 1 from k
end repeat
add 1 to k; put pts[i] into H[k]
end repeat
-- transform to string in ccw order
repeat with i=1 to k
put cr & H[i] after pts2
end repeat
return char 2 to -1 of pts2
end convexHull

-- ccw if > 0, cw if < 0, collinear if = 0
function crossProduct p1,p2,p3
return  (item 1 of p2 - item 1 of p1)*(item 2 of p3 - item 2 of p1) \
- (item 2 of p2 - item 2 of p1)*(item 1 of p3 - item 1 of p1)
end crossProduct``````
[Edit. Improved explanation a little bit and added link.]
Last edited by [-hh] on Sun Nov 06, 2016 4:10 am, edited 2 times in total.
shiftLock happens

danielrr
Posts: 117
Joined: Mon Mar 04, 2013 4:03 pm

### Re: drawing a polygon around objects

Once again , I stand in awe at the solution. Thanks so much hh!. It's pretty late here, so I'll spend the first hours of the day of tomorrow enjoying your code.

However, as it stands, the code is not flawless: I implemented it thusly:

Code: Select all

``````on mouseUp
put  fld "myFields" into myFields  --each line contains the name of the related fields I want within the same polygon
repeat with x  = 1 to the number of lines of myFields
put line x of myFields into lalin
put "" into losRects
repeat for each item elit in lalin
put the rectangle of fld (elit) & return after losRects
end repeat
put convexHull (losRects) into elPoligono
choose polygon tool
repeat for each line lalin in elPoligono
drag from (item 1 to 2 of lalin) to  (item 3 to 4 of lalin)
end repeat
choose browser tool
end repeat
end mouseUp
``````
For every polygon, the fields of one of the "sides" are left outside the graphic; the polygon is drawn with reference to one of its edges, but not the most extreme of the field.

best,

Daniel

[-hh]
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

### Re: drawing a polygon around objects

For a LiveCoder it is never too late

You take the rectangle, for example "20,30,100,120". This is (left,top,right,bottom)
[LC awaits points and treats these four items as (left,top) & cr & (right, bottom) -- usually wrong because leaving out bottomleft and topright.].
But you have to take the four extreme points topleft, topright, bottomleft and bottomright of each field's rectangle.
A point (x,y) has two items, the x-coord and the y-coord. You can say, for example.
'put (10,20) into myPoint' or 'put "10,20" into myPoint'. And the function convexHull needs lines of points as input. Now this works:

Code: Select all

``````on mouseUp
lock screen; lock messages
put  fld "myFields" into myFields
--repeat with i=1 to the num of flds
--put the short name of fld i into line i of myFields
--end repeat
repeat with x=1 to the num of lines of myFields
put line x of myFields into lalin
repeat for each item elit in lalin
put the rect of fld elit into r -- is (r1,r2,r3,r4)
put cr & (item 1 of r, item 2 of r) & cr & \ -- topleft = (left,top)
(item 3 of r ,item 2 of r) & cr & \ -- topright = (right, top)
(item 3 of r, item 4 of r) & cr & \ -- bottomright = (right, bottom)
(item 1 of r, item 4 of r) after losPoints -- bottomleft = (left, bottom)
end repeat
end repeat
put "convexHullOfFlds" into g
if there is no grc g then create grc g
set style of grc g to "polygon"
set forecolor of grc g to "red"
set points of grc g to convexHull(losPoints)
unlock screen; unlock messages
end mouseUp``````
[Edit. Corrected wrong order in explanation in the first paragraph.]
Last edited by [-hh] on Sun Nov 06, 2016 4:06 am, edited 1 time in total.
shiftLock happens

danielrr
Posts: 117
Joined: Mon Mar 04, 2013 4:03 pm

### Re: drawing a polygon around objects

Thanks, again.

I had arrived at a similar, less elegant solution:

Code: Select all

``````on mouseUp
put  fld "filiaciones" into filiaciones
repeat with x  = 1 to the number of lines of filiaciones
put line x of filiaciones into lalin
put "" into losRects
repeat for each item elit in lalin
put the rectangle of fld (elit) into elRect
put item 1 to 2 of elRect & "," &  item 1 to 2 of elRect & return after losRects
put item 3 to 4 of elRect & "," &  item 3 to 4 of elRect & return after losRects
put item 1 of elRect & "," &  item 4 of of elRect & "," & item 1 of elRect & "," &  item 4 of elRect & return after losRects
put item 3 of elRect & "," &  item 2 of of elRect & "," & item 3 of elRect & "," &  item 2 of elRect & return after losRects
end repeat
put convexHull (losRects) into elPoligono
choose polygon tool
repeat for each line lalin in elPoligono
drag from (item 1 to 2 of lalin) to  (item 3 to 4 of lalin)
end repeat
choose browser tool
end repeat
end mouseUp
``````
your solution is better.