Page 1 of 1

drawing a polygon around objects

Posted: Fri Nov 04, 2016 6:31 pm
by danielrr
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

Re: drawing a polygon around objects

Posted: Sat Nov 05, 2016 9:14 pm
by [-hh]
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.]

Re: drawing a polygon around objects

Posted: Sat Nov 05, 2016 9:53 pm
by danielrr
:shock: :D :D

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

Re: drawing a polygon around objects

Posted: Sat Nov 05, 2016 10:33 pm
by [-hh]
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.]

Re: drawing a polygon around objects

Posted: Sat Nov 05, 2016 10:46 pm
by danielrr
:D :D 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.