2
votes
0answers
45 views

area estimation with tiling

For any given shape drawn on a graph paper, a kid can calculate the area of any shape by counting the tiles with a simple formula: any edge covering 50% or more, mark the tile; total area = sum all ...
0
votes
1answer
30 views
+150

Defining ellipse using points and normal vectors from them

There is an article on how to detect circles in images using pairs of gradient vectors (assuming the circle is dark and background is bright). The thing is that gradient of image intensity at each ...
0
votes
0answers
26 views

Find a point C on line segment AB such that line segment DC is perpendicular to AB. D is a point outside the line segent

Find a point C on line segment AB such that line segment DC is perpendicular to AB. D is a point outside the line segment. Note, Point A,B and C are in latitude,longitude format, i.e A = {lat,long} ...
0
votes
1answer
23 views

Given N points with integers coordinates find the number of parallel lines

nC2 will give the number of lines we can form in O(n^2) complexity. Finding the slope of these lines in O(n^2) complexity and store them in an array, say x. Sort x in O(n^2 logn) complexity. Search ...
0
votes
1answer
36 views

Algorithm - the longest chord whose supporting line contains a given point, in a convex polygon

"Let $P$ be a convex $n$-gon and $q$ a point in the plane. Find an algorithm to compute the longest chord whose supporting line contains q." When $q$ is external to $P$, I think I can prove the ...
1
vote
2answers
27 views

algorthm to find a farthest point in a convex polygon to an external point

Given a point $q$ external to a convex polygon $P$, propose an algorithm to compute a farthest point in $P$ to $q$. One can always have at least one vertex of $P$ in the set of farthest points of $P$ ...
3
votes
1answer
29 views

algorithm to find closest point in a convex polygon from an external point

Given a convex polygon $P$, and a point $q$ of the plane, external to $P$, what is the fastest algorithm to compute the closest point in $P$ to $q$. A linear algorithm of course works, computing the ...
1
vote
1answer
46 views

Given the coordinates of four points on a plane, how can one determine the shape they form?

Actually it is an algorithm problem, however I cannot solve the problem. So, We have 4 points, how can we know what kind of shape(figure) can be drawn ? I want to learn mathematically. If possible i ...
2
votes
3answers
46 views

How to check a polygon in $\mathbb{R}^2$ for convexity.

Given $n$ points in $\mathbb{R}^2$, $\{p_1,p_2,\ldots,p_n\}$, how do we test if the (interior of the) polygon formed by drawing the line segments $[{p_{i-1},p_i}]$ for $1\le i \le n$ and also ...
1
vote
0answers
34 views

Count balls to put in triangle

Given balls of radius $R$ we need to find how many balls can be put into a triangular container with sides $a,b$ and $c$. Example : Let $R=1$ and $a=3,b=4$ and $c=5$ then answer is $1$, as only one ...
1
vote
2answers
40 views

When is a point in the plane inside a simple closed path?

Suppose I have a simple closed curve $\gamma(t)$ in the plane. In general, how do I tell if some point $p$ is inside or outside this curve? For example say $\gamma(t) = (2 \cos(t), \sin(t) + ...
0
votes
1answer
18 views

Labeling of cells from 2D plane division by lines

My question is about a labeling scheme for the cells (convex polygon regions) resulting from the division of a 2D plane by a set of lines. I am seeking answer for the Euclidean (flat) 2D plane, ...
0
votes
1answer
29 views

Selecting a random orthogonal polygon

For a certain demo application, I want to create at random a rectilinear polygon with a given number of corners. Selecting random $x$ and $y$ coordinates of each corner is not a good method, since ...
1
vote
1answer
38 views

Pack rectangular objects of different sizes in a fixed size rectangle

If this has been asked before, please help me find it, I have scoured Math.stackexchange and have found quite similar questions but not exactly what I am looking for. I have a rectangular space. I ...
1
vote
1answer
32 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 ...
3
votes
2answers
49 views

Largest Equilateral Triangle in a Polygon

Is there an algorithm to determine the largest equilateral triangle in a convex polygon?
1
vote
1answer
71 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
5
votes
1answer
81 views

filling an occluded plane with the smallest number of rectangles

I've got a specific problem which I'll try to describe as clearly as possible. I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular ...
4
votes
1answer
146 views

Find if a point lies in all given circles

I have a set of n given circles. I want to find that if there exists at least one point that lies in all of the given circles. Is there a method to do so? I can ...
0
votes
1answer
71 views

Finding end point of straight line given starting point and angle

I have a program which computes the angle of skew of a scanned photograph. It returns the angle of skew in degrees. I now need to draw lines across the image which follow the angle of skew. These ...
0
votes
0answers
16 views

Unrolling and rerolling with a different thickness

I have two rolls, the main one with two layers of material and the secondary one with just one of them. As the main one unrolls it loses one layer of thickness, and simultaneously the second one has ...
0
votes
0answers
38 views

Finding the point satisfying the condition

Given N interesting points on the plane. Each interesting point has integer coordinates. Also, all the interesting points form a strictly convex polygon. If we select two coordinates from these ...
2
votes
2answers
62 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 ...
1
vote
2answers
63 views

Does anyone know of any open source software for drawing/calculating the area of intersection of different shapes?

I would like to be able to draw any number of different shapes and determine the area of their intersections. I'm looking for free, open source software. I thought about trying to code something up ...
0
votes
0answers
17 views

Fitting by an ellipsoid with a known center?

Consider a set of $N$ points in 3D of coordinates : $$p_{i} = \left\{x_{i}, y_{i}, z_{i} \right\}$$ The very general question I ask is : how to fit these points by the surface of an ellipsoid ...
2
votes
2answers
147 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 ...
0
votes
0answers
12 views

Proof for finding isothetic cover with minimum verteces

I have given an Inner Isothetic Polygon and outer isothetic polygon. now I have to make an Isothetic polygon which will lie in the region between Inner isothetic polygon and outer isothetic polygon ...
2
votes
2answers
32 views

Slicing up geometry to create triangles

When rendering object onto a screen, one must often cut up their objects into quads and triangles to allow the computer to process them and finally draw them onto a screen. I am trying to slice up a ...
0
votes
0answers
10 views

Determining the minimal number of axis to test against in the SAT (Separating Axis Theorem)

Most implementations of the SAT algorithm I've seen involve testing each axis in either shape being tested against for collisions. But I recently implemented the SAT algorithm in python and noticed ...
0
votes
1answer
34 views

How to test for a polygon witn n vertices if it's nonintersecting polygon or not?

How can you design an algorithm to know if an n-vertex polygon nonintersecting ? On what criteria is the test going to be
3
votes
1answer
96 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
1
vote
1answer
34 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 ...
0
votes
1answer
37 views

Construct the polygon

Given N number of Pipes of length L1 , L2 ,L3 , …... LN. Using these pipes,which can only be joined end to end (such that they can move freely in a 2-D plane only about the pivot/point of ...
0
votes
1answer
306 views

Working algorithm for testing two rectangles for overlapping in Earth GPS coordinates plain

Here is a seemingly simple, but actually quite tricky problem: I am trying to figure out the correct algorithm to test intersection/overlapping of two rectangles, which are plotted on the Earth's ...
0
votes
0answers
62 views

Calculate the fraction of volume of a rectilinear grid cell within some radius of the origin

I have a sphere (radius $R$) on a rectilinear grid. Some cells intersect the edge of that sphere, call them 'edge cells'. Designate a given cell by indices $[i,j,k]$ which refer to the lowest-index ...
0
votes
1answer
50 views

Number of ways to make grid

I need to construct a L x 3 grid as shown below But i can use only two shapes to make it which are : Here L is the number of small square boxes in each row. I can rotate the shapes as I want. I ...
0
votes
1answer
19 views

How to identify a variable-sized zone by a point given by coordinate?

The Cartesian plane is partitioned into zones of variable sizes. A zone is always a rectangle. For example, a zone can be represented like $x \in (0, 3], y \in (30, 50]$ The range in the Cartesian ...
5
votes
3answers
71 views

Name of the generalization of quadtree and octree?

What is the name of the equivalent of quadtrees and octrees in n-dimension ?
0
votes
2answers
37 views

Room for computational geometry in advanced algorithms course

I am currently putting together an independent study in advanced algorithms and because of my interest in (computational) geometry, wanted to include as many interesting algorithms from this field as ...
1
vote
0answers
112 views

Number of classes of K-sets

I am having a plane in N dimension. Th distance between 2 points (a1,a2,...,aN) and (b1,b2,...,bN) is max{|a1-b1|, |a2-b2|, ..., |aN-bN|}. I need to to know how many K-sets exist(here K-set refers to ...
1
vote
2answers
86 views

Calculate geometry created by “slicing” rectangle with lines

Given a rectangle with a series lines intersecting it, how would you calculate the points of each individual shape created? In this particular application that we are working on, the user can "slice" ...
0
votes
0answers
188 views

Maximum Area of rectangle without any monsters

Given a rectangular grid of N*M (1-based indexing) in which their are k monsters on k different cells.Now we need to answer Q queries in which we will be given lowest row number(L) and highest row ...
0
votes
1answer
152 views

given point lies inside or outside a polygon

I was trying this question and found a solution : Draw a horizontal line to the right of each point and extend it to infinity ...
1
vote
1answer
63 views

Determining box-box intersection without cross product

Does anyone know a way to correctly determine if an axis-aligned box intersects with an oriented (using any invertible square matrix) box in a space with three or more dimensions, without using cross ...
1
vote
1answer
56 views

Which icosahedral triangles projected onto sphere's surface contain points in P?

I am working on a Python script to: Compute the vertex coordinates of a geodesic sphere/icosahedron, Project the triangles onto a sphere, then Find which spherical triangle contains an arbitrary ...
2
votes
0answers
107 views

Megiddo's algorithm for lines of least weighted sum distance from a set of points

I came across the following problem: Given a set of n points (coordinate in 2d plane) within a rectangular space, find out a line ($ax+by=c$), from which the sum of the perpendicular distances of all ...
0
votes
1answer
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
1answer
141 views

How to generate the n-simplex?

I was following this wikipedia section, in the simplex article to see if I could create a MATLAB algorithm to generate a simplex with $n$ points in $3$-dimensional space. Sure enough it works for 4 ...
3
votes
0answers
49 views

Selecting k vectors with maximum spread out of a set of n vectors

Given a set $\mathcal{V}$ of $n$ vectors, find a subset $\mathcal{V}_k = \mathcal{V} - \mathcal{V}_{n-k}$ containing $k$ maximally spread vectors. Intuitively, these $k$ vectors should be spread as ...
1
vote
1answer
120 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 ...