Intersecting polygons

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

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

Intersecting polygons

Post by danielrr » Sun Nov 06, 2016 1:12 pm

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]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Intersecting polygons

Post by [-hh] » Sun Nov 06, 2016 7:50 pm

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?
shiftLock happens

dunbarx
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 6715
Joined: Wed May 06, 2009 2:28 pm
Location: New York, NY

Re: Intersecting polygons

Post by dunbarx » Sun Nov 06, 2016 9:29 pm

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
Posts: 117
Joined: Mon Mar 04, 2013 4:03 pm

Re: Intersecting polygons

Post by danielrr » Sun Nov 06, 2016 9:35 pm

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 :wink: ). 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.
Attachments
Map2.jpg

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

Re: Intersecting polygons

Post by [-hh] » Sun Nov 06, 2016 11:29 pm

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).
shiftLock happens

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

Re: Intersecting polygons

Post by danielrr » Mon Nov 07, 2016 12:16 am

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]
VIP Livecode Opensource Backer
VIP Livecode Opensource Backer
Posts: 2262
Joined: Thu Feb 28, 2013 11:52 pm
Location: Göttingen, DE

Re: Intersecting polygons

Post by [-hh] » Mon Nov 07, 2016 8:36 am

[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)
Attachments
intersectPoly.png
green: the clipping square, blue: the poly to be clipped
yellow: the intersecting poly (not filled)
red: the convex hull (of the green and blue poly together)
intersectPoly.png (15.55 KiB) Viewed 1927 times
shiftLock happens

Post Reply

Return to “Getting Started with LiveCode - Complete Beginners”