georust / georust/robust

Incircle test for weighted vertices

Open
#35 3 comments 0 reactions 0 assignees View on GitHub
Dominant language
Rust
Stars
108
Forks
16
PR merge metrics
No merged PRs in 30d

Description

Hi, first of all thanks for the great work of bringing the robust predicates to rust ! 👏🏻

I would like to advance the incircle test to work with weighted vertices, i.e. each vertex has an associated weight.
So for a given triangle $a, b, c$ and a vertex $v$ to test, the general test:

$$
incircle(triangle, v) = det
\begin{bmatrix}
a_x & a_y & a_x^2 + a_y^2 & 1 \\
b_x & b_y & b_x^2 + b_y^2 & 1 \\
c_x & c_y & c_x^2 + c_y^2 & 1 \\
v_x & v_y & v_x^2 + v_y^2 & 1 \\
\end{bmatrix} = det
\begin{bmatrix}
a_x - v_x & a_y - v_y & (a_x - v_x)^2 + (a_y - v_y)^2 \\
b_x - v_x & b_y - v_y & (b_x - v_x)^2 + (b_y - v_y)^2 \\
c_x - v_x & c_y - v_y & (c_x - v_x)^2 + (c_y - v_y)^2 \\
\end{bmatrix}
$$

becomes this one (substracting the weights from the sum):

$$
inpowercircle(triangle, v) = det
\begin{bmatrix}
a_x & a_y & a_x^2 + a_y^2 - a_w & 1 \\
b_x & b_y & b_x^2 + b_y^2 - b_w & 1 \\
c_x & c_y & c_x^2 + c_y^2 - c_w & 1 \\
v_x & v_y & v_x^2 + v_y^2 - v_w & 1 \\
\end{bmatrix}
$$

$$
= det \begin{bmatrix}
a_x - v_x & a_y - v_y & (a_x - v_x)^2 + (a_y - v_y)^2 - w_a + w_v \\
b_x - v_x & b_y - v_y & (b_x - v_x)^2 + (b_y - v_y)^2 - w_b + w_v \\
c_x - v_x & c_y - v_y & (c_x - v_x)^2 + (c_y - v_y)^2 - w_c + w_v \\
\end{bmatrix}
$$

My questions is: since the change in the matrix determinant is rather small, one substraction and addition per line, can you estimate how easily this could be incorporated into the algorithm?
I already scanned the code and saw the places for the lifting (lines 589 to 600) in `incircle()`, but I can not really see how this translates into `incircleadapt()`.

Thanks for your help in advance!

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.