Questions tagged [polygon]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
14 votes
1 answer
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 ...
arthur.sw's user avatar
  • 377
12 votes
1 answer
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 ...
Bla...'s user avatar
  • 481
10 votes
1 answer
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 ...
Jiloc's user avatar
  • 201
10 votes
0 answers
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. ...
luser droog's user avatar
  • 1,343
9 votes
1 answer
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 ...
user7413's user avatar
  • 143
9 votes
1 answer
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 ...
jiggunjer's user avatar
  • 191
6 votes
2 answers
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 ...
fearless_fool's user avatar
6 votes
2 answers
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 ...
mmmeff's user avatar
  • 163
6 votes
3 answers
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 ...
sajis997's user avatar
  • 1,249
6 votes
1 answer
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 ...
Timm's user avatar
  • 538
5 votes
3 answers
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 ...
user3453636's user avatar
5 votes
1 answer
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 ...
SE - stop firing the good guys's user avatar
4 votes
1 answer
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"?
user9778's user avatar
  • 191
4 votes
1 answer
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 ...
user7413's user avatar
  • 143
4 votes
1 answer
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 ...
rwallace's user avatar
  • 143
4 votes
1 answer
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 ...
Gabor's user avatar
  • 41
3 votes
1 answer
133 views

How to compute the following integral over a polygon?

I am implementing an algorithm which requires me to compute the following integral, $$\int_{Poly(P_i)}||P-P_i||^2 dP$$ where $P_i=(X_i, Y_i)$ is a point in 2D and $Poly(P_i)$ is a polygon containing $...
Student's user avatar
  • 133
3 votes
2 answers
482 views

An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane ...
John Barber's user avatar
3 votes
3 answers
3k views

How to understand Z-Fighting?

I searched for Z Buffer on Google and I discovered that's a 2 dimensional array used by the graphical card and whose aim is to enable the handling of two pixels' depth in order to display one of these ...
user5740's user avatar
3 votes
1 answer
333 views

Maximal and minimal no. of angles obtained from clipping a convex polygon with n angles

I'm trying to figure this out for my Computer Graphics course, but I find it very hard to understand. I believe the minimum number of angles obtained from clipping a convex polygon with n angles is ...
Alex's user avatar
  • 163
3 votes
1 answer
101 views

Finding the maximum number of disconnected fragments

In a plane, we have a convex polygon with n sides. What would be the maximum number of disconnected pieces / fragments if this polygon is clipped against a square?
Sharmishtha's user avatar
3 votes
1 answer
843 views

Rounding a corner formed by Arc and Line

Given shapes like these, which contain just Arcs and lines, I want to round all its corners with certain radius. I know the vertices of the lines & arcs these shapes. I can round the corners of a ...
user3453636's user avatar
3 votes
0 answers
158 views

Generate polygons after marching squares in parallel

I've implemented the marching squares algorithm following Wikipedia's https://en.wikipedia.org/wiki/Marching_squares. The output I got is a set of edges, to which each contouring cell contributes 0, 1,...
Huy Le's user avatar
  • 31
3 votes
1 answer
169 views

Remove clearly not visible vertices from a polygon

For a visibility algorithm I want to remove verts of polygon that are guaranteed not visible from a vert S. The idea is to remove pockets that points are on the backside of a plane formed by the ...
rr84's user avatar
  • 105
3 votes
0 answers
86 views

What is a good algorithm, and framework, to calculate centres of gravity or mass (cog)?

I'd like to take an photograph, subdivide it into a tesselation, either of squares, or (ideally), hexagons, and then find the centre of gravity (or, if you prefer, centre of mass) of each cell of the ...
Peter Brooks's user avatar
2 votes
3 answers
637 views

Clipping circle and polygon and generate a CAD drawing

I'm developing a CAD drawing generator using C# and netdxf library (https://github.com/haplokuon/netDxf) The app first performs boolean operations (specifically - union & subtraction) on polygons ...
user3453636's user avatar
2 votes
1 answer
228 views

Painter's algorithm test 2 and test 3?

TEST #2: Surface S is completely behind the overlapping surface relative to the viewing position. S1 is completely behind/inside the overlapping surface S2 How to check these conditions? i) Set the ...
S. M.'s user avatar
  • 211
2 votes
4 answers
184 views

3D object to slices like in medical scan

I am novice lacking professional terminology. I want to create from 3D object (let's say from polygon mesh) a slice through to PNG file in order to create something like reverse medical MRI scan from ...
Adam's user avatar
  • 21
2 votes
0 answers
54 views

Divide mesh according to level of detail

Background I need to remesh by OpenVDB, like what Blender remesh does: Voxel Uses an OpenVDB to generate a new manifold mesh from the current geometry while trying to preserve the mesh’s original ...
Megidd's user avatar
  • 133
2 votes
0 answers
1k views

Scan Line Polygon Fill Edge Table Entry Order

I am trying to figure out the correct order between edges on edge table on scan line polygon fill. One example here on Y=1 takes first ...
Manuel Pap's user avatar
1 vote
1 answer
187 views

Nomenclature: Other word for non-closed polygon?

In Wikipedia, a polygon is defined as a closed polygonal chain. In other words, the term "polygon" implies that the curve is closed. My question is: Is it common to refer to non-closed, ...
Amos Egel's user avatar
  • 113
1 vote
1 answer
323 views

Back face detection

Suppose I have one convex polyhedron, I need to detect back face. And $N=(A, B, C)$ is normal vector of polygon surface and vector $V$ in viewing direction. According to books formula and internet ...
S. M.'s user avatar
  • 211
1 vote
1 answer
275 views

Projection of a Polyhedron on xy Plane with CGAL

I am trying to project a Polyhedron on the xy plane with CGAL, which should result in a (2D) polygon. I wonder, if there is an elegant way to achieve it? Of course, I can iterate over all surfaces ...
Ctx's user avatar
  • 21
1 vote
2 answers
79 views

Given two non-intersecting polygons, how to determine which one is in front

I have two 3D polygons, and in both of them all vertices are coplanar. I set a viewing direction and transform the polygons into the coordinate system of the viewing direction, such that the x, y ...
Vince W.'s user avatar
  • 111
1 vote
1 answer
111 views

Why do 3d modeling packages use a single normal per polygon and how is this viable for smooth shading

If we have a quad that is non-planar. Why do most 3d modeling packages choose to use a single normal for the quad (Specifically for Blender3d by using cross product of two edge's vectors that do not ...
Lenny White's user avatar
1 vote
1 answer
456 views

Fill an irregular region with 2D shapes

I am creating a 2D CAD drawing generator in C# using .netDXF library. Given a area I want to fill it with rectangles/circles (convex). For example, the regions marked with numbers in below image. This ...
user7413's user avatar
  • 143
1 vote
0 answers
36 views

How to get a polyline from an image with consistent winding number

I am trying to find an algorithm for the following problem. Assume we have a black and white image. The image contains a white region that encloses a space. This space may be concave but it has no ...
Makogan's user avatar
  • 1,696
1 vote
0 answers
54 views

The ploygon width parallel to the x axis as a function of the y ordonate?

Considering a polygon with n vertices as input. I need to calculate the integral of the form \[\int_A p(y) dA \] where $p(y)$ is a piecewise polynomial function of $y$. May be if I could find the ...
Hafid Boukhoulda's user avatar
1 vote
0 answers
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 ...
Julius's user avatar
  • 111
1 vote
0 answers
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 ...
Mohbenay's user avatar
  • 131
1 vote
0 answers
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 ...
JSmith's user avatar
  • 183
1 vote
2 answers
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 ...
Looft's user avatar
  • 111
0 votes
2 answers
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 ...
Lenny White's user avatar
0 votes
1 answer
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 ...
JoungCPPser's user avatar
0 votes
1 answer
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 ...
Megidd's user avatar
  • 133
0 votes
3 answers
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 ...
Randomize's user avatar
  • 101
0 votes
1 answer
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 ...
user3453636's user avatar
0 votes
0 answers
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 ...
Bits168's user avatar
0 votes
0 answers
35 views

AMD GPU specific triangles disappearing by subsequent draw calls in same frame

we have a Windows/DirectX11 2D Renderer that paints textured triangles to the screen from back to front. There is no face-culling or depth test activated. Now on AMD GPUs it happens randomly that an ...
user20154's user avatar
0 votes
0 answers
63 views

How would you represent a mesh with tris and quads?

My understanding is that, while subdivision algorithms like Catmull-Clark can work for any polygonal mesh (including triangles) it's preferable to start with a quad mesh. Currently my rendering engine ...
Chris Gnam's user avatar