1

Topic: Point hit in a circuit

Is available N points at which bypass the closed circuit is formed. It is necessary to learn, whether the given point in this circuit gets or remains outside. It is desirable without trigonometry,  and other long calculations since it will be fulfilled on the microcontroller.

2

Re: Point hit in a circuit

Hello, 777777w, you wrote: 7> Is available N points at which bypass the closed circuit is formed. It is necessary to learn, whether the given point in this circuit gets or remains outside. It is desirable without trigonometry,  and other long calculations since it will be fulfilled on the microcontroller. Count an amount of intersections of a ray beginning of the given point in any direction with segments. In case of the continuous closed curve the even amount is meant by a point outside, odd accordingly - inside. Analyze cases when the intersection goes on points instead of segments... Not to consider their two times..., Still it is necessary to solve on mine as to be when a segment it is parallel to a ray.

3

Re: Point hit in a circuit

Hello, 777777w, you wrote: 7> Is available N points at which bypass the closed circuit is formed. It is necessary to learn, whether the given point in this circuit gets or remains outside. It is desirable without trigonometry,  and other long calculations since it will be fulfilled on the microcontroller. int inside (double px, double py, int n, double *x, double *y) {int i, j, s; s=0; j=n-1; for (i=0; i <n; j=i ++) {if ((py <y [i] ^ py <y [j]) || py == y [i] || py == y [j]) {if ((px <x [i] ^ px <x [j]) || px == x [i] || px == x [j]) {if (y [i] <y [j] ^ (x [i]-px) * (y [j]-py)> (y [i]-py) * (x [j]-px)) s ^ = 1;} else {if (px> x [i] && y [i]! =y [j]) s ^ = 1;}}} return s;}

4

Re: Point hit in a circuit

Hello, kov_serg, you wrote: _> _> int inside (double px, double py, int n, double *x, double *y) {_> int i, j, s; _> s=0; j=n-1; _> for (i=0; i <n; j=i ++) {_> if ((py <y [i] ^ py <y [j]) || py == y [i] || py == y [j]) {_> if ((px <x [i] ^ px <x [j]) || px == x [i] || px == x [j]) {_> if (y [i] <y [j] ^ (x [i]-px) * (y [j]-py)> (y [i]-py) * (x [j]-px)) s ^ = 1; _>} else {_> if (px> x [i] && y [i]! =y [j]) s ^ = 1; _>} _>} _>} _> return s; _>} _> And in words it is possible to explain, how it works?

5

Re: Point hit in a circuit

Hello, 777777w, you wrote: 7> Hello, kov_serg, you wrote: _>> _>> int inside (double px, double py, int n, double *x, double *y) {_>> int i, j, s; _>> s=0; j=n-1; _>> for (i=0; i <n; j=i ++) {_>> if ((py <y [i] ^ py <y [j]) || py == y [i] || py == y [j]) {_>> if ((px <x [i] ^ px <x [j]) || px == x [i] || px == x [j]) {_>> if (y [i] <y [j] ^ (x [i]-px) * (y [j]-py)> (y [i]-py) * (x [j]-px)) s ^ = 1; _>>} else {_>> if (px> x [i] && y [i]! =y [j]) s ^ = 1; _>>} _>>} _>>} _>> return s; _>>} _>> 7> And in words it is possible to explain, how it works? You set an array of points enum If c=0 did not get, if =1 got. The algorithm works very simply  all edges and considers kol-in intersections on  (-inf, py). (px, py). More precisely parity of this amount.

6

Re: Point hit in a circuit

Hello, SArd, you wrote: SA> Count an amount of intersections of a ray beginning of the given point in any direction with segments. In case of the continuous closed curve the even amount is meant by a point outside, odd accordingly - inside. Analyze cases when the intersection goes on points instead of segments... Not to consider their two times..., Still it is necessary to solve on mine as to be when a segment it is parallel to a ray. It does not turn out. The point can be two times in a circuit. And then you . I understand that you took the decision from the textbook, but here such now textbooks +----------- + | | | +----------- + | | * <- a point | | + - |--------- | - + +--------- +

7

Re: Point hit in a circuit

Hello, alpha21264, you wrote: A> it does not turn out. The point can be two times in a circuit. And then you . A> I understand, what you took the decision from the textbook, but here such now textbooks A> A> +----------- + A> | | A> | +----------- + A> | | * <- a point | | A> + - |--------- | - + A> +--------- + A> And how such to process? To flood all? To flood everything, and that that inside two times?

8

Re: Point hit in a circuit

Hello, alpha21264, you wrote: A> it does not turn out. The point can be two times in a circuit. And then you . A> A> +----------- + A> | | A> | +----------- + A> | | * <- the point | | A> + - |--------- | - + A> +--------- + A> Self-intersections, for limits of a parent circuit is better to beat outputs of notches on the approach. They in any algorithm are not laid down. The decision with a ray the suitable. Fast also works with nonconvex polygons. A> I understand that you took the decision from the textbook, but here such now textbooks In 80 were the same textbooks (by the way, I recommend).

9

Re: Point hit in a circuit

Hello, T4r4sB, you wrote: TB> Hello, alpha21264, you wrote: A>> it does not turn out. The point can be two times in a circuit. And then you . A>> I understand, what you took the decision from the textbook, but here such now textbooks A>> A>> +----------- + A>> | | A>> | +----------- + A>> | | * <- a point | | A>> + - |--------- | - + A>> +--------- + A>> TB> And how such to process? To flood all? To flood everything, and that that inside two times? Well, I had a circuit directed clockwise. Thus segments appear "opening" and "closing" depending on that, there are they upwards or downwards. In this case we have two opening segments to the left of a point. The problem is taken from designing of printed-circuit boards. Some circuits on a board get divorced in steams. The circuit from the conjugate circuit should lie in a corridor - not more close than, and not further than. That is in somebody a corridor. To construct a corridor not a problem. But it, an infection, often enough appears self-intersected, with eyelets in corners. And then the program-trassirovshchik goes mad. That inside considers all outside and on the contrary. The tracer - Specctra (Cadence).

10

Re: Point hit in a circuit

11

Re: Point hit in a circuit

12

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ> it is similar on Vatti clipping. In gpc the such is implemented. But at the best gives O (n log (n)), and in the worst - degenerates in square complexity. Somehow not so similar And on Wikipedia it is directly written as for the linear time it is considered. SVZ> the Simple ray from couples/ODD NUMBERS - linear on complexity. And implementation the elementary. And here not strongly it is more difficult. If to take for a basis a source code from an adjacent branch the Author: kov_serg Date: 16.11 00:47 it is necessary to replace simply s ^ = 1 on s + = (a condition from )? +1:-1.

13

Re: Point hit in a circuit

Hello, watchmaker, you wrote: SVZ>> it is similar on Vatti clipping. In gpc the such is implemented. But at the best gives O (n log (n)), and in the worst - degenerates in square complexity. W> it is Somehow not so similar And on Wikipedia it is directly written as for the linear time it is considered. If all of us still about Vatti there it is used sweep line. And in it there is a sorting. If about something another specify, about what. SVZ>> a simple ray from couples/ODD NUMBERS - linear on complexity. And implementation the elementary. W> and here not strongly it is more difficult. If to take for a basis a source code from an adjacent branch the Author: kov_serg Date: 16.11 00:47 it is necessary to replace simply s ^ = 1 on s + = (a condition from )? +1:-1. As far as I understand, at first it is necessary to calculate winding from each side of an edge (i.e. already additional procedure turns out), and then, sorting out edges, to define, to what area we get. Simply "s + = (a condition from )? +1:-1" not . Let's tell, if there are no notches and it is necessary to ignore self-intersections to us approaches NONZERO. Count that check if the point is outside of a circuit returns: +------------- + | | | +-------------- + 0 | 1 | 2 | 1 | * <- a point | | | | + - - |--------- |--- + | | +--------- + If the ray is launched, as nearby it is offered, from (-inf, py) in (px, py) check returns hit in a circuit. It seems to me, instead of calculation S, it is possible to select the edge nearest to a point intersected by a ray and to look at it value winding. Truth it demands one more sorting (and to finish thinking about check it is lazy).

14

Re: Point hit in a circuit

Hello, SArd, you wrote: 7>> Is available N points at which bypass the closed circuit is formed. It is necessary to learn, whether the given point in this circuit gets or remains outside. It is desirable without trigonometry,  and other long calculations since it will be fulfilled on the microcontroller. SA> count an amount of intersections of a ray beginning of the given point in any direction with segments. In case of the continuous closed curve the even amount is meant by a point outside, odd accordingly - inside. Analyze cases when the intersection goes on points instead of segments... Not to consider their two times..., Still it is necessary to solve on mine as to be when a segment it is parallel to a ray. It undertakes normal a horizontal ray. And yes, separately the horizontal segment should be processed. I such like simply would discard, but is not assured, I do not remember. Still the nuance - when transits this ray exactly through a point which is the general for two segments. If a point more low on Y the second end of a segment it is ignored. There actually the heap of all gets out. For  if there is a possibility and the task allocates, it is better to do it is integer. Still nuances can be, if a circuit not only from segments, and from circle arcs

15

Re: Point hit in a circuit

16

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ> Self-intersections, for limits of a parent circuit it is better to beat outputs of notches on the approach. They in any algorithm are not laid down. SVZ> the decision with a ray the suitable. Fast also works with nonconvex polygons. With any works

17

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ> But for thought of thanks. I for hit check in nested polygons used other methods, the blessing at us is . The information (who metal, and who - notch in metal). About, and you than are engaged? I here at a leisure  for  write, I debug on cardboard . Well, and still  not the dusty I seek, where brains  it would be possible. There is no such?

18

Re: Point hit in a circuit

19

Re: Point hit in a circuit

Hello, Marty, you wrote: SVZ>> the Decision with a ray the suitable. Fast also works with nonconvex polygons. M> with any works Simply for convex polygons there is even easier a decision.

20

Re: Point hit in a circuit

Hello, Marty, you wrote: SVZ>> But for thought of thanks. I for hit check in nested polygons used other methods, the blessing at us is . The information (who metal, and who - notch in metal). M> About, and you than are engaged? I here at a leisure  for  write, I debug on cardboard . Well, and still  not the dusty I seek, where brains  it would be possible. There is no such?  for designing of printed-circuit boards, the competitor to the Alpha Couple of years back we had a vacancy the Author: V. Zudin Date: 23.12.14, new while is not present.

21

Re: Point hit in a circuit

22

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ>>> But for thought of thanks. I for hit check in nested polygons used other methods, the blessing at us is . The information (who metal, and who - notch in metal). M>> About, and you than are engaged? I here at a leisure  for  write, I debug on cardboard . Well, and still  not the dusty I seek, where brains  it would be possible. There is no such? SVZ>  for designing of printed-circuit boards, the competitor to Alpha SVZ> Couple of years back we had a vacancy the Author: V. Zudin Date: 23.12.14, new while is not present. I see. If that is, write, can I will be useful By the way, the same question to the Alpha You to me somehow with corners, I remember, not bad helped: double calcAngleDelta_StanislavVZudinV01 (double s, double e, bool ccw); double calcAngleDelta_StanislavVZudin (double s, double e, bool ccw); void calcAngleDelta_StanislavVZudin_TestStep (double s, double e, bool ccw); void calcAngleDelta_StanislavVZudin_TestSuite ();//oh, it already I went:) ) double calcAngleDelta_Marty01 (double s, double e, bool ccw); I there rethought, made the better, but for history left PS I Seek  for maintenance of trousers. Trousers are closer by the spring start to fall well While the I want to work. Colleagues, too with RSDN, offered  better current routine, I left, but after the test I did not approach them. It is too closed, told. Two-three times for a week pecked on , with remaining itself understood. It appeared, it was necessary to peck more often. PSS well and it is frank, I not so tried on the test is a sentence of new operation it was simple the trigger that leaves and to try something new. And new I wanted or new interesting operation, or  the. The  benefited PSSS Why I in this subject search for operation? Because in "about operation" personnel officers and other , and here my "little man" simply showed that it is interesting to me and that I am able

23

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ>>> the Decision with a ray the suitable. Fast also works with nonconvex polygons. M>> with any works SVZ> Simply for convex polygons there is even easier a decision. Protupil/nedorasparsil, I simply had the arbitrary polygons from arcs and segments, I something assumed that edges can be set and splines or still somehow, and  the case forgot

24

Re: Point hit in a circuit

Hello, V. Zudin, you wrote: SVZ> If all of us still about Vatti there it is used sweep line. And in it there is a sorting. If about something another specify, about what. I about that is unimportant as am arranged inside Vatti and that he there demands is not related algorithm. Not clearly what for it  to the determination task the point in a circuit lies-whether. SVZ> as far as I understand, at first it is necessary to calculate winding from each side of an edge (i.e. already additional procedure turns out), and then, sorting out edges, to define, to what area we get. It is not necessary to invent anything is it is not necessary. Do as in Wikipedia it is written or as already in an adjacent branch told: let out from a point a ray in any direction and consider number of its intersections with a circuit, considering a circuit direction (i.e. +1 or-1 for directions against and clockwise, accordingly). This number also answers about an accessory of a point to a polygon. SVZ> Count that check if the point is outside of a circuit returns: SVZ> If the ray is launched, as nearby it is offered, from (-inf, py) in (px, py) check returns hit in a circuit. s = 0 - that is the point is out of a circuit in any interpretation from above-stated (odd, nonzero etc.).

25

Re: Point hit in a circuit

Hello, alpha21264, you wrote: A> Hello, SArd, you wrote: SA>> Count an amount of intersections of a ray beginning of the given point in any direction with segments. In case of the continuous closed curve the even amount is meant by a point outside, odd accordingly - inside. Analyze cases when the intersection goes on points instead of segments... Not to consider their two times..., Still it is necessary to solve on mine as to be when a segment it is parallel to a ray. A> it does not turn out. The point can be two times in a circuit. And then you . A> I understand that you took the decision from the textbook, but here such now textbooks A> A> +----------- + A> | | A> | +----------- + A> | | * <- a point | | A> + - |--------- | - + A> +--------- + A> If the condition allows self-intersections that I did not consider, it is possible to apply algorithms of normalization. In details with them it is not familiar. Those which I saw in business can give more than one normalized circuit.