Questions tagged [polygons]
The polygons tag has no usage guidance.
26
questions with no upvoted or accepted answers
4
votes
1
answer
102
views
Can we find the largest intersecting subfamily of convex polygons in quadratic time?
Let $\mathcal{F} = \{P_1, P_2,\ldots,P_m\}$ be a family of (closed) convex polygons in the plane, each represented by their vertices in (say) clockwise order. Let $n$ be the total number of vertices (...
3
votes
0
answers
26
views
Algorithm to separate single contour of glyph into several strokes?
A glyph contour contains points set {p}, a point contains tuple (x,y,on_curve).
Now, think about this need, converting contour of glyph X, for example, into to two contour parts or two strokes, point ...
3
votes
0
answers
197
views
Overlay two Voronoi Diagrams and calculate membership and areas of intersecting polygons
I would like to generate a composite diagram of two Voronoi diagrams. I'm currently researching the cgal library for options, but I'm not sure if my precise application is covered.
Basically, I have ...
3
votes
0
answers
70
views
area of the projection of a mesh
Given:
a quadrilateral mesh that forms the surface of a sphere
a linear projection from 3D to 2D (a 2x3 matrix)
The mesh is not convex in general, but it is regular enough
that we know that the ...
3
votes
0
answers
187
views
Construct polygons from axis-aligned intervals
Scenario
Consider one or more curved shapes in 2D space, clipped to a rectangular viewport. For example:
Unfortunately, data that would describe these shapes precisely, is not available.
Input data
...
2
votes
0
answers
31
views
Minimum time inpainting a polygon with constraints
Given are the coordinates of a convex polygonal area ("field"), a moving circle of radius r ("crayon") and a home location for the crayon ("home") well outside the field.
...
2
votes
0
answers
49
views
Minimal bounding quadrilateral of a convex polygon
I am looking at the problem of finding the quadrilateral of minimum area that encloses a convex polygon.
I found the following articles:
An Optimal Algorithm for Finding Minimal Enclosing Triangles ...
2
votes
0
answers
29
views
Find simple polygon with most guards outside of it
I’ve been researching an optimal strategy of playing in mobile game of Ingress and came up with an interesting (for me) computational geometry problem.
Statement of the problem: You’re given N ...
2
votes
0
answers
35
views
Efficient parameterization of low vertex count polygons
I'm trying to design a method to represent polygons as vectors. There are many ways to do this, but I have a few goals and I'm not sure what representation is best to fulfil these. The objectives are:
...
2
votes
0
answers
63
views
How Expensive is Projecting onto a Polytope?
I have a problem where our action set is a polytope $\mathcal P\subset \mathbb R^d$ and an algorithm that involves projecting onto the action set. For example it says to select the Euclidean ...
2
votes
0
answers
354
views
Modified Sutherland Hodgeman Algorithm
I'm familiar with applying the sutherland hodgeman algorithm for convex polygons(and even concave polygons with a slight modification) against convex clipping windows.
However, if I am to modify the ...
1
vote
2
answers
47
views
Locating a sequence of 2D points in a set of polygons with holes
Using the CGAL library, I am working on a 2D layout graph which contains an array of 2D polygons with holes. The aim is to generate random points (based on some conditions) and only keep the points ...
1
vote
0
answers
48
views
When Triangulating monotone polygons, how can diagonals be added to a DCEL in constant time?
I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4.
I've managed to turn polygons into y-monotone polygons ...
1
vote
0
answers
63
views
An algorithm to split an area into multiple polygons based on other polygons intersection
I have a list of n polygons (A,B,C,D,E,...) which possibly intersect each other.
I need to find a new list of polygons (or multi-...
1
vote
0
answers
148
views
What are the correct steps in solving polygon monotone triangulation?
I am working out step by step and I am stuck on vertex 7. I got that it was a regular vertex and helper(e_i-1) is not a merge vertex so I look for the leftmost edge in the sweep line. My question is, ...
1
vote
0
answers
52
views
Find closest points in a polygon
I have a 2D polygon defined by a list of $n$ points: $A$, $B$, $C$... These points are sorted in clockwise order. Example:
I would like to find the most performant algorithm to detect all points ...
1
vote
0
answers
87
views
If a polygon is monotone with respect for a line, how can I determine the two monotone polygonal chains?
I need to determine the two monotone polygonal chains of a y monotone polygon.
I have the vertices stored in an array.
How can I do this?
1
vote
0
answers
22
views
Is there a way to *round* a nearby point into the feasible set?
Let $P \subset \mathbb R^d$ be a polytope with interior given by $F$-many linear inequalities. Suppose we have a convex problem with feasible set $P$. For example computing the Euclidean projection of ...
1
vote
0
answers
39
views
Cover a polygon with least amount of parallelograms
I am solving the task that is as follows:
Input: a polygon. Can be any kind of polygon without self intersections. Can be a non-convex and with holes inside.
Goal: to cover it with 2 (at least) or ...
1
vote
0
answers
218
views
Computational Geometry: what is the key of the BST in the algorithm " Partitioning a polygon in y-monotone pieces"
The algorithm to partition a polygon into y-monotone pieces is as follows:
...
0
votes
0
answers
15
views
Algorithm for surface mesh of convex decomposition
I have an object mesh. This is loaded into a physics simulator, which does a convex decomposition. Now I want to perform operations outside the simulator that require a mesh representation. I could ...
0
votes
0
answers
13
views
Compute the intersection and difference of multiple polygons
I have multiple (possibly concave) simple polygons, and need to compute the union and difference of them, some polygons have to be added, some subtracted from the final shape. I have found algorithms ...
0
votes
0
answers
57
views
Points in convex d-dimensional polytope
Given a set of points, and a convex d-dimensional polytope represented only by a set of its' vertices, I need to query in order to check for each point if it's inside the polytope. I know of the O(log(...
0
votes
0
answers
1k
views
Algorithm for dividing a polygon into rectangles?
I have a polygon as a set of coordinates (fex [(0,0), (1,0), etc.). I'd like to find a way to divide this into as few rectangles as possible. The background for this is that I wish to have a user ...
0
votes
0
answers
388
views
How to determine the number of active linearly independent constraints in a basic feasible solution for linear programming?
I am trying to determine if a given solution is a basic feasible solution. I am working with an $n-$dimension polyhedron $P$ defined by a set of $M$ inequalities $Ax \leq B$. I am running into an ...
0
votes
0
answers
206
views
Algorithms for Counting Number of Triangulations of a Simple Polygon
Recently, I was asked to design an algorithm that counts the number of triangulations in a simple polygon without Steiner points. This is pretty simple to do in $O(n^3)$ time using dynamic programming,...