# Tagged Questions

57 views

### splitting polygon in 4 equal parts

I have a convex polygon and I want to divide into 4 equal parts using the two perpedicular splits. Like in a picture. I need s1 = s2 = s3 = s4; I need to get coordinates of point where the lines ...
17 views

### What's wrong with this pseudocode for Forster-Overfelt's version of the Greiner-Horman polygon clipping algorithm?

The Problem I'm trying to understand and implement the Forster-Overfelt version of the Greiner-Horman polygon clipping algorithm. I've read the other Stackoverflow post about clarifying this ...
39 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 ...
118 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 ...
33 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 ...
443 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 ...
117 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 ...
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 ...
93 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 ...
152 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 ...
110 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 ...
86 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 ...
160 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 ...
733 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 ...
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 ...