# Thread: Detection of edge of a polygon

1. ## Detection of edge of a polygon

I have one polygonal model with sharp edge at one end. Howcan I automatically detect the edge of apolygon? Is there any algorithm available? Thanks.

2. Originally Posted by jenny_wui
I have one polygonal model with sharp edge at one end. Howcan I automatically detect the edge of apolygon? Is there any algorithm available? Thanks.
What do you mean by 'sharp edge'? I can think of two interpretations:
1) the poly does not share this edge with any other polys, or
2) the angle between this poly and a neighboring poly is large (> 10 degs?).

Unshared edges are fairly easy to search for assuming non-redundant vertices.
Just loop through all the edges of the model, checking against all other edges (defined by vertices).
It's not fast, but it's easy to code up. This won't work if you have redundant vertices, which means
vertices sharing the same coordinates. In this case you'd have to do a preprocessing loop to merge
redundant verts.

To find large (up to you to define) angles between neighboring polys, compute the flat normals to
each poly, then compute angles between normals of neighboring polys. In this case the proprocessing
might consist of merging redundant verts, then looping through all polys and edges to figure out which
polys neighbor each other.

Have fun.

3. Thank you very much for the reply. Could you explain"vertices sharing the same coordinates", I didn't get it. I aminterested to find the ends of a polygon. I want to consider a simple case.Suppose i have cylinder with two ends closed. That means the cylinder has twoedges. As the ends are closed, I think your first suggestion won't apply. Ineed to go for second one i.e. 2) the angle between this poly and a neighboringpoly is large (> 10 degs?). Isn't it?

But in my case I am interested about the end edges (if there is any) and edgesare closed. Can I put some other conditions to separate the end edge from theinternal edge? Is there any other solution for the ends? Do I need to checkwhether the vertices form a loop to separate the edges?

4. ....second one i.e. 2) the angle between this poly and a neighboringpoly is large (> 10 degs?). Isn't it?
The angle between the top and bottom faces of a cylinder and the side faces are 90 degs, which is far more than 10 degs.

.... I am interested about the end edges (if there is any) and edges are closed.
I assume you have access to all of the geometric information on this cylinder shaped object. That would include which vertices make up which polygons, and what the x, y, and z coordinates of each vertex is. With this info you can compute flat normals of every polygon making up the object. Do you know how to do this? That would be the first step in identifying which edges are 'sharp'.

Redundant vertices would be two or more vertices at exactly the same coordinates. For example it's quite possible that an extra set of vertices is specified to define the end polygons of a cylinder, even though their coordinates would be the same as the vertices making up the side polygons. This is done intentionally to prevent rendering codes from trying to do smooth shading around sharp edges.

5. Yes, but I am thinking about some more complex model; how can I separate end edges from other sharp corner?? Like cyliner, the end vertices may not always lie on a plane.

6. Originally Posted by jenny_wui
Yes, but I am thinking about some more complex model; how can I separate end edges from other sharp corner?? Like cyliner, the end vertices may not always lie on a plane.
The end vertices of a cylinder do lie in a plane, even if it's not a right, circular, cylinder. Sounds like you have some tube-like structures. Are the ends of the tubes closed or not? You seemed to indicate that they were closed before. If so, what are they closed by - a non-planar polygon? What about the rest of your model? Is it also made up of non-planar polygons?

7. Can I recommend 'Computational Geometry in C' by Joseph O'Rourke - excellent coverage of collision/edge detection with convex/concave shapes (2d) hulls (3d) and a whole host of other things. (£28 on amazon: http://www.amazon.co.uk/Computationa...7326361&sr=1-1) - helped me massively through advanced graphics module at university.

8. If you're working with edges, you should probably use a half-edge data structure to find them quickly and easily.
Then you can start building your own tools upon it.

9. Thank you all for the suggestion. If the edges of the polygon is closed, will still the half-edge data structure will apply? Actually what I wantto do is as follows:
I have a polygonnal data where boundary edges are closed.
There is also some non-boundary sharp edges.
I want to separate only the boundary edges;
closed boundary may be non-planar polygons;

10. Also I would like to know whether the edges form a ring, is any algorithm available for it?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•