Questions tagged [polygons]

The tag has no usage guidance.

48 questions
Filter by
Sorted by
Tagged with
1k 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 + ...
• 3,912
2k 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 ...
227 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 ...
• 161
660 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 ...
• 141
1k 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 ...
93 views

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane. the polygons are either convex or star-shaped with a ...
• 143
48 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 ...
• 143
65 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 (...
• 2,209
547 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 ...
163 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-...
466 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, ...
581 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}$ ...
2k 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 ...
• 133
1k 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 ...
• 243
65 views

How to check whether a lattice polytope embeds into another lattice polytope?

Suppose I have two polytopes $P\subset \mathbb R^m$ and $Q\subset \mathbb R^n$ with vertices with integral coordinates. How do I check whether $P$ is embeddable into $Q$? More precisely, "...
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 ...
122 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 ...
51 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 ...
• 131
178 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 ...
• 163
662 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?
• 21
72 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 ...
110 views

How to find simple polygons in a complex polygon created by two lines

Given the image attached, I am looking for a way/strategy/pseudocode to iteratively find each polygon created either by two blue-dotted line segments, a blue-dotted line segment and an intersection, ...
• 21
31 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: ...
• 21
284 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
189 views

Is Dual Graph of a Triangulation of a Polygon Tree?

I have read that; if a polygon contains a hole in it, then the dual graph of a triangulation of the polygon not have to be a tree. But could not get it exactly. How is it possible, what is the ...
• 51
1 vote
68 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 ...
• 121
1 vote
93 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 ...
• 133
1 vote
42 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 ...
• 169
1 vote
194 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 ...
• 319
1 vote
262 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 ...
• 265
1 vote
1k 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 ...
1 vote
19 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 ...
1 vote
28 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 ...
• 11
1 vote
43 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-...
• 111
1 vote
55 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
33 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
75 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
21 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 ...
• 131
1 vote
48 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 ...
• 131
1 vote
34 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 ...
• 111
1 vote
192 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: ...
101 views

Euler polygon division algorithm

I am trying to enumerate and display all possible divisions of an n-polygon into (n-2) triangles (as in the following mathworld ...
• 101
37 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 ...
• 133
104 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 ...
117 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 ...
• 101
81 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 ...
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,...