Intersecting polygons
Moderators: Klaus, FourthWorld, heatherlaine, kevinmiller
Intersecting polygons
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
best,
Daniel

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

 VIP Livecode Opensource Backer
 Posts: 6715
 Joined: Wed May 06, 2009 2:28 pm
 Location: New York, NY
Re: Intersecting polygons
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
I cannot find that thread, but I bet it will be useful here/
Craig
Re: Intersecting polygons
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.
I hope I explained myseld a little bit better this time.

 VIP Livecode Opensource Backer
 Posts: 2262
 Joined: Thu Feb 28, 2013 11:52 pm
 Location: Göttingen, DE
Re: Intersecting polygons
The Area of a nonselfintersecting 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
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).
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
@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
Re: Intersecting polygons
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

 VIP Livecode Opensource Backer
 Posts: 2262
 Joined: Thu Feb 28, 2013 11:52 pm
 Location: Göttingen, DE
Re: Intersecting polygons
[The first snippet is also for beginners, the second snippet is somehow advanced code, perhaps the wrong subforum for this thread ...]
LC Script snippets ...
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.
Usage with the above
LC Script snippets ...
 for getting the area of a closed polygon, see the wiki to the math (= shoelace formula).
 for getting the intersectionpolygon 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
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
Code: Select all
put points1() into qq1; put points0() into qq0
set points of grc "intersection" to hhClipPoly(qq1,qq0)
 Attachments

 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
 green: the clipping square, blue: the poly to be clipped
shiftLock happens