From: Maxime Chupin (escudo) <chupin@fougeriens.org>
Date: Mon, 6 Feb 2017 23:43:37 +0000 (+0100)
Subject: Création du fichier polygon-luamesh avec les outils pour savoir si un point appartien... 
X-Git-Url: https://melusine.eu.org/syracuse/G/git/?p=delaunay.git;a=commitdiff_plain;h=299267d3c929e2afe9bd34ec2617b1ccbf79e14d

Création du fichier polygon-luamesh avec les outils pour savoir si un point appartient à l'intérieur d'un polygone
---

diff --git a/luamesh.lua b/luamesh.lua
index 3ff737b..a2c2608 100644
--- a/luamesh.lua
+++ b/luamesh.lua
@@ -1,3 +1,5 @@
+require "polygon-luamesh"
+
 -- Bowyer and Watson algorithm
 -- Delaunay meshing
 function BowyerWatson (listPoints,bbox)
diff --git a/polygon-luamesh.lua b/polygon-luamesh.lua
new file mode 100644
index 0000000..555ccc6
--- /dev/null
+++ b/polygon-luamesh.lua
@@ -0,0 +1,82 @@
+-- Given three colinear points p, q, r, the function checks if
+-- point q lies on line segment 'pr'
+function onSegment(p,q,r)
+   if(q.x <= math.max(p.x,r.x) and q.x >= math.min(p.x,r.x) and
+      q.y <= math.max(p.y,r.y) and q.y>= math.min(p.y,r.y)) then
+      return true
+   else
+      return false
+   end
+end
+
+-- To find orientation of ordered triplet (p, q, r).
+-- The function returns following values
+-- 0 --> p, q and r are colinear
+-- 1 --> Clockwise
+-- 2 --> Counterclockwise
+function orientation(p,q,r)
+   val = (q.y-p.y)*(r.x-q.x)-(q.x-p.x)*(r.y-q.y)
+   if(val == 0) then
+      return 0
+   end
+   if(val > 0) then
+      return 1
+   else
+      return 2
+   end
+end
+
+
+-- The function that returns true if line segment 'p1q1'
+-- and 'p2q2' intersect.
+function doIntersect(p1,q1,p2,q2)
+   -- Find the four orientations needed for general and
+   -- special cases
+   o1 = orientation(p1, q1, p2)
+   o2 = orientation(p1, q1, q2)
+   o3 = orientation(p2, q2, p1)
+   o4 = orientation(p2, q2, q1)
+
+   -- gerenal case (without limite case)
+   if(o1 ~= o2 and o3 ~= o4) then
+      return true
+   end
+
+   -- Special case
+   -- p1, q1 and p2 are colinear and p2 lies on segment p1q1
+   if (o1 == 0 and onSegment(p1, p2, q1)) then return true end
+   -- p1, q1 and p2 are colinear and q2 lies on segment p1q1
+   if (o2 == 0 and onSegment(p1, q2, q1)) then return true end
+   --  p2, q2 and p1 are colinear and p1 lies on segment p2q2
+   if (o3 == 0 and onSegment(p2, p1, q2)) then return true end
+   -- p2, q2 and q1 are colinear and q1 lies on segment p2q2
+   if (o4 == 0 and onSegment(p2, q1, q2)) then return true end
+   return false; -- Doesn't fall in any of the above cases
+end
+
+-- Returns true if the point p lies inside the polygon[] with n vertices
+function isInside(listPoints,p)
+   -- There must be at least 3 vertices in polygon[]
+   if (#listPoints <= 3)  then return false end
+   -- Create a point for line segment from p to infinite
+   extreme = {x=1e05,y=p.y};
+   -- Count intersections of the above line with sides of polygon
+   count = 0
+   for i=1,#listPoints do
+      ip = (i)%(#listPoints)+1
+      -- Check if the line segment from 'p' to 'extreme' intersects
+      -- with the line segment from 'polygon[i]' to 'polygon[next]'
+      if (doIntersect(listPoints[i], listPoints[ip], p, extreme)) then
+         -- If the point 'p' is colinear with line segment 'i-ip',
+         -- then check if it lies on segment. If it lies, return true,
+         -- otherwise false
+         print("coucou")
+         if (orientation(listPoints[i], p, listPoints[ip]) == 0) then
+            return onSegment(listPoints[i], p, listPoints[ip])
+         end
+         count = count+1
+      end
+   end
+   -- Return true if count is odd, false otherwise
+   return (count%2 == 1)
+end
diff --git a/test/polygon-luamesh.lua b/test/polygon-luamesh.lua
new file mode 120000
index 0000000..2d6109a
--- /dev/null
+++ b/test/polygon-luamesh.lua
@@ -0,0 +1 @@
+../polygon-luamesh.lua
\ No newline at end of file
diff --git a/test/test.lua b/test/test.lua
index e1582e0..846ff8f 100644
--- a/test/test.lua
+++ b/test/test.lua
@@ -22,3 +22,8 @@ end
 listPoints, triangulation = readGmsh("maillage.msh")
 print(#listPoints,#triangulation)
 print(listPoints[2].x)
+
+listPoints = {{x=0, y=0},{x=1,y=0},{x=1,y=0.5},{x=0.5, y=1},{x=-0.3,y=0.3}}
+q = {x=1.5,y=0.2}
+print(q.x)
+print(isInside(listPoints,q))