0
$\begingroup$

[Input]: the begin and end points of an arbitrary line (small red points) and the line width (green line)
[Example]: begin=(20,20), end=(100,50), width=5

enter image description here

[Output]: The set of pixels (not the total area) that are in the yellow rectangle
[Example]: {(20,20), (20,21), (20,22),...etc.}

How can i calculate the output set?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ I think this still classifies as cross-posting. But, to me, it seems to be slightly worse since one has to click on the link before getting to the question. $\endgroup$ – Bernhard Barker May 21 '13 at 11:03
  • $\begingroup$ i removed the question from stackoverflow $\endgroup$ – A.B. May 21 '13 at 14:24
1
$\begingroup$

An algorithm to know if a point $P$ is in the rectangle $ABCD$ is to check that

  • $\vec{AB}\cdot \vec{AP}\leq 0$,
  • $\vec{DC}\cdot \vec{DP}\geq 0$,
  • $\vec{DA}\cdot \vec{DP}\leq 0$, and
  • $\vec{CB}\cdot \vec{CP}\geq 0$.

Since you have the two extremity point and the width $A,B,C$ and $D$ should be easy to compute. And you can restrict the point you are checking to $(x,y)$ such that $min(A_x,B_x,C_x,D_x)\leq x \leq max(A_x,B_x,C_x,D_x)$ and $min(A_y,B_y,C_y,D_y)\leq y \leq max(A_y,B_y,C_y,D_y)$.

It may not be optimal but it should be working.

Ps: I agree with @Dukeling.

[Edit] to compute $A$

If begin and end have the same abscissa (or ordinate) then it easy. Otherwise:

Let $begin=(b_x,b_y)$, $end=(e_x,e_y)$, $A=(x,y)$ and $width/2=w$ you know that: $$\vec{beginend}=((e_x-b_x),(e_y-b_y))$$ $$\vec{beginA}=((x-b_x),(y-b_y))$$ hence: $$\vec{beginend}\cdot\vec{beginA}=(e_x-b_x)(x-b_x)+(e_y-b_y)(y-b_y)=0$$ hence: $$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$ Also $|\vec{beginA}|=w$ hence: $$(x-b_x)^2+(y-b_y)^2=w$$ hence: $$(b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)}-b_x)^2+(y-b_y)^2=w$$ Solve this equation and you have $y$, then replace the solution in $$ x = b_x -\frac{(e_y-b_y)(y-b_y)}{(e_x-b_x)} $$ and you have $x$.

Notice that you have two solution one for $A$ the other for $D$ ...

Do the same for $B$ and $C$ with appropriate vectors.

Improve this answer
$\endgroup$
  • $\begingroup$ The problem is that the line is random. Therefore i don't know how to compute the A,B,C,D of the rectangle $\endgroup$ – A.B. May 21 '13 at 14:26
  • $\begingroup$ what do you mean the line is random? you are given 'begin' 'end' and the width right? so you can compute ABCD, no? $\endgroup$ – wece May 21 '13 at 14:49
  • $\begingroup$ The user draws an arbitrary line. Let's imagine 3 different lines are sketched: one is verticel the other one is horizontal and the last one is with any unknown slope. How can you compute A,B,C,D in this case? $\endgroup$ – A.B. May 21 '13 at 14:56
  • $\begingroup$ you have begin and end and width?? $\endgroup$ – wece May 21 '13 at 14:58
  • $\begingroup$ How the line (and its corresponding rectangle) is shaped, is based on the slope and (in my case) the Bresenham's Algorithm. You don't have any fixed line where you can say, i would just add the width to x or y coordinates of begin and end to find A,B,C,D. $\endgroup$ – A.B. May 21 '13 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.