3
$\begingroup$

The problem is as follows

I have two intersected closed curves and each curve was represented by two arrays respectively, which means we know the coordinates of every points $(x_i,y_i)$ but no analytic formula was given. For example, an example was given in the plot: two intersected ellipse

I want to remove those points overlapped or inside the exterior boundary. The two intersected points (blue dots) were given in $(x_1,y_1),(x_2,y_2)$. What I did was to remove points with coordinates between x1 and x2, y1 and y2, and get a plot like: some interior points were removed

Apparently, this was not enough for removing all interior points. So does anyone have idea of how to identify those inside points? Bear in mind that the boundary was not yet known until the inside and outside points were distinguished. So this is not a same problem as posted in Find grid points interior to a closed curve

Thank you all!

$\endgroup$

1 Answer 1

2
$\begingroup$

You are trying to find the boolean union of the regions the two curves enclose. So, you could just look up "boolean operations on polygons". The Wikipedia page has links to several available software packages. But, if you want to do it yourself, here's one approach ...

Let's call the two curves $A$ and $B$.

First, find the points where the two curves intersect.

Divide both curves into pieces at these intersection points. Call the pieces $A_1, \ldots, A_m$ and $B_1, \ldots, B_n$. In your example, each curve gets split into two pieces.

The boundary you want consists of the pieces $A_i$ that are outside $B$, plus the pieces $B_j$ that are outside $A$. So, for each $i \in \{1,2, \ldots, m\}$, we need to decide whether $A_i$ is inside or outside of $B$. To do this, just take one of the vertices of $A_i$ and check if its inside or outside of $B$. You will need a "point-in-polygon" test to do this. There are two basic approaches, both described here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .