Questions tagged [polygons]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
2 answers
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 + ...
user avatar
  • 3,912
5 votes
3 answers
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 ...
user avatar
4 votes
3 answers
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 ...
user avatar
  • 161
4 votes
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
4 votes
1 answer
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 ...
user avatar
  • 143
4 votes
1 answer
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 ...
user avatar
  • 143
4 votes
1 answer
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 (...
user avatar
  • 2,209
4 votes
3 answers
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 ...
user avatar
3 votes
1 answer
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-...
user avatar
3 votes
1 answer
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, ...
user avatar
3 votes
1 answer
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}$ ...
user avatar
3 votes
1 answer
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 ...
user avatar
  • 133
3 votes
1 answer
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 ...
user avatar
  • 243
3 votes
0 answers
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, "...
user avatar
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
  • 163
2 votes
1 answer
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?
user avatar
2 votes
1 answer
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 ...
user avatar
2 votes
2 answers
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, ...
user avatar
  • 21
2 votes
0 answers
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: ...
user avatar
  • 21
2 votes
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 51
1 vote
2 answers
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 ...
user avatar
  • 121
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 319
1 vote
1 answer
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 ...
user avatar
  • 265
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
1 vote
0 answers
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-...
user avatar
  • 111
1 vote
0 answers
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, ...
user avatar
1 vote
0 answers
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 ...
user avatar
1 vote
0 answers
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?
user avatar
1 vote
0 answers
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 ...
user avatar
  • 131
1 vote
0 answers
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 ...
user avatar
  • 131
1 vote
0 answers
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 ...
user avatar
  • 111
1 vote
0 answers
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: ...
user avatar
0 votes
2 answers
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 ...
user avatar
  • 101
0 votes
1 answer
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 ...
user avatar
  • 133
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 101
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
241 views

Triangulating a simple polygon via its trapezoidal map

Given a trapezoidal map of a simple polygon $P$, is it possible to compute the triangulation of $P$ in $\mathcal{O}(n)$ time?
user avatar
0 votes
0 answers
144 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,...
user avatar