Custom QLine
-
Hi Guys, i'm thinking how can i create custom QLine so i can add extra features like
.equation()to get line equation information of that particular line.i use PyQt4 in Python 2.7, and i try to store it in Dictionary, but that doesn't fill like the best solution, what i'm trying to do is to have the points as well as line equation of the line, so i can check if there is any line intersection happening.
example:
# List of shape points ShapePoints = [(400,200),(100,100),(200,400),(500,600),(500,400),(800,400),(600,500),(800,600),(1100,400),(1000,200),(700,300),(600,100),(400,200)] #Dictionary of shape's points, Lines and Equations ShapeDictionary = {} for num in range(0,(len(ShapePoints)-1)): p1 = [ShapePoints[num][0],ShapePoints[num][1]] p2 = [ShapePoints[num+1][0],ShapePoints[num+1][1]] Line = QtCore.QLine(p1[0],p1[1],p2[0],p2[1]) Equation = LineEquation(Point1St=p1, Point1End=p2) ShapeDictionary["Point %s-%s"%(num, num+1)] = { "Line" : Line, "Equation": Equation} #Dictionary of 2 point's, Line and Equation Line = QtCore.QLine(20,10,1000,2000) Equation = LineEquation(Point1St=[20,10], Point1End=[1000,2000]) LineDictionary = { "Line" : Line, "Equation": Equation}This is the
LineEquationfunction:def LineEquation(Point1St, Point1End): ''' Finding the Slope and Intercept of 2 points Return slope, intercept, equation example: y = mx + c m = (y2 - y1) / (x2 - x1) c = (x - x1) + y1 ''' x1 = Point1St[0] y1 = Point1St[1] x2 = Point1End[0] y2 = Point1End[1] # General Line Equation y = mx + c if x1 != x2 and y1 != y2: slope = float((y2-y1))/float((x2-x1)) intercept = (slope*(-x1))+y1 equation = "General" # Horizontal Line Equation x = c elif x1 == x2: slope = 0 intercept = x1 equation = "Horizontal" # Vertical Line Equation y = c elif y1 == y2: slope = 0 intercept = y1 equation = "Vertical" return slope,intercept,equationNow, if there are lots of points, it will take lots of memory and become kind of out of control, right? so i think i should try something different and add some features in QLine or make a totally new custom function to manage that.
please feel free it doesn't have to be in Python, if you use C++, write in C++, also any comment/suggestion/tips are appreciated.
@Bernard-Rouhi
Hello,
Putting the code aside for a moment this:y = mx + cis not a line equation, this is the functiony(x)which happens to be a line. Why I'm making a point of this is because this can not represent a vertical line. Now, if you want to have the line equation it's this one:A * x + B * y + C = 0, which has a normal vector n (-B, A). This particular set of parameters you could obtain by solving a linear system of equations for the two points. Suppose you have the normal vector n for the line you're searching for and the points r1 (x1, y1) and r2 (x2, y2) that define the line. Then the scalar product between the direction and the normal vector is zero, meaning they're orthogonal: (r1 - r2) . n = 0. I'll not bore you with the linear algebra, the parameters A, B and C you can extract from the two points' coordinates directly:A = y2 - y1 B = x1 - x2 C = x2 * y1 - x1 * y2If you want to see if two lines intersect you just take the scalar product of their normalized normal vectors and see if you get 1, if you get 0, then they're perpendicular.
Now back to the code. I suggest using your own class that extract the information you require and performs whatever checking you wish to implement, instead of subclassing
QLine. That said you could just implementQLineEquationthat has a methodQLineEquation::setLineand keeps track of the line equation. Then you could check if two lines intersect (and where if you need) by using suchQLineEquationinstances.I hope this helps.
Kind regards. -
Putting the code aside for a moment:
@Bernard-Rouhi said:
so i can check if there is any line intersection happening
If you use standard floating-point arithmetic and non-robust geometric predicates you are entering the house of pain.
-
Putting the code aside for a moment:
@Bernard-Rouhi said:
so i can check if there is any line intersection happening
If you use standard floating-point arithmetic and non-robust geometric predicates you are entering the house of pain.
@Wieland
you are entering the house of pain
Well this is pretty simple linear algebra. Having two line equations of the aforementioned type (my previous post) the intersection point's coordinates is found by solving the system of equations:
A1 * x + B1 * y + C1 = 0 A2 * x + B2 * y + C2 = 0Which obviously can be written in matrix form as well. However I always advise usage of ready-made libraries for reasons of numerical stability.
Kind regards.
-
@Wieland
you are entering the house of pain
Well this is pretty simple linear algebra. Having two line equations of the aforementioned type (my previous post) the intersection point's coordinates is found by solving the system of equations:
A1 * x + B1 * y + C1 = 0 A2 * x + B2 * y + C2 = 0Which obviously can be written in matrix form as well. However I always advise usage of ready-made libraries for reasons of numerical stability.
Kind regards.
@kshegunov He said he wants to check if "any line intersection [is] happening". The careless solution will simply always answer "yes, we have an intersection" even when the lines are parallel.
@kshegunov said:
I always advise usage of ready-made libraries
I strongly agree.
-
@kshegunov He said he wants to check if "any line intersection [is] happening". The careless solution will simply always answer "yes, we have an intersection" even when the lines are parallel.
@kshegunov said:
I always advise usage of ready-made libraries
I strongly agree.
@Wieland
He said he wants to check if "any line intersection [is] happening". The careless solution will simply always answer "yes, we have an intersection" even when the lines are parallel.
Just for fullness, I've provided the criterion for such a check in my first post, if n1.n2 = 1 then the lines are parallel, where n1 is the first line's normal vector, and n2 is the second's.
-
Hi Guys, i'm thinking how can i create custom QLine so i can add extra features like
.equation()to get line equation information of that particular line.i use PyQt4 in Python 2.7, and i try to store it in Dictionary, but that doesn't fill like the best solution, what i'm trying to do is to have the points as well as line equation of the line, so i can check if there is any line intersection happening.
example:
# List of shape points ShapePoints = [(400,200),(100,100),(200,400),(500,600),(500,400),(800,400),(600,500),(800,600),(1100,400),(1000,200),(700,300),(600,100),(400,200)] #Dictionary of shape's points, Lines and Equations ShapeDictionary = {} for num in range(0,(len(ShapePoints)-1)): p1 = [ShapePoints[num][0],ShapePoints[num][1]] p2 = [ShapePoints[num+1][0],ShapePoints[num+1][1]] Line = QtCore.QLine(p1[0],p1[1],p2[0],p2[1]) Equation = LineEquation(Point1St=p1, Point1End=p2) ShapeDictionary["Point %s-%s"%(num, num+1)] = { "Line" : Line, "Equation": Equation} #Dictionary of 2 point's, Line and Equation Line = QtCore.QLine(20,10,1000,2000) Equation = LineEquation(Point1St=[20,10], Point1End=[1000,2000]) LineDictionary = { "Line" : Line, "Equation": Equation}This is the
LineEquationfunction:def LineEquation(Point1St, Point1End): ''' Finding the Slope and Intercept of 2 points Return slope, intercept, equation example: y = mx + c m = (y2 - y1) / (x2 - x1) c = (x - x1) + y1 ''' x1 = Point1St[0] y1 = Point1St[1] x2 = Point1End[0] y2 = Point1End[1] # General Line Equation y = mx + c if x1 != x2 and y1 != y2: slope = float((y2-y1))/float((x2-x1)) intercept = (slope*(-x1))+y1 equation = "General" # Horizontal Line Equation x = c elif x1 == x2: slope = 0 intercept = x1 equation = "Horizontal" # Vertical Line Equation y = c elif y1 == y2: slope = 0 intercept = y1 equation = "Vertical" return slope,intercept,equationNow, if there are lots of points, it will take lots of memory and become kind of out of control, right? so i think i should try something different and add some features in QLine or make a totally new custom function to manage that.
please feel free it doesn't have to be in Python, if you use C++, write in C++, also any comment/suggestion/tips are appreciated.
@Bernard-Rouhi Sorry for derailing your thread. Just one last hint: http://www.cs.berkeley.edu/~jrs/papers/robustr.pdf
-
@Bernard-Rouhi Sorry for derailing your thread. Just one last hint: http://www.cs.berkeley.edu/~jrs/papers/robustr.pdf
@Wieland
Sorry for derailing your thread.
As I see it, this thread is exactly for discussing how and why, so I don't believe you're derailing it in any way. In any case, I'm not at all proponent of arbitrary precision arithmetic. I find that for most intents and purposes using
doublewill give you enough mantissa bits do pretty much what you want, if you take care to use the proper algorithms. For example, naive summations are a no-no! That said, one of the best-designed linear algebra libraries I've worked with is Eigen and it performs quite well. It also thankfully doesn't fight with Qt. However, the most robust solution will depend very much on the problem, as no algorithm/data structure scales perfectly for all situations.@Bernard-Rouhi
Bernard, can you tell us what are you trying to achieve, so maybe better "guidance" could be provided?Kind regards.
-
@kshegunov :
Thanks for theA * x + B * y + C = 0formula, i did read about it, watched some videos, but i didn't understand it, i mean they give me the formula but they didn't explain it, so if i don't understand it, how can i make better code or debug it, also i'm not familiar with linear algebra (which is my fault, i'm trying to catch up).However, i do understand the
y = mx + creally well, about special cases like Vertical or Horizontal i came up with a simple solution, when we sayy = mx + cit's exactly same asx = my + calsox = candy = c, so Intercept is the key for special cases, in myLineEquation()function i do get type of equation like General, Vertical or Horizontal, and base on that i know Intercept is x or y.
so if i do this:>> P1 = [100,10] >> P2 = [100,1200] >> LineEquation(Point1St= P1, Point1End= P2) (0, 100, 'Vertical')the return is Slope, Intercept and Equation Type, simple enough, the
"Vertical"meanxand intercept is 100,
and in case of Horizontal:>> P1 = [10,200] >> P2 = [1200,200] >> LineEquation(Point1St= P1, Point1End= P2) (0, 200, 'Horizontal')Horizontal mean
yand intercept is 200.so to find the intersection, using Line Intersection formula is the solution, which is pretty simple.(sorry i can't use MathJax in here but i leave the link to it)
keeping in mind that Line Intersection is giving the intersection without any limitation, so the solution i come up with is to check if the intersection x and y is within the line that i'm checking.
so that's how i work around it, i'm not Mathematician and my solution might sound silly, so yeah when i see
A * x + B * y + C = 0i don't really understand where A and B come from? and were is the slope? or how can i use this in line intersection? you know what i mean.Why i'm doing this:
okay, i'm writing a application to fit/generate different size of Rectangular in Any direction in Any shape. (yeah, i know, it sounds complicated and not clear.)so i do have a library of different sizes of Rectangular and using knapsack problem and PolyFill Scan Conversion of a Polygon to fit best possible size in the area which the user will choice from what angle and where need to start generate those sets of rectangular.
right now i'm focusing on PolyFill Scan Conversion of a Polygon, which is working fine, just i found the way i'm doing, could take lots of memory. worst case could cause crash. because i make lots of dictionary of each lines with their points, intercept, slope and etc. so i was thinking maybe i need to improve the way i'm handling that and try not to store them in memory while not reducing the performance of application.
so why creating class is better than adding those feature into Qline it self? if i have custom QLine i can add those features and everything will be within QLine right?
@Wieland :
I don't know calculus, but it's a good excuse to learn it, thanks for document. -
@Bernard-Rouhi
Well, you seem to have put yourself an ambitious task. I advise to get a good grasp on the problem domain, which would include some basic linear algebra and some very basic calculus, otherwise you'll have trouble understanding what's done and why, even if you use an external library.just i found the way i'm doing, could take lots of memory
Is it, or is it not taking a lot of memory? If it's only a prospect just forget about it, you don't need to bother yourself at this point in the beginning with that issue. Think about designing your code well, and worry about diminished performance at a later stage.
try not to store them in memory while not reducing the performance of application.
Moving it from memory to any other medium will cause performance degradation, there's no way to avoid that.
so why creating class is better than adding those feature into Qline it self? if i have custom QLine i can add those features and everything will be within QLine right?
For one
QLineis nothing more than a set of two points in a discrete rectangular coordinate system (their coordinates are integers) and you most probably will need to work with floating point numbers, which defeats the purpose of deriving fromQLine. Additionally, you're not really extending the line, but are instead adding complete new set of primitives so I do believe it is better to use aggregation instead of inheritance.Kind regards.
Read and abide by the Qt Code of Conduct
-
@Bernard-Rouhi
Well, you seem to have put yourself an ambitious task. I advise to get a good grasp on the problem domain, which would include some basic linear algebra and some very basic calculus, otherwise you'll have trouble understanding what's done and why, even if you use an external library.just i found the way i'm doing, could take lots of memory
Is it, or is it not taking a lot of memory? If it's only a prospect just forget about it, you don't need to bother yourself at this point in the beginning with that issue. Think about designing your code well, and worry about diminished performance at a later stage.
try not to store them in memory while not reducing the performance of application.
Moving it from memory to any other medium will cause performance degradation, there's no way to avoid that.
so why creating class is better than adding those feature into Qline it self? if i have custom QLine i can add those features and everything will be within QLine right?
For one
QLineis nothing more than a set of two points in a discrete rectangular coordinate system (their coordinates are integers) and you most probably will need to work with floating point numbers, which defeats the purpose of deriving fromQLine. Additionally, you're not really extending the line, but are instead adding complete new set of primitives so I do believe it is better to use aggregation instead of inheritance.Kind regards.
I advise to get a good grasp on the problem domain, which would include some basic linear algebra and some very basic calculus, otherwise you'll have trouble understanding what's done and why, even if you use an external library.
i guess i have to, i'm glad www.khanacademy.org is out there, they are really helpful.
Is it, or is it not taking a lot of memory?
if there is only one shape, it doesn't take much memory, but if there are 20 of them and also if they are huge in size, yeah it will take lots of memory, yeah i agree with you, i think once i complete it, then i start to optimize them.
For one QLine is nothing more than a set of two points in a discrete rectangular coordinate system (their coordinates are integers) and you most probably will need to work with floating point numbers, which defeats the purpose of deriving from QLine. Additionally, you're not really extending the line, but are instead adding complete new set of primitives so I do believe it is better to use aggregation instead of inheritance.
you are right, QLine only support integer and even QLineF that support decimal doesn't look any helpful, creating aggregation class is the better solution.
Thanks alot man.
-
@Bernard-Rouhi
Hello,i guess i have to, i'm glad www.khanacademy.org is out there, they are really helpful.
I don't presume to know your circumstances, for me linear algebra and single-variable calculus was covered in my first semester at the university, so I wouldn't have use of such sites. However, if they work for you, by all means use all the help you can get.
Thanks alot man.
No problem, I'm glad the discussion is helpful.
Kind regards.
Read and abide by the Qt Code of Conduct
-
@Bernard-Rouhi
Hello,i guess i have to, i'm glad www.khanacademy.org is out there, they are really helpful.
I don't presume to know your circumstances, for me linear algebra and single-variable calculus was covered in my first semester at the university, so I wouldn't have use of such sites. However, if they work for you, by all means use all the help you can get.
Thanks alot man.
No problem, I'm glad the discussion is helpful.
Kind regards.
@kshegunov
Hi,I don't presume to know your circumstances, for me linear algebra and single-variable calculus was covered in my first semester at the university, so I wouldn't have use of such sites. However, if they work for you, by all means use all the help you can get.
yeah, it's fine, i think you did study Computer Science, right? for me programming start at high school and ended there for while and after that, i studied Multimedia in Art, you know 3D sculpting/Modeling and animation, so after graduation, while i was working, programming became some sort of hobby and self thought, but work limitation changed my aim, now i'm picking up math from scratch and improving my programming skills (though, can't wait to get my hands on OpenGL/OpenCL).
Complicated path ha, but i guess it's some sort of evolving. :D
-
@kshegunov
Hi,I don't presume to know your circumstances, for me linear algebra and single-variable calculus was covered in my first semester at the university, so I wouldn't have use of such sites. However, if they work for you, by all means use all the help you can get.
yeah, it's fine, i think you did study Computer Science, right? for me programming start at high school and ended there for while and after that, i studied Multimedia in Art, you know 3D sculpting/Modeling and animation, so after graduation, while i was working, programming became some sort of hobby and self thought, but work limitation changed my aim, now i'm picking up math from scratch and improving my programming skills (though, can't wait to get my hands on OpenGL/OpenCL).
Complicated path ha, but i guess it's some sort of evolving. :D
i think you did study Computer Science, right?
No, not really. I haven't had formal computer science education. I've studied physics in school, and have started with programming as a hobby at 10th grade. Then in the university I studied physics again, and then as a master I studied applied physics, and now am doing a PhD in theoretical nuclear physics. In any case I'm self-thought myself (programming-wise), so I believe that's not uncommon.
Kind regards.
