# Questions tagged [polygons]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
897 views

### Partial polygon matching

I am looking for fast procedures for polygon matching, i.e. checking polygon similarity under different transforms translation only, translation + rotation, translation + scaling, translation + ...
1k views

### How can I determine if two vertices on a polygon are consecutive?

Suppose I have a set of points that construct a convex polygon in the Cartesian plane with the points as its vertices. I randomly choose two vertices and want to know if they are consecutive vertices ...
154 views

### Is there an efficient algorithm to extract the farthest ends of a thin contour?

Let's say you have pixel bitmaps that look something like this: From this I can easily extract a contour, which will be a concave polygon defined by a set of 2D points. The question is what is the ...
481 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 ...
43 views

### Check if intersection of several 2D half-planes is empty

I have a large set of half-planes $a_ix+b_iy + c_i \geq 0$. What I need is is the fastest way to determine if they have at least one common point. Currently I build a convex polygon by adding half-...
36 views

### Detecting rotational symmetries of spatial structures

I have a spatial graph-like structure. The structure consists of vertices in the 3D space and connecting edges. Are there any algorithms available that would identify the rotational symmetries of ...
814 views

### Convex-hull of a star shaped polygon in O(n)

I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows: A polygon $P$ is star-shaped if ...
464 views

### Repeated point in polygon: preprocessing complexity given logarithmic query time?

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is ...
296 views

### How to efficiently find line-segment intersections between two sets?

So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, ...
448 views

### Compute visible vertices of a polygon

Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the vertices of $P$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ ...
1k views

### Is a circle inside a polygon?

How do I test if a circle (x,y,radius) is inside a polygon ([x,y],[x,y],[x,y],[x,y]...) without touching the edges? Update I decided to do a point in polygon followed by a circle line collision on ...
870 views

### Finding all faces in a wireframe mesh

I'm trying to find an algorithm for finding all faces in a wireframe mesh. Wireframe means only the vertices and edges are given as input. There is no restriction on the number of edges a resulting ...
21 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 ...
32 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 ...
165 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 ...
42 views

### assign points to non-overlapping rectangles

I have N (~100M) points in 2D and M (~10k) non-overlapping axis-parallel rectangles. I'm looking for an algorithm to assign each point to a rectangle it is contained in (or say that it is outside of ...
297 views

### Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
854 views

### Using visible line segments to compute a visibility polygon

Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the region in $P$ consisting of all points $q$ visible from point $p$. A point $q$ is visible from point $p$, if the ...
25 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: ...
35 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 ...
204 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 ...
51 views

### Efficient rasterisation of vector image with polygons

Imagine I have a 2D area where I have many simple polygons ("simple" meaning not self-intersecting, they are not necessarily concave). A polygon is given to me as a series of points. I have ...
61 views

### Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

The feasible region of a Linear Program (LP) is $\{x \in {\bf R}^n: Ax \le b, x\ge 0 \}$. This is an intersection of halfspaces, a polyhedron. If the LP is bounded and feasible, its optimal value will ...
41 views

### Running time for Testing Polygonal Neighbours for Intersection or Inclusion

I was reading this paper by Shamos, M.I, on "Geometric Intersection Problems" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.366.9983&rep=rep1&type=pdf) , and was trying to ...
62 views

### Convert a polygon mesh into a b-spline surface

$\textbf{Problem:}$ Getting a $\textit{polygon-mesh}$ as input, I have to construct a surface that looks exactly to the given input. My task is to generate a $\textit{b-spline}$ surface that exactly ...
115 views

### Find an edge that is completely visible from point outside a polygon (Convex Hull)

I want to implement algorithms from this paper: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.5609&rep=rep1&type=pdf In particular, I am currently dealing with the one in ...
16 views

### Probable focal point of a set of rays

Given a set of two-dimensional rays, how can I determine the probable focal area of the rays? For simplicity, assume a circle focal area. Imagine a number of people throwing paper airplanes at a ...
27 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 ...
25 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?
10 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 (...
20 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 ...
39 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 ...
33 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 ...
166 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: ...
33 views

### Selecting a polygon within an array of complex polygons

I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram. Unlike a Voronoi diagram I cannot simply find the nearest centroid to select ...
28 views

### Joining points of polygon in correct order

I have a point's array of some 2d shape(polygon). The polygon could be either crossed or convex, I don't know it. And I want to join those points in the correct order. My first thought was to take ...
10 views

### Polygon Subdivision Into Multiple Edge Aligned Grids Containing Maximum Cells

I have a non-convex Polygon which I want to fill with fixed size tiles on a grid such that as many tiles as possible from the grid are wholly contained within the polygon. An additional important ...
Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?
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,...