If O(n^3) is permissible, then the following works:
--
If we can find one point that falls on such a line, then it is easy to
find the other points
because the slope between this point and all other points that fall on
this line wi
On 6/14/07, Monu Rathour <[EMAIL PROTECTED]> wrote:
>
> There are some rectangles and some pin-vertices's in a two dimensional
> plane. I have to join pin-vertices's such that lines are rectilinear and
> line should not cross over the rectangles.
>
> How to write a mathematical formula for calc
Please anyone help me..
On 6/15/07, monu <[EMAIL PROTECTED]> wrote:
>
> I am given the co-ordinates of rectangles and pin-vertices's as ( Xi,
> Yi ) where i lies b/w 1 to n. Now i have to write formula in terms of ( Xi,
> Yi ) .
>
> Please help me
>
> On 6/15/07, Victor Carvalho <[EMAIL
I am given the co-ordinates of rectangles and pin-vertices's as ( Xi,
Yi ) where i lies b/w 1 to n. Now i have to write formula in terms of ( Xi,
Yi ) .
Please help me
On 6/15/07, Victor Carvalho <[EMAIL PROTECTED]> wrote:
>
> I know how to do a easier variation of this problem, is not
I know how to do a easier variation of this problem, is not a simple
problem, I think I can help you only with a start point... :)
1) Do you perceive that I can firstly calculate the shortest distance
between 2 points based on lines and the rectangle edges, ok?
You take all the paths with all ar
Please anyone help me..
On 6/14/07, Monu Rathour <[EMAIL PROTECTED]> wrote:
>
> There are some rectangles and some pin-vertices's in a two dimensional
> plane. I have to join pin-vertices's such that lines are rectilinear and
> line should not cross over the rectangles.
>
> How
Right, by splitting ( O(log(N)) ) the polygon into two chains at two
extremes can avoid removing vertexes.
Actually following this idea, I found a simpler algorithm:
1. Take arbitrary 3 vertexes (say A,B,C) that can split the polygon
into 3 more or less equally sized chains. These 3 vertexes for
I think a sequence of vertices in (counter)clockwise order with
constant time access by index will well suffice. Below I assume the
counterclockwise order, which I prefer in most cases.
My approach is to first split the polygon into two chains of vertices
at two extremes with respect to the direc
I agree with you, it not correct to say it does not take O(N) time. I
mainly wanted to point out the factor that in the mentioned algorithm
to remove some vertexes there is no need to iterate on the vertexes.
To get a real O(log(N)) algorithm for the problem, probably it can be
done with another
On Feb 16, 4:23 am, "Limin Fu" <[EMAIL PROTECTED]> wrote:
> Hi,
> It does not take O(N) time to remove these vertexes, if you store them
> in an array allocated in a continuous memory. It only need to copy a
> block of memory without iterating on the vertexes.
In order to determine the time compl
Hi,
It does not take O(N) time to remove these vertexes, if you store them
in an array allocated in a continuous memory. It only need to copy a
block of memory without iterating on the vertexes.
On 2月15日, 下午1时52分, "Shayan Ehsani" <[EMAIL PROTECTED]> wrote:
> Hi
>
> What do you mean "remove vertex
Hi
What do you mean "remove vertexes
between A and B from the vertex list and repeat(1); "
It takes O(N) too remove these vertexes.Can you explain more?
Thanks.
On 2/14/07, Limin Fu <[EMAIL PROTECTED]> wrote:
>
>
> Hi,
>
> If the vertexes are sorted in clockwise or the reverse order, there is
Hi,
If the vertexes are sorted in clockwise or the reverse order, there is
a simple algorithm to find the instersection points in O(log(N)) time.
This algorithm works similarily as binary searching. That is:
(1) starting from the first vertex (A) in the vertexes list, and take
another vertex (B)
Hi,
I think that I've made a mistake in the explanation. Here is the
correct one:
I have 2 polygons (any shape). I have to put them on a 2D surface so
the the area of the sorrounding rectangle is minimal.
The polygons can touch each other, but NO overlapping is allowed.
Also the polygons can b
laura wrote:
> Dear all,
>
> I have a problem and I don't know how to solve it:
>
> I have 2 concave polygons and I need a way to match them so that the
> surrounding rectangle is minimal (has a minimal surface).
>
> Are there any fast algorithms for this problem?
> What about the case when the p
Look out for Bentley Ottman Sweep line algorithm to determine all intersection points of set of line segments. The worst case running time is O(N^2 lg N) since max no of intersection points is O(N^2). But since we need to determine only one intersection, we can modify the algorithm to determine if
Any takers on the second problem ?
Hi
Modifying the Vijay Venkat Raghavan N's solution.
The idea is to store the data not in an array but hash with key the
slope.
Each entry in this hash has as value other hash where the key is the
pointId and value - list of the lines in which this point participates
with this slope. If while fil
Hi,
But the 2 slopes may not have a common point. If that is not so, they
are jus referring to 2 parallel lines and not 3 collinear points.
-VijayOn 12/1/05, forest <[EMAIL PROTECTED]> wrote:
You can do without matrix, sort ALL slopes and then find 2 adjacentequal, as sorting n^2 is O(n^2 log (n^
You can do without matrix, sort ALL slopes and then find 2 adjacent
equal, as sorting n^2 is O(n^2 log (n^2)) = O(2n^2 log n) = O(n^2 log n)
hi,
i have an answer to ur first question. it is n^2 lgn, but its quite a
long procedure and I am sure there must be somethng better.
1. set up and nXn matrix, where the entry at (i,j) is the directed slope between points i and j. this is n^2
2. sort each row of this matrix. sorting one row is n
21 matches
Mail list logo
