2
votes
2answers
35 views

Forming a simple polygon from the extrusion of a polygonal chain

Let's say I have a set of vertices connected by edges to form a polygonal chain. Each vertex may be shared by a number of edges to form various sub-chains. An example is shown below. Each edge has ...
2
votes
2answers
112 views

What is inside and outside of complex polygon?

I am reading this paper http://arxiv.org/pdf/1207.3502.pdf Given a complex polygon. Its edges may intersect. The algorithm finds out if given point is inside of polygon or not. It draws a line from ...
1
vote
1answer
31 views

How does one solve arbitrary polygons, in the same sense as one solves a triangle?

Let us say you are given a polygon, and also are given some, but not all, of its angle measures and side lengths. How would one compute the following: If there is a finite number (zero inclusive) of ...
3
votes
2answers
389 views

Algorithm of cutting a polygon into equal parts

I have a convex polygon. I need to divide it into 4 equal parts using the two slit. For example, if I have a square, I have to cut it along the diagonals. Are there some common algorithm for this ...
1
vote
1answer
115 views

Shortest path calculation

I have a given set of start points, a given set of end points. Each start point corresponds to one endpoint. I have to visit all start points, and then the corresponding end points, in the most ...
0
votes
0answers
73 views

First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
2
votes
1answer
83 views

Generalized Straight Skeleton

The straight skeleton of a polygon can be computed by having the edges of the polygon move inwards at a uniform constant speed. Is it useful to generalize this computation process by varying the ...
7
votes
2answers
151 views

How to check if polylines can be untangled?

In a program I'm writing I need to be able to check whether a straight line between two points is homotopic to a polyline between them. For example in the below example the first one is equivalent to ...
0
votes
1answer
107 views

Computing bounding box of polytope (system of linear inequalities)

Given a N real valued variables and a set of linear inequality constraints, I would like to find a minimal bounding box which encapsulates the convex polytope defined by these constraints. I think ...
1
vote
3answers
84 views

Are there any Heron-like formulas for convex polygons?

Are there any Heron-like formulas for convex polygons ? By Heron-like I mean formulas without angles as arguments and which takes as arguments only lenghts of sides of polygon - that is - we know no ...
8
votes
2answers
158 views

Why does the term ${\frac{1}{n-1}} {2n-4\choose n-2}$ counts the number of possible triangulations in a polygon?

In the given picture bellow, it counts the number of different triangloations in a polygon, how do the get to this expression, why is it: $$ {2n-4\choose n-2} $$ and why do we multiply it by ...
3
votes
1answer
720 views

Concave polygons overlapping test

I have set of $N$ concave polygons, given as list of 2D Euclidean coordinates. How to compute: a. if any of them are overlapping? b. if one arbitrarily selected polygon overlaps with any of the ...
1
vote
1answer
82 views

Diagonal of a convex polygon such that the obtained cuts have simmilar areas

Let $P$ be a convex polygon represented with a list of vertices specified by some orientation. Consider the following problem Problem. Find in linear time a diagonal of $P$ such that the absolute ...
2
votes
1answer
784 views

How many rectangles can fit in a polygon with n-sides?

I am trying to write an algorithm to solve a problem I have. I have a few ideas of what the algorithm might be like but I am posting to see if anyone else has a better more efficient solution or any ...