Questions tagged [polygons]

The tag has no usage guidance.

26 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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 (...
Tassle's user avatar
  • 2,522
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 ...
oner ptkh's user avatar
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 ...
Pedro Relich's user avatar
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 ...
Glenn Davis's user avatar
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 ...
smls's user avatar
  • 163
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. ...
Gabe's user avatar
  • 121
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 ...
user avatar
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 ...
user1782685's user avatar
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: ...
Erik's user avatar
  • 21
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 ...
Daron's user avatar
  • 141
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 ...
Ramit Sawhney's user avatar
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 ...
Apurv Mishra's user avatar
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 ...
Jobe's user avatar
  • 11
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-...
OMRY VOLK's user avatar
  • 111
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, ...
Tigertron's user avatar
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 ...
Saelhenen's user avatar
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?
user113413's user avatar
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 ...
Daron's user avatar
  • 141
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 ...
nickolay's user avatar
  • 111
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: ...
Monowar Anjum's user avatar
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 ...
Johannes's user avatar
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 ...
nothacking's user avatar
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(...
Ron Michal's user avatar
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 ...
L42's user avatar
  • 101
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 ...
user avatar
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,...
user340082710's user avatar