Re: overlapping area of two ellipses

Kaba wrote:
In article <b16cb342-c4ad-4349-82e5-dfefa4998e73
@y38g2000hsy.googlegroups.com>, info@xxxxxxxxxxx says...
2) Find out the intersection of the convex polygons (which is again a
convex polygon).

A sweep-algorithm works for 2).

Hi Kaba,

Can you help me to find a paper on this subject? I need to find
intersection of a polygon an a rectangle.

See the Sutherland-Hodgman algorithm. Google helps, for example:

http://www.cs.drexel.edu/~david/Classes/CS430/Lectures/L-05
_Polygons.6.pdf

As the paper reads, the same idea can be generalized to clipping inside a convex polygon. However, for the convex-convex (polygon) clipping I would use a sweep-based algorithm instead for increased performance (at least asymptocally):

http://en.wikipedia.org/wiki/Sweep_line_algorithm

Yes, that's a common problem. I've coded it at least twice.
It's all bookkeeping, not math. Plenty of examples in the
literature.

Ellipse vs. ellipse is more of a puzzle-like cute problem.
It might even be possible to develop a closed form solution,
but it's going to have multiple regions to be integrated
separately. Why do you need one?

I once spent months trying to develop a closed form solution
for the distance between two Pentland deformed superquadrics,
then gave up and went with convex polyhedra.

John Nagle
Animats
.

Relevant Pages

  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)
  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)
  • Re: From Triangle tiles to convex Polygons.
    ... all internal edges that don't have a connection to a convex vertex. ... You don't get the minimal convex decomposition that way. ... like metric to avoid all the long and thin triangles. ... the polygon with holes to a simple polygon. ...
    (comp.graphics.algorithms)
  • Re: From Triangle tiles to convex Polygons.
    ... I start out with a complicated non-convex polygon with holes. ... it into OpenGL GLU, and I get back a few hundred triangles that ... problem is that a few hundred triangles is way too many, ... I think you can do this by taking your triangulation and merge triangles to build multiple convex polygons from it. ...
    (comp.graphics.algorithms)
  • Re: Arrange points so polygon is not self intersecting
    ... I was wondering if someone knows some sort of algorithm to find an ... order for a set of points so that the polygon of those points is not ... that convex polygon. ... resemble a sort of circular labyrinth. ...
    (sci.math)
Loading