Intersecting polygons

[danielrr]

I am still enjoying [-hh's] answer to my previous post about creating a polygon around a set of points (aka creating a convex hull of a set of points, a matter I'm still reading about). Now the question arises, and by posting it I'm probably only exhibiting my ignorance, (a) How do I know what's the intersection space between two poligons? and of course (b) How do I code the algorythm to avoid such intersection?, i.e., if I'm drawing two different polygons (convex hulls) surrounding all the points on a surface, how do I avoid the lines of the polygons intersecting with each other?

best,

Daniel

[[-hh]]

Daniel.
Don't know what you mean. A convex hull is _unique_ for a fixed set of points. Could you show us an image/screenshot?

[dunbarx]

Hermann, weren't you heavily involved in a thread a while back that delineated the actual "lines" of a graphic as opposed to the ordinary extent of that graphic. The point being that a polygon's extent is greater than the visible "line" elements that comprise it.

I cannot find that thread, but I bet it will be useful here/

Craig

[danielrr]

Sure. Probably I explained myself poorly. I am sending a screenshoot of my project. You'll see three graphs encompassing different points. Together they include all the points in the map (i's a semantic map, by the way). Graphs are drawn as per your algorythm. As you can see, the blue polygon intersects with the red polygon. Not lethal, but it is not nice to see. I'd like to be able to draw each of the graphs without intersecting the other two (I know, I know, I can place the points in different places but what's the joycin that ). Additionally, I'd be glad to know (for another project) the way to estimate the exact size of the intersected space between two fields in a situation like that.

I hope I explained myseld a little bit better this time.

[[-hh]]

The Area of a non-selfintersecting polygon is already implemented in Raspberry Pi stacks collection #57 (= Sunday game 'Area and Centroid')

For the intersection of convex polygons you may use the by far more general algorithm of Sutherland–Hodgman.

There is also the LC function "intersect" that you could use for checking if there is an intersection.

You may also script the convexHull graphics by

Code: Select all

on mouseDown
    grab me
end mouseDown

Then drag them around and update by script the points and the lines between the 'clusters' (simply change the loc of the graphics).

@Craig. Yes, we had several threads here related to what is inside/outside of graphic shapes. One resulted in 'pointInShape' (Raspberry Pi stacks collection #47).

[danielrr]

Thanks again [-hh] (can't imagine how to spell that) for the Sutherland–Hodgman tip! And for those living the last year under a rock like my own, the RB Pi stacks reference is a pointer to http://forums.livecode.com/viewtopic.php?f=76&t=19248

[[-hh]]

[The first snippet is also for beginners, the second snippet is somehow advanced code, perhaps the wrong subforum for this thread ...]

LC Script snippets ...

• for getting the area of a closed polygon, see the wiki to the math (= shoelace formula).
• for getting the intersection-polygon of a deliberate closed polygon which is clipped by a convex polygon, see the description of the Sutherland–Hodgman algorithm and the Rosetta Code page for the source code in other languages.

Code: Select all

-- returns the area of a closed polygon in px^2 units.
-- not correct for selfintersecting polygons
function hhPolyArea p -- This version: [-hh fecit, Nov 2016]
  put line 1 of p into L1; put 0 into A
  put item 1 of L1 into x0; put item 2 of L1 into y0
  repeat for each line L in p
    if L is empty then next repeat
    put item 1 of L into x1; put item 2 of L into y1
    add x0 * y1 - x1 * y0 to A
    put x1 into x0; put y1 into y0
  end repeat
  return abs(A/2)
end hhPolyArea

Code: Select all

-- Algorithm of Sutherland–Hodgman
-- Returns the intersection of a closed convex poly
-- with a deliberate other closed polygon.
-- The second poly is "clipping" the first.
-- q1=points of the poly being clipped
-- q2=points of the convex clipping poly
function hhClipPoly q1,q2 -- This version: [-hh fecit, Nov 2016]
  -- remove 'closing' for the algorithm
  if line -1 of q1 is line 1 of q1 then delete line 1 of q1
  if line -1 of q2 is line 1 of q2 then delete line 1 of q2
  -- the loop
  put q1 into qOut
  put line -1 of q2 into p1
  repeat for each line p2 in q2
    put qOut into qIn
    put empty into qOut
    put line -1 of qIn into p3
    repeat for each line p4 in qIn
      if insidePolyLine(p4,p1,p2) then
        if not insidePolyLine(p3,p1,p2) then
          put cr & intersectionOf(p1,p2,p3,p4) after qOut
        end if
        put cr & p4 after qOut
      else if insidePolyLine(p3,p1,p2) then
        put cr & intersectionOf(p1,p2,p3,p4) after qOut
      end if
      put p4 into p3
    end repeat
    delete char 1 of qOut
    put p2 into p1
  end repeat
  -- we are done, add 'closing'
  if line 1 of qOut is not line -1 of qOut then
    put cr&line 1 of qOut after qOut
  end if
  return qOut
end hhClipPoly

-- helper function
function intersectionOf t1,t2,t3,t4
  put (item 1 of t1 - item 1 of t2, item 2 of t1 - item 2 of t2) into m1
  put (item 1 of t3 - item 1 of t4, item 2 of t3 - item 2 of t4) into m2
  put item 1 of t1 * item 2 of t2 - item 2 of t1 * item 1 of t2 into n1
  put item 1 of t3 * item 2 of t4 - item 2 of t3 * item 1 of t4 into n2
  put item 1 of m1 * item 2 of m2 - item 2 of m1 * item 1 of m2 into n3
  return ( round((n1*item 1 of m2 - n2*item 1 of m1)/n3), \
        round((n1*item 2 of m2 - n2*item 2 of m1)/n3) )
end intersectionOf

-- helper function
function insidePolyLine t0,t1,t2
  return (item 1 of t2 - item 1 of t1)*(item 2 of t0 - item 2 of t1) > \
        (item 2 of t2 - item 2 of t1)*(item 1 of t0 - item 1 of t1)
end insidePolyLine

Here are two functions that return the points of the example used by the Rosetta Code page. The square is the clipping poly the other is the poly being clipped.

Code: Select all

function points0 -- a square
  put "100,100=300,100=300,300=100,300=100,100" into p
  replace "=" with cr in p; return p
end points0

function points1
  put "50,150=200,50=350,150=350,300=250,300=200,250=150,350=100," & \
        "250=100,200=50,150" into p
  replace "=" with cr in p; return p
end points1

Usage with the above

Code: Select all

put points1() into qq1; put points0() into qq0
set points of grc "intersection" to  hhClipPoly(qq1,qq0)