Path: utzoo!attcan!uunet!samsung!zaphod.mps.ohio-state.edu!rpi!wrf From: wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) Newsgroups: comp.graphics Subject: Re: Triangulating concave polygons Message-ID: Date: 6 Jun 90 18:31:34 GMT References: <807@fsu.scri.fsu.edu> <1990May29.212826.3457@everexn.uucp> Organization: Rensselaer Polytechnic Institute, Troy NY Lines: 22 This problem is harder to do fast than you'd think. It's related to the planar graph location problem. (Given a net of polygons, process them so that we can tell which polygon contains a new point). The triangulation can actually be implemented to run in (n lg n) time, I think. Chazelle may have an (n lg* n) method. People think a linear method exists. All these times are from a vague recollection. Actually the easiest way is probably to divide and conquer. Pick 2 nonadjacent vertices and see if they are visible from each other. If so join them and recursively solve the 2 subproblems. If not, keep looking, perhaps by moving to an endpoint of the edge that prevents the 2 original points from seeing each other. Put a counter here to stop the program from infinitely looping. There will always be some pair of visible vertices, but optimization attempts may prevent you from hitting them. -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180