The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [polygons]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
78 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 ...
0
votes
1answer
22 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 ...
4
votes
1answer
29 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 ...
2
votes
0answers
26 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 ...
1
vote
0answers
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 ...
2
votes
1answer
179 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?
3
votes
0answers
20 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 ...
1
vote
1answer
71 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 ...
3
votes
1answer
102 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, ...
3
votes
0answers
154 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 ...
0
votes
1answer
150 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?
3
votes
1answer
374 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}$ ...
1
vote
1answer
47 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 ...
2
votes
2answers
689 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 ...
3
votes
1answer
938 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 ...
1
vote
0answers
135 views
4
votes
1answer
371 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 ...
1
vote
1answer
40 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 ...
4
votes
1answer
685 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 ...
2
votes
0answers
161 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 ...
0
votes
0answers
116 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,...
3
votes
1answer
705 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 ...
4
votes
3answers
130 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 ...
4
votes
3answers
379 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 ...
1
vote
1answer
15 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 ...
6
votes
2answers
787 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 + ...