Linear Algebra – How to Calculate Angle Bisectors and Intersection Points for a Polygon

Question

I am trying to construct staright skeleton of a polygon. I have coordinates array of polygon. How to construct angle bisectors of lines using coordinates? And then how can I calculate intersection point of 2 angle bisectors as in the picture? angle bisectors

Answer 1

Take a look at the following picture where the initial convex polygon boundary is in red :

It represents the variations of function $z=d(x,y)$ defined as the (internal) distance function to the boundary of the polygon. The peak $(x_0,y_0,z0)$ is such that $(x_0,y_0)$ is the most internal point and $z_0$ is its closes distance to the polygon boundary.

The different planes $P_k$ that need to be considered are those that cross the horizontal plane along edges $E_k$ of the polygon with, say, a 45° inclination. Seeing the resulting surface as a roof constituted by different planar panes, the skeleton is, in a natural way, the projection of the panes' limits (locus of points whose distance to the border can be computed in two ways = pieces of angle bissectors : here we are...).

Mathematicaly, the above distance function is defined in this way :

$$d(x,y)=\min_k(f_k(x,y)) \ \text{where} \ z=f_k(x,y)$$

is the equation of the $k$th plane.

For a fully automatic obtention of the skeleton in a general case, one has to keep track of the "right planes at the right place" by using a hierarchical organisation, proceeding inward, from the border, keeping track of which plane is still "active" at such and such distance, until there is ... no longer any active plane.

Here is the Matlab program that I have conceived for such a picture, providing in particular the exact plane equations.

x=[0,3,5,7,8,6,3,0,0];y=[0,0,1,3,7,8,7,3,0];
L=length(x)-1;
plot(x,y,'r','linewidth',2);
[X,Y]=meshgrid(0:0.01:8,0:0.01:8);
Zc=10*ones(size(X));hold on;
Z1=zeros(size(X));
for k=1:L
   vx=x(k+1)-x(k);vy=y(k+1)-y(k);
   Vx=vx/norm([vx,vy]);Vy=vy/norm([vx,vy]);
   xm=(x(k+1)+x(k))/2;ym=(y(k+1)+y(k))/2;
   P=[xm-Vy,ym+Vx,sqrt(1/2)]';% normal vect. to plane P_k
   M=[x(k),x(k+1);y(k),y(k+1)];
   dd=det([[M,[P(1);P(2)]];ones(1,3)])
   den=1/dd;
   Z=den*P(3)*(Y*vx-X*vy+det(M));%plane equ.
   Zc=min(Zc,Z);Zc=max(Zc,Z1);
end; 
view([-29,36]);
g=surf(X,Y,Zc);
set(g,'edgecolor','none')

Appendix : A very straightforward way to obtain the analytical equation of the two angle bissectors of two lines with resp. equations $a_1x+b_1y+c_1=0$ and $a_2x+b_2y+c_2=0$ is to express that a point $M(x,y)$ belongs to one of them iff its signed distance is the same to both of them, i.e.,

$$\dfrac{a_1x+b_1y+c_1}{\sqrt{a_1^2+b_1^2}}=\pm \dfrac{a_2x+b_2y+c_2}{\sqrt{a_2^2+b_2^2}}$$

($\pm$ sign for distinguishing interior and exterior angle bissectors)