3

I want to divide a self-intersecting polygon into simple polygons. I have the edges and the intersection points saved in a data structure (a connected list).

So here is an example. I have a connected list with the x,y coordinates of the edges and the intersection points of the polygon. According to the polygon in this picture it would be :: (1) -> (2) -> (3) ... -> (7). What I'm trying to do is to get the edges of the simple polygons (triangles here). In this case :: 1,2,7 / 3,4,5 / 5,6,7.

Chau
  • 5,540
  • 9
  • 65
  • 95
ItsMe
  • 31
  • 1
  • 2
  • 1
    I suggest you flesh this question out a bit more, at least showing the data structure with an example and maybe what you have started. Welcome to SO. – Dusty Nov 07 '10 at 00:27

1 Answers1

3

I would think that Bentley-Ottman would be your best bet. There's a nice interactive visualization here. Another nice description here.

MPG
  • 835
  • 4
  • 10