finding discrète coordinate of Intersection of two convex polygon?

Question

I seek for cartésien coordinate of vertex's of the intersection area between two polygons ? We have two convex polygon's P & Q such that : all vertex of P (resp. Q) are in 2D cartésien plane. I proceeded like that :

• 1 : executing the O'rourke algorithm . // will générate the new convex polygon associated to the intersection of P & Q.

• 2 : Some vetrex haven't an integer coordinate , so every point with non-cartésien coordinate will générate Two other points (with integer coordinate) inculuded to both P and Q.

• 3 : calculing the convex hull of the resulting points set.

Example

Can any one help me to find (an algorithm) out the blue Polygon as a result ?

Answer 1

An algorithm is described in this book (and C & Java code is available):

Computational Geometry in C. (webpage link.)

---

         

---

It's trickier than one might imagine.

---

Added. Now I see that the OP wants the largest lattice convex polygon contained in the intersection of $P$ & $Q$. Perhaps the best method is to intersect $P$ & $Q$ with horizontal lattice lines, find the extreme lattice points on each such line contained in both, and then take the convex hull of all these extreme points.