Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complex Polygon Detection

  1. Feb 12, 2009 #1
    Hi, I am working on a simulation code that simulates the deformation of sand grains in 2D. The sand grains are modeled as simple polygons. However, during the simulation the grains can deform to create non-convex vertices. Further more, when deformation becomes extreme, there is a possibility that "self intersection" can occur (the polygon goes from being non-convex to complex).

    My question is then, is there an algorithm that can determine which vertex has "self-penetrated" the polygon? Even if I check for intersections between all edges and determine that the polygon is now complex, I do not know which vertex has penetrated.

    Here's an example where vertex A has "folded"

    Attached Files:

  2. jcsd
  3. Feb 17, 2009 #2
    Do the "well behaviored" polygons have to be convex?
  4. Feb 17, 2009 #3
    All of the grains are initially simple and convex (ie. created using a Voronoi tessellation) . During the simulation, many become non-convex (one or more reflex angles are created) due to deformation. And some could even become complex (have self-intersections). This is what I need to check for and correct.
  5. Feb 17, 2009 #4
    Below is an image sequence of what could happen to a grain. (1) Simple, Convex Grain (2) Non-Convex Grain (3) Complex Grain (self-intersection)


    Attached Files:

  6. Feb 19, 2009 #5
    I'm sorry for the persistence, but does anyone have any insight on this problem?
  7. Feb 24, 2009 #6
    You could try embedding the vertices of your polygon in the complex plane. Choose a function that has pairs of simple poles close to each of the vertices of your polygon such that for each vertex, one simple pole lies in the interior of the polygon and close enough to the vertex, and such that the other simple pole lies in the exterior of the polygon and close enough to the vertex.

    So long as your polygon vertices do not self intersect,

    then only the poles in the interior of your polygon will contribute to the value of the contour integral of the function, where the contour is along the lines of your polygon.

    However, when the vertices intersect, as shown in your diagram, a few more pairs of poles will cross over into the interior region enclosed by the contour of the contour integral in question, and evaluating the contour integral piecewise along each line, will result in a different value, and thereby, in theory at least, detect that a self-intersection has occurred.

    The question remains on how costly, numerically speaking, the above integral is to evaluate in your particular simulation.

    I hope this helps.

    Best Regards,

    Edwin G. Schasteen
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook