# Questions tagged [polygon]

The tag has no usage guidance.

57 questions
Filter by
Sorted by
Tagged with
3k views

### How to triangulate from a Voronoï diagram?

I computed a Voronoï diagram from a set of points (with Boost.polygon). I try to find a Delaunay triangulation, connecting each cell center for each Voronoï edge, but I miss some edges. In the ...
• 377
5k views

### What is the benefit of using Half Edge over Winged Edge?

For mesh representation, what is the benefit of using Half Edge over Winged Edge data structure? I understand both mesh representations, the only difference is that half edge uses directional edge ...
• 481
2k views

### Pipeline to create Voronoi Meshes

I would like to implement a Maya plugin (this question is independent from Maya) to create 3D Voronoi patterns, Something like I just know that I have to start from point sampling (I implemented the ...
• 201
166 views

### How to describe the bi-directional links for the Weiler-Atherton algorithm?

My postscript interpreter currently implements the Hodgeman-Sutherland clipping algorithm but this is limited to simpler shapes and doesn't have a provision for utilizing various winding-number rules. ...
• 1,343
201 views

### How can I check if a polygon can completely contain a circle of a certain radius?

How can I check if a polygon (can also be irregular) can completely contain a circle of a certain radius? I do not want to actually draw a circle inside the polygon but just a boolean outcome whether ...
• 143
366 views

### Find the longest straight line between two points on surface of polygon

My shape is a slightly concave polygon, and I'd like to know the maximal diameter. I imagine a straight line between two points on the surface of the polygon, such that the line does not pass outside ...
• 191
2k views

### Converting cartesian pixels to polar pixels

(I've largely revamped this entire question, though the motivation remains the same.) revised question I want to convert a raster of cartesian pixels into polar pixels. Is there a sensible ...
295 views

### Finding the angle of any side of a polygon

I'm trying to find the angle it would take for me to rotate a polygon so that a specific side is completely horizontal and on the bottom. For example, a shape like this: Needs to be rotated so the ...
• 163
4k views

### Explanation of the Vatti clipping algorithm

I am going through the Vatti Arbitrary Polygon Clipping Algorithm, but got stuck at their very initial explanation. It says the following: Call an edge of a polygon a left or right edge if the ...
• 1,249
386 views

### List of triangles to minimum amount of convex polygons

I'm in search for an algorithm that takes the left side of the following graphic as an input and outputs a minimal amount of convex polygons as seen on the right side of the graphic. The input mesh ...
• 538
2k views

### Rounding corners of polygon given vertices of its corners

Given a polygon (regular or irregular, convex or concave), I want to round its corner, with a given radius; let's say 'x'. I have the code to draw an arc given 2 points, but how can I find the start ...
• 105
158 views

### Where should I project a polygon corner when it is behind me?

I am creating a simple 3D engine as a learning project to get the hang on spherical trigonometry. I am using the following approach. 1. A model consists of a lot of triangular faces. 2. Each triangle ...
808 views

### Why do polygons have to be "simple" and "convex"?

I'm new to computer graphics and just wanted a solid understanding of why? Why is it so important that polygons you push through the pipeline be "simple" and "convex"?
• 191
130 views

### Vertices of a regular polygon given the incircle radius

How can I find the vertices of a polygon (specifically hexagon) given the radius of the incircle? I want to calculate the vertices of a polygon given the face-to-face distance (inscribed circle ...
• 143
311 views

### Polygons versus curve primitives in software rendering

Most 3D video games since the nineties have used hardware rendering based on polygons. Why polygons? They work well for some things, but not so well for others, e.g. a human figure rendered in ...
• 143
252 views

### Spine. What is the name of the process?

https://www.youtube.com/watch?v=twUz99ek5do&list=WL&index=5 There is a process from 1:51, where the guy start making polygons around the bodyparts. I think this is this part is where (with ...
• 41
133 views

1 vote
141 views

### How to do a scanline fill with a self intersecting polygon?

I have a bezier curve and would like to draw it's stroke. To do that, I planned to approximate the stroke to a polygon and fill it with a scanline algorithm. While I feel confident about implementing ...
• 111
1 vote
56 views

### Convert a polygon mesh to a bspline surface

Problem: Getting a polygon mesh as input, I have to construct a surface that looks exactly to the given input. My task is to generate a b-spline surface that exactly looks like the connected polygon ...
• 131
1 vote
294 views

### How can I convert a shape made out of pixels to vertices

I'm trying to implement the solution to get the minimum dissection into rectangles of a rectilinear polygon. My shape is made out of pseudo-pixels (different width/height) but for the moment let's ...
• 183
1 vote
175 views

### Convert triangulated object to a polygonized object

Is there an efficient algorithm to convert a 3D object described with a set of triangles to a 3D object described with a set of polygons. Polygons can have an arbitrary number of points, more is ...
• 111
1k views

### How to calculate vertex normals on a mesh with non-planar polygons

If I have a mesh consisting of polygons that are not necessarily triangles and not necessarily planar. As answered in the previous question I asked, there's no correct answer to calculating normals ...
• 516
113 views

### HalfEdge: How to get list of all faces from one face

I need to, starting from one face, iterate over the rest of the faces until I reach the first facet. For this I can use twin, start, end or other info of halfedges, faces, vertex. That is, I need to ...
39 views

### Differential or intersection of islands of 2D polygons in different layers

I have a 2D layer/section containing the 2D polygons colored in shades of green. I have another layer containing the 2D polygons colored in shades of blue. I intend to figure out how different are ...
• 133
368 views

### An algorithms for covering a 2d polygon with a predetermined number of rectangles?

I am looking for an algorithm that is able to cover with non-overlapping rectangles in a pre-defined number and minimum area a generic 2d-polygon. Polygons are usually free-hand draws, so they can be ...
• 101
259 views

### Finding vertices of the outer contour of intersecting polygons

I have a bunch of intersecting convex polygons, I want to find vertices of the outer contour of all those polygons. An individual polygon is not self-intersecting. Could you please tell What could be ...
• 105
60 views

### Can STEP files contain polygon data? How do I get a smoother mesh out of a STEP file?

I am trying to work with a .STEP file I have received. Upon opening it in CAD Assistant, I find its surface as jagged lines, like a low poly model. When I export it as OBJ from there, the edges and ...