drawing a polygon around objects
Moderators: FourthWorld, heatherlaine, Klaus, kevinmiller
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
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
-
- 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.
[Edit. Improved explanation a little bit and added link.]
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
Last edited by [-hh] on Sun Nov 06, 2016 4:10 am, edited 2 times in total.
shiftLock happens
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
best,
Daniel
-
- 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:
[Edit. Corrected wrong order in explanation in the first paragraph.]
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
Last edited by [-hh] on Sun Nov 06, 2016 4:06 am, edited 1 time in total.
shiftLock happens
Re: drawing a polygon around objects
Thanks, again.
I had arrived at a similar, less elegant solution:
your solution is better.
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