luamesh-polygon.lua

   1 -- Given three colinear points p, q, r, the function checks if
   2 -- point q lies on line segment 'pr'
   3 function onSegment(p,q,r)
   4    if(q.x <= math.max(p.x,r.x) and q.x >= math.min(p.x,r.x) and
   5       q.y <= math.max(p.y,r.y) and q.y>= math.min(p.y,r.y)) then
   6       return true
   7    else
   8       return false
   9    end
  10 end
  11
  12 -- To find orientation of ordered triplet (p, q, r).
  13 -- The function returns following values
  14 -- 0 --> p, q and r are colinear
  15 -- 1 --> Clockwise
  16 -- 2 --> Counterclockwise
  17 function orientation(p,q,r)
  18    val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y)
  19    if(val == 0) then
  20       return 0
  21    end
  22    if(val > 0) then
  23       return 1
  24    else
  25       return 2
  26    end
  27 end
  28
  29
  30 -- The function that returns true if line segment 'p1q1'
  31 -- and 'p2q2' intersect.
  32 function doIntersect(p1,q1,p2,q2)
  33    -- Find the four orientations needed for general and
  34    -- special cases
  35    o1 = orientation(p1, q1, p2)
  36    o2 = orientation(p1, q1, q2)
  37    o3 = orientation(p2, q2, p1)
  38    o4 = orientation(p2, q2, q1)
  39
  40    -- gerenal case (without limite case)
  41    if(o1 ~= o2 and o3 ~= o4) then
  42       return true
  43    end
  44
  45    -- Special case
  46    -- p1, q1 and p2 are colinear and p2 lies on segment p1q1
  47    if (o1 == 0 and onSegment(p1, p2, q1)) then return true end
  48    -- p1, q1 and p2 are colinear and q2 lies on segment p1q1
  49    if (o2 == 0 and onSegment(p1, q2, q1)) then return true end
  50    --  p2, q2 and p1 are colinear and p1 lies on segment p2q2
  51    if (o3 == 0 and onSegment(p2, p1, q2)) then return true end
  52    -- p2, q2 and q1 are colinear and q1 lies on segment p2q2
  53    if (o4 == 0 and onSegment(p2, q1, q2)) then return true end
  54    return false; -- Doesn't fall in any of the above cases
  55 end
  56
  57 -- Returns true if the point p lies inside the polygon[] with n vertices
  58 function isInside(listPoints,p,h)
  59    -- if the point is to close to a point of the polygon
  60    for i=1,#listPoints do
  61       if(math.sqrt(math.pow(p.x-listPoints[i].x,2) + math.pow(p.y-listPoints[i].y,2))<0.4*h) then
  62          return false
  63       end
  64    end
  65    -- There must be at least 3 vertices in polygon[]
  66    if (#listPoints <= 3)  then return false end
  67    -- Create a point for line segment from p to infinite
  68    extreme = {x=1e05,y=p.y};
  69    -- Count intersections of the above line with sides of polygon
  70    count = 0
  71    for i=1,#listPoints do
  72       ip = (i)%(#listPoints)+1
  73       -- Check if the line segment from 'p' to 'extreme' intersects
  74       -- with the line segment from 'polygon[i]' to 'polygon[next]'
  75       if (doIntersect(listPoints[i], listPoints[ip], p, extreme)) then
  76          -- If the point 'p' is colinear with line segment 'i-ip',
  77          -- then check if it lies on segment. If it lies, return true,
  78          -- otherwise false
  79          if (orientation(listPoints[i], p, listPoints[ip]) == 0) then
  80             return onSegment(listPoints[i], p, listPoints[ip])
  81          end
  82          count = count+1
  83       end
  84    end
  85    -- Return true if count is odd, false otherwise
  86    return (count%2 == 1)
  87 end