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.


enter image description here

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


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.

| cite | improve this answer | |
  • $\begingroup$ I tried to understand a bit how is the algorithm described in this book. But I seek a kind of discretization of the set of points of the intersection of two convex polygons. because the research during intersection point we just have points of non-integer coordinates. this is the problem how to ovoide this ? $\endgroup$ – Limeme Ben Ali Apr 4 '15 at 20:33
  • $\begingroup$ @LimemeIbnAli: You cannot avoid non-integer coordinates, as your own example illustrates. Unless you want to approximate the intersection, rather than obtain the exact intersection. $\endgroup$ – Joseph O'Rourke Apr 4 '15 at 23:38
  • $\begingroup$ how it can be done if the two polygons are ConvexLatticePolygon ? I mean by avoid non-integer coordinates, from the intersection result, is obtaining just the convex Lattice polygon. So a point with non-integer coordinate will not be defined in the case? $\endgroup$ – Limeme Ben Ali Apr 13 '15 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.