19
votes
Accepted
How to triangulate from a Voronoï diagram?
The centre point in your diagram is a degenerate edge of the Voronoi diagram. If you generate a Voronoi diagram for an irregular point cloud, every vertex will have degree 3. A vertex with degree 4 (...
- 2,710
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$) ...
- 341
8
votes
Accepted
What is the benefit of using Half Edge over Winged Edge?
As far as I can tell, the main advantage of half-edge is that traversal can be a bit simpler due to a guarantee of edges having a consistent orientation within each face.
Consider the problem of ...
- 24.4k
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 ...
- 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 ...
- 8,317
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 ...
- 9,389
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 ...
- 1,951
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 ...
- 8,317
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 ...
- 8,317
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 ...
- 5,850
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, ...
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 ...
- 3,596
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 ...
- 1,585
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.
...
- 8,317
3
votes
Spine. What is the name of the process?
This appears to be simply skeletal animation, which is a standard technique that is available in all modern animation packages. Whether applied to 3D meshes or (as here) 2D ones, the principle is the ...
- 24.4k
3
votes
Accepted
Finding the angle of any side of a polygon
Deducing the angle and rotating by that angle works quite well in 2D (describe in TLousky's post). This strategy, does not extend very well into three-dimensional realm. I will provide an alternative ...
- 8,317
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 ...
- 24.4k
2
votes
Finding the angle of any side of a polygon
This algorithm is based on this answer for finding the angle between vectors, and this answer for rotating polygon points. It's written in Python, and assumes you want to align an edge with the X axis ...
- 199
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 ...
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}...
- 121
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 ...
- 6,650
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 ...
- 27
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 ...
- 166
1
vote
Clipping circle and polygon and generate a CAD drawing
If Clipper has the capability of working with tagged edges (i.e. such that you can associate some label to every edge of the input polygons and retrieve these labels after clipping), then you can tag ...
- 687
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 ...
- 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.
- 2,087
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.
- 27
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 ...
- 810
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 ...
- 8,317
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 ...
- 5,850
Only top scored, non community-wiki answers of a minimum length are eligible