Skip to main content
Share Your Experience: Take the 2024 Developer Survey
10 votes
Accepted

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

This is likely more complicated than you would prefer, but: Compute the medial axis, which immediately yields the largest disks that fit inside the polygon: their centers are vertices (degree $\ge 3$) ...
Joseph O'Rourke's user avatar
6 votes
Accepted

Converting cartesian pixels to polar pixels

I have implemented the cartesian-to-polar-conversion and have used different interpolation methods: 1) nearest neighbor 2) a subsampling approach, which averages 81 subpixel locations 3) bilinear ...
NodeCode's user avatar
  • 341
6 votes

Rounding corners of polygon given vertices of its corners

Ok, Xenapior and Reynolds together have the right idea. But the explanation is a bit lacking so here is a image to explain it all and some further musings. First let us start by drawing an image (yes ...
joojaa's user avatar
  • 8,437
5 votes
Accepted

How to compute the following integral over a polygon?

Triangulate the Voronoi cell then write the integral as a sum over the triangles: $$\int_{\Omega}\|P - Pi\|\,dP = \sum_{k=1}^{N}\int_{\Delta_k}\|P-P_i\|\,dP.$$ Write the integration over the ...
lightxbulb's user avatar
  • 2,226
5 votes

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

Polygon rasterization (the conversion of the analog polygon data into a raster image) is a key operation in rasterization-based rendering. As such, performing this operation fast, and with predictable ...
Nicol Bolas's user avatar
  • 9,832
4 votes
Accepted

Nomenclature: Other word for non-closed polygon?

I personally wouldn't like to describe non-closed piecewise linear curves as polygons. You might find polyline a better word to describe it. A polyline is a collection of connected straight line ...
Reynolds's user avatar
  • 1,283
3 votes

Vertices of a regular polygon given the incircle radius

what is the relation between radius of the in-circle and circum-circle of a polygon? That is $cos ( \frac{2\pi}{n}*\frac{1}{2} ) = cos ( \frac{\pi}{n})$ The triangle with edges from the center to ...
ratchet freak's user avatar
3 votes
Accepted

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

Since this is a homework question, I'll give hints rather than a numerical answer. Clipping a convex polygon Think about how many times the polygon can cross each edge of the rectangle. In general, ...
trichoplax is on Codidact now's user avatar
3 votes
Accepted

Polygons versus curve primitives in software rendering

Most software rendering engines dice the parametric primitives to micropolygons, usually on the fly as needed. In essence this reduces the needed complexity to determine intersections. The surface ...
joojaa's user avatar
  • 8,437
3 votes

constrain based dynamic geometry generation

It is possible to generate geometry from constraints. However, some of your constraints are hard to formulate as continuous functions that can be minimized or maximized. Also the ones that can be ...
joojaa's user avatar
  • 8,437
3 votes

How to understand Z-Fighting?

The camera does not need to move for this problem to exist. You can see the mixed polygons as in your linked image even with a static camera. Things are worse with a moving camera because it makes ...
Olivier's user avatar
  • 1,585
3 votes

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

There are different numerical approximations you could use: A simple solution is to use brute-force Monte Carlo integration. Distribute $N$ random points on the polygon and calculate the number of ...
JarkkoL's user avatar
  • 3,636
3 votes

Finding the maximum number of disconnected fragments

A convex polygon has the property: A line drawn through a convex polygon will intersect the polygon exactly twice. From this follows that any line trough splits the convex polygon in 2 pieces. ...
joojaa's user avatar
  • 8,437
3 votes
Accepted

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

If you're interested in vertex normals specifically, there's an easy answer even for non-planar polygons that avoids the question of defining what the exact surface is: for each vertex, calculate the ...
Nathan Reed's user avatar
2 votes

Explanation of the Vatti clipping algorithm

{𝑝0,𝑝8,𝑝7,𝑝6} and {𝑝4,𝑝3,𝑝2} are called "left bounds" because if you look at both these bounds, the polygon interior is to the right of them: Likewise, {𝑝0,𝑝1,𝑝2} and {𝑝4,𝑝5,𝑝6}...
Rafael Eyng's user avatar
2 votes

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

If you have GL (or equivalent) available, the easiest way is probably to set up your projection matrix so that the plane of the polygon is the near clipping plane, draw the polygon into the stencil ...
Dan Hulme's user avatar
  • 6,830
2 votes

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

Trying to explain a problem seems to help the thought process. This is what eventually worked for me: I realized that I can easily find the point (in 3D space) where a line between two of the corners ...
SE - stop firing the good guys's user avatar
2 votes

Projection of a Polyhedron on xy Plane with CGAL

A possible way to do this is tracing the silhouette edges of the polyhedron and projecting them to a 2d polygon only at the end of the process. A silhouette edge (in your context) is defined by its ...
Iddo Hanniel's user avatar
2 votes

Rounding a corner formed by Arc and Line

I suppose you want an arc of C0 and C1 continuity between the line and an arc. As illustrated above, you already have a vertex A which is the intersection of an edge and an arc of which the center ...
Xenapior's user avatar
2 votes
Accepted

Back face detection

Now suppose in this case for front face where V and N are parallel to each then they makes angle 0Β°. In your example, V and N are pointing in opposite directions. The angle between them is 180 ...
Nicol Bolas's user avatar
  • 9,832
1 vote

3D object to slices like in medical scan

Some terminology: Intersection of a polyhedron with a plane.                     Wolfram Demo.
Joseph O'Rourke's user avatar
1 vote

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

(Not an answer but my comments are too large for a "comment") This is more computational geometry than graphics. First of all, it would help if you could give an example (a drawing) which describes ...
beyond's user avatar
  • 315
1 vote

Rounding corners of polygon given vertices of its corners

The cut length from the vertex is x*ctan(t/2), where t is the angle at this vertex.
Xenapior's user avatar
1 vote
Accepted

Rounding corners of polygon given vertices of its corners

Since you're working on CAD software, you probably want some precise results. Here an algorithm that could work: For each side: Compute the segment's equation. Compute each round corner's circle ...
bernie's user avatar
  • 830
1 vote

Clipping circle and polygon and generate a CAD drawing

I don't know how the clipping library you are using returns the clipped objects, but if I understand your question, you want a way to represent your circles that does not use much memory? If you are ...
Chuck's user avatar
  • 296
1 vote
Accepted

Finding vertices of the outer contour of intersecting polygons

Sounds like you’re looking for a way to do a Boolean union operation. There’s a couple of algorithms linked from that article that should do the trick.
Noah Witherspoon's user avatar
1 vote

Fill an irregular region with 2D shapes

There is no general algorithm for packing problems. Only some of the special cases have known, and optimal, solutions. If you are packing one shape then finding a reasonable solution is possible. Like ...
joojaa's user avatar
  • 8,437
1 vote

List of triangles to minimum amount of convex polygons

If a edge corner is concave then it needs to border 2 of the output polygons. So one algorithm would be to find all concave corners (including the ones in the holes) and making cuts starting from ...
ratchet freak's user avatar
1 vote

How to understand Z-Fighting?

As others mentioned, z-fighting/stiching occurs even if the camera is not moving. However, when the camera is moving and you're getting z-fighting, it will appear as though the polygons are ...
boni's user avatar
  • 11

Only top scored, non community-wiki answers of a minimum length are eligible