Stack Overflow
Stack Overflow

Questions tagged [convex-polygon]

A convex polygon is a simple polygon whose interior is a convex set. In a convex polygon ,every internal angle is less than or equal to 180 degrees and every line segment between two vertices remains inside or on the boundary of the polygon.

99 questions
22
votes
4 answers

Asymptotically optimal algorithm to compute if a line intersects a convex polygon

An O(n) algorithm to detect if a line intersects a convex polygon consists in checking if any edge of the polygon intersects the line, and look if the number of intersections is odd or even. Is there an asymptotically faster algorithm, e.g. an O(log…
infinity_x
  • 223
  • 1
  • 2
  • 4
21
votes
4 answers

Get border edges of mesh - in winding order

I have a triangulated mesh. Assume it looks like an bumpy surface. I want to be able to find all edges that fall on the surrounding border of the mesh. (forget about inner vertices) I know I have to find edges that are only connected to one…
Ross Oliver
  • 1,075
  • 1
  • 11
  • 15
8
votes
3 answers

Smooth a convex polygonal shape so that it becomes as large as possible while retaining diameter

Given a convex polygon, I am trying to grow its shape (as in "maximal area") while preserving its diameter. The diameter is defined as the length of the longest segment that can be placed within the polygon. Since the polygon is convex, I assume…
tucuxi
  • 17,561
  • 2
  • 43
  • 74
8
votes
1 answer

Convex hull in higher dimensions, finding the vertices of a polytope

Suppose I have a point cloud given in 6-dimensional space, which I can make as dense as needed. These points turn out to lie on the surface of a lower-dimensional polytope (i.e. the point vectors (x1, x2, ... x6) appear to be coplanar). I would…
Denor
  • 171
  • 1
  • 8
7
votes
2 answers

Polygon Partitioning vs Triangulation

I recently asked this question about how to cut down a concave polygon to convex ones, and I was suggested to do Triangulation or Polygon Partitioning. The library I'm using (SFML\Box2D) only takes convex shapes. This is what I want to know: Is…
Griffin
  • 2,399
  • 7
  • 48
  • 83
7
votes
2 answers

Algorithm to find if a set of point describes a convex enveloppe

I Would like to check if a set of N points describe a convex polygon or not I was wondering if there is a good algorithm for that ? Here is some approaches I thought of: 1.Convex Hull algorithm : If the set is equal to his convex hull then it's…
Ricky Bobby
  • 7,490
  • 7
  • 46
  • 63
7
votes
2 answers

Scipy ConvexHull and QHull: rank/dimension is not maximal

I am trying to create a Convex Hull using the library Scipy and ConvexHull. As far as I know, it calls QHull. The problem appears when the points I want to add do not have 'full dimension'. Example: from scipy.spatial import ConvexHull import numpy…
Jesus Martinez Garcia
  • 269
  • 2
  • 10
6
votes
2 answers

Find all polygons in points using MATLAB

I have a set of points in the plane and I want to find all convex polygons without including a point inside them. For example I want to find all triangles, all four sized polygons, all four five sized polygons and so on until is possible to find…
jessica
  • 379
  • 8
  • 23
6
votes
2 answers

Algorithm for the decomposition of polygons

Does anyone know a relatively fast algorithm for decomposing a set of polygons into their distinct overlapping and non-overlapping regions, i.e. Given a set of n polygons, find all the distinct regions among them? For instance, the input would be 4…
Hamza Juzer
  • 65
  • 6
5
votes
4 answers

Find max y coordinate of a convex polygon

I have an array V[1,2,....,n], where each element of the array represents a vertex of a convex polygon in the form of a coordinate pair (x,y). It is given that V[1] is the vertex with the minimum x coordinate and that the vertices V[1,2,....,n] are…
Ank
  • 1,864
  • 4
  • 31
  • 51
4
votes
3 answers

How to create Random Geo-Points within a distance d from another Geo-point?

How to get Random Geo-points[ lat/long in decimal], placed anywhere inside a 100 meter radius circle? The center of the circle is another reference GeoPoint. Is there any Function/Formulae that implements this? Basically I am reading the GPS input…
aswin akhilesh
  • 115
  • 2
  • 7
4
votes
0 answers

concave polygon into convex polygons using r

I am trying to split a concave polygon into convex polygons using r. I am trying to figure out how to successfully accomplish this for one polygon with the hopes of implementing this on a large number of polygons in an automated way. The only way…
sea83
  • 81
  • 5
4
votes
4 answers

largest prefix of array of vertices that forms a convex polygon

Related to: Polygon Decomposition - Removing Concave Points to Form Convex Polygons I am looking for an algorithm to do the following: The input is an array of 2D points (P0…PN-1). The length N of the array varies (3 ≤ N < ∞) For any M ≤ N there…
finnw
  • 47,861
  • 24
  • 143
  • 221
4
votes
2 answers

Android Google Maps PolygonOptions not plotted from given set of coordinates

I am trying to plot a complex polygon around a route, following its steps with a given radius. To do so I drew 50-sided uniform polygons (which are practically circles) around each step (coordinate) of the route. Now I obtain a set of coordinates of…
AymanKun
  • 241
  • 1
  • 4
  • 20
1
2 3 4 5 6 7